Podejście z binary searchem.

Question

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ść?

Answer 1

Hint: digit dp

Answer 2

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

Comments

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

---

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

---

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.

---

Dałbyś radę napisać jakiś kod bądź pseudokod