Masala #0563

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 22 %
14

  

Azimjonning sovg'asi

Azimjon bosh qotirmalarga qiziqadi. U bir kuni akasi bilan shunday o'yin o'ynadiki o'yinda \(n\) ta uy bor, uylar 1 dan \(n\) gacha o'sish tartibida raqamlangan, bu uylarning ichida \(k\) tadan tuzoq bor. Azimjonning akasi \(A\) raqamli uyga sovg'a yashirgan. Azimjon sovg'ani olguncha eng kamida nechta tuzoqni bosib utishi kerak. Azimjon bu o'yinda optimal (eng yaxshi) o'yinchi deb hisoblansin.

Azimjonga yordam sifatida, akasi sovg`ali xonadan tashqari hamma xonaga > yoki < belgili plakat ilib chiqdi > belgisi, qidirilayotgan xona teparoqda

< belgisi qidirilayotgan xona pastroqda ekanligini anglatadi
Uy raqamlari tartiblangan holda bo'ladi. Azimjonnig uzi bu ishni uddalay olmaydi, siz Azimjonga yordam bering.


Kiruvchi ma'lumotlar:

Bitta qatorda \(n\), \(k\) va \(A\) butun sonlari. \((1 \le A \le n \le 10^{18}, 1 \le k \le 5000)\)


Chiquvchi ma'lumotlar:

Bitta qatorda Azimjonning eng yaxshi usul bilan tushungan tuzoqlar soni.


Misollar
# input.txt output.txt
1
21 5 20
20
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin