Masala G
Toshlar bilan o'yin
Shohruh va Farrux sevimli mashg'uloti matematik o'yin o'ynashmoqda. Bu safar ular n ta toshni qopga solib, quyidagicha o'ynashdi:
- Shohruh birinchi bo'lib boshlaydi, keyin Farrux, keyin yana Shohruh, keyin Farrux va hokazo;
- Shohruh birinchi harakatida qopdan istalgan miqdordagi toshlarni (1 dan N gacha) olishi mumkin;
- Keyingi yurishlarning har birida o'yinchi kamida 1 ta tosh olishi kerak va oldingi yurish paytida olingan toshlar miqdoridan ko'pi bilan ikki baravar ko'p olishiga ruxsat beriladi; tabiiyki, qopda qolgan miqdordan ko'proq tosh olish mumkin emas;
- Oxirgi toshni olgan o'yinchi g'olib hisoblanadi.
Shohruh ham, Farrux ham optimal o'ynashadi (agar bir o'yinchi ikkinchisini mag'lub etishi mumkin bo'lsa, u o'yinchi doimo g'alaba qozonadi). Biz Shohruhning o'yinda g'alaba qozonishi kafolatlaydigan birinchi yurishi uchun minimal toshlar sonini topishimiz kerak.
Kiruvchi ma'lumotlar:
Yagona qatorda butun son N - toshlar soni kiritiladi.
\(2 \le N \le 10^{15}\)
Chiquvchi ma'lumotlar:
Minimal toshlar sonini chop eting.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 |
1 |
| 2 |
7 |
2 |
| 3 |
13 |
13 |
Izoh:
1-test:
Biz barcha toshlarni olgan holda g'alaba qilishimiz mumkin. Lekin bu minimal emas. Agar biz 1 ta tosh oladigan bo'lsak, keyingi yurishda raqib nechta tosh olishidan qat'iy nazar g'alaba qilamiz.
Telegram kanalimizga obuna bo'ling