Masala E
Javoxir va Yetti
Javoxirning juda maxsus soni bor — bu sonni 7 ga bo'lganda qoldiq 0 bo'ladi. Javoxir bu xususiyat haqida o'ylaganida, u doim: "WOW, bu ajoyib son!" deydi.
Hammaga ma'lumki, Javoxir oddiy uy hayvoni emas — u aqlli va qiziquvchan. Shuning uchun u asl sonni quyidagicha o'zgartiradi: Javoxir sonni ikkilik (binary) ko'rinishda yozadi, so'ngra ikkita indeks tanlaydi va o'sha pozitsiyalardagi bitlarni o'zaro almashtiradi. U bir muddat shu kabi bir necha almashtirish amallarini bajaradi.
Javoxir bajargan almashtirish amallarining umumiy sonini eslamaydi, lekin u ikkilik ko'rinishda qaysi pozitsiyalar biror algaqida almashtirilganini eslab qolgan. Bundan tashqari, u eng muhim bit (most significant bit) hech qachon almashtirilmaganini ham eslaydi.
Endi Javoxir asl sonni tiklashni istaydi, ammo u band — shuning uchun sizdan yordam so'raydi. Javoxirga yordam bera olasizmi?
Kirish bir nechta test holatlaridan iborat. Har bir test holati uch qatordan tashkil topadi.
Birinchi qatorda bitta butun son \(n\) — o'zgartirilgan son \((7 \le n \le 2^{60})\).
Ikkinchi qatorda bitta butun son \(k\) — almashtirilgan pozitsiyalar soni \((2 \le k \le 20)\).
Uchinchi qatorda \(k\) ta turli butun son o'sish tartibida — eng kichik aniq bitdan (zero-indexed) hisoblab almashtirilgan pozitsiyalar.
Har bir test holati uchun bitta butun son chop eting: 7 ga bo'linadigan tiklangan sonni. Agar bir nechta javob mavjud bo'lsa, eng katta qiymatni chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
79 5 0 1 2 4 5 |
91 |
| 2 |
21 2 0 3 |
28 |
| 3 |
1152921504606846975 5 13 39 40 58 59 |
1152921504606846975 |
1-test holatida asl son (almashtiruvlarsiz) 91 ga teng.
Indekslar: 6 5 4 3 2 1 0
91 = 1 0 1 1 0 1 1
Javoxir quyidagi almashtirish amallarini bajargan deb faraz qilaylik:
swap(0, 2, 1011011) -> 1 0 1 1 1 1 0 = 94
swap(4, 5, 1011110) -> 1 1 0 1 1 1 0 = 110
swap(0, 1, 1101110) -> 1 1 0 1 1 0 1 = 109
swap(2, 4, 1101101) -> 1 1 1 1 0 0 1 = 121
swap(0, 1, 1111001) -> 1 1 1 1 0 1 0 = 122
swap(2, 4, 1111010) -> 1 1 0 1 1 1 0 = 110
swap(0, 5, 1101110) -> 1 0 0 1 1 1 1 = 79
Shunday qilib, 79 soni hosil bo'lgan. E'tibor bering: Javoxir bir xil indeksni bir necha marta almashtirishga va 6-pozitsiya hech qachon almashtirilmaganiga.
2-test holatida 21 soni uchun faqat 0 va 3-pozitsiyalar almashtirilgan. 7 ga bo'linadigan eng katta son 28 ga teng.
Telegram kanalimizga obuna bo'ling