Podejście z binary searchem.

pytanie zadane 30 kwietnia 2023 w C i C++ przez Dani Obywatel (1,450 p.)

Witam, rozwiązałem zadanie : https://codeforces.com/problemset/problem/919/B , z brutem ale chociaż tak. Patrząc na tagi pisze tam, że jednym z rozwiązań jest binary search. Chciałbym wiedzieć jak zoptymalizować operacje, i rozwiązać to przez binary search'a. Czy wiecie może jak by to podejść?

2 odpowiedzi

odpowiedź 1 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

odpowiedź 1 maja 2023 przez nanautzin Obywatel (1,510 p.)

Jeżeli dobrze rozumiem zadanie, to nie widzę tu sensu użycia binary search, bo nie robisz tu żadnego przeszukania tylko operacje matematyczną

komentarz 1 maja 2023 przez Dani Obywatel (1,450 p.)
edycja 1 maja 2023 przez Dani

W editorialu tego zadania, pisze, że można to rozwiązać binary searchem, żeby k mogło być <= 10^18.

komentarz 1 maja 2023 przez nanautzin Obywatel (1,510 p.)

A single line with a positive integer k (1≤k≤10000).

To widocznie ja dobrze nie rozumiem tego zadania

Żeby binary search miało sens kontener musi byc posortowany

komentarz 1 maja 2023 przez Whistleroosh Maniak (57,400 p.)

Jeśli w tym zadaniu weźmiesz taki kontener, że arr[i] to liczba liczb mniejszych/równych od i oraz o sumie cyfr równej 10 to ten kontener jak najbardziej będzie posortowany.