~/algor $ cat masalalar/sehrli-tangalar
Sehrli Tangalar
ALGOR bilimlar xazinasida qadimiy sehrli sandiq bor. Sandiqda qiymatlari 2 ning darajalari bo'lgan tangalar mavjud:
$$1, 2, 4, 8, 16, 32, \dots, 2^k, \dots$$
Har bir qiymatdagi tangadan cheksiz miqdorda olish mumkin.
Sandiqni ochish uchun unga qiymatlari yig'indisi aynan S ga teng bo'lgan tangalar to'plamini tashlash kerak. Biroq sandiqning qat'iy talabi bor:
Tashlangan tangalar soni albatta TOQ (1, 3, 5, 7, ...) bo'lishi shart!
Sizning vazifangiz — yig'indisi S ga teng bo'ladigan va tangalar soni toq bo'lgan to'plam uchun eng kam (minimal) tangalar sonini topishdir.
Agar bunday toq sondagi tangalar yordamida S summani yig'ishning iloji bo'lmasa, -1 chiqaring.
Kiruvchi ma'lumotlar
Yagona qatorda bitta butun son: S ($1 \le S \le 10^{18}$) kiritiladi.
Chiquvchi ma'lumotlar
Yig'indisi S bo'lgan toq sondagi minimal tangalar sonini chiqaring.
Izoh
1-namuna: 5 -> 3 (5 = 4 + 1 ikkita tanga (juft), lekin 4 ni ikkita 2 ga bo'lsak: 2 + 2 + 1 = 3 ta tanga (toq))
2-namuna: 7 -> 3 (7 = 4 + 2 + 1, 3 ta tanga)
3-namuna: 2 -> 1 (2 = 2 bitta tanga, 1 toq son)
Misollar
5
3
7
3
2
1
Yechim tahlili
Avval o'zingiz yechib ko'ring — tahlilni o'qish o'rganishga yordam beradi, lekin javobni tayyor beradi.
Masala tahlili (Problem C)
S sonini 2 ning darajalari yig'indisi sifatida ifodalaganda minimal tangalar soni S ning ikkilik sanoq tizimidagi birlar soni ($popcount(S)$) ga teng.
- Agar $popcount(S)$ toq son bo'lsa, eng kam tangalar soni aynan $popcount(S)$ bo'ladi.
- Agar $popcount(S)$ juft son bo'lsa, tangalar soni juft bo'lib qoladi. Toq qilish uchun ixtiyoriy 2^p ($p \ge 1$) tangani ikkita $2^{p-1} ga ajratsak, umumiy tangalar soni +1$ ga oshadi va toq bo'ladi: $popcount(S) + 1$.
$S \ge 1 va popcount(S)$ juft bo'lgani sababli kamida bitta $p \ge 1$ bo'lgan bit mavjud (chunki yagona p=0 bo'lgan son 1 bo'lib, uning popcounti 1 — toq).
Xulosa:
- Agar $popcount(S) % 2 == 1$ bo'lsa: $popcount(S)$
- Aks holda: $popcount(S) + 1$.
Vaqt murakkabligi: $O(1)$ (__builtin_popcountll).