A. Oson Ifoda

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga n va k butun sonlari beriladi. Siz quyidagi kasrlarni:
\(\frac{1}{2^k},\ \frac{2}{2^k},...,\frac{n}{2^k}\)

qisqarmas shaklga olib keling va suratlari yig'indisini chop eting.

Kasr qisqarmas bo'lishi uchun maxraji va surati EKUB qiymati 1 ga teng bo'lishi kerak.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T(\(1\le T\le10^5\)butun soni - Testcaselar soni

Har bir testcase uchun n (\(1\le n \le 10^9\)) va k (\(0 \le k \le 10^9\))

Chiquvchi ma'lumotlar:

Har bir testcase uchun masalaga yechim chop eting

Izoh:

1-testcase uchun izoh:
Kasrlar qisqartirilgandan keyingi holatda quyidagicha bo'ladi:
\(\frac{1}{2},\frac{1}{1},\frac{3}{2},\frac{2}{1},\frac{5}{2}\)

va 1 + 1 + 3 + 2 + 5 = 12

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 5 1	12
2	1 4 3	6
3	5 3 8 10 7 10 1 6 7 4 3	5 36 40 14 6

B. Tanos va uning sehrli toshlari

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Bilamiz Tanos Marvel olamidagi eng yovuz qahramonlardan biri. Uni kuchli qilib turadigan narsalar esa sehrli toshlar. Tanos juda ham injiq bo'lgani uchun u toshlari orasidan xohlagan ikkitasini tanlaganda, ularning kuchlari bir biridan 2 martaga farq qilmasligi kerakligi aytdi. Ya'na ham aniqroq qilib aytadigan bo'lsak, Ikki toshning kuchlarini mos ravishda x va y deydigan bo'lsak, x = 2 * y ga teng bo'lmasligi kerak. Endi u sizdan eng kamida nechta toshini olib tashlaganda, uning xohishlari amalga oshishi so'rayapti.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N ( 1 ≤ N ≤ \(10^5\)) - Toshlari soni.

Keyingi qatorda N ta sondan tashkil topgan massiv, (\(a_1, a_2,..., a_N\)). (1 ≤ \(a_i\) ≤\(10^6\)).

Chiquvchi ma'lumotlar:

Chiqish faylining yagona qatorida minimum olib tashlanishi kerak bo'lgan toshlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 2 4 8 9	2

C. Boltavoy va massiv

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Boltavoyda N ta sondan tashkil topgan massiv bor. U massiv ustida quyidagi amallardan xohlagancha ishlatishi mumkin.

Massivning xohlagan x elementini tanlash va shu elementni x / 2 ning pastga yaxlitlanganiga o’zgartirish
Massivning xohlagan x elementini tanlash va shu elementni x – 1 ga tenglash.

Har safar 1 – amalni bajarish uchun k tanga ketadi. 2 – amalni bajarishga esa faqatgina 1 tanga ketadi.
Massivning hamma elementlarini 1 ga tenglash uchun minimum nechta tanga ketishini aniqlang

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N va K butun sonlari ( 1≤N,K ≤\(10^6\))

Keyingi qatorda N ta son massiv elementlari ,\(a_1, a_{2},...., a_n\), (1≤\(a_i\)≤\(10^5\))

Chiquvchi ma'lumotlar:

Chiqish faylining yagona qatorida minimal tangalar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 4 1 3	3

D. Sonlarni o'chirish

Xotira: 512 MB, Vaqt: 1000 ms

Masala

Doskada 1 dan n(toq son) gacha bo'lgan n ta son yozilgan. Sizni esa bir savol o'ylantirib qo'ydi. Doskadagi sonlar orasidan qaysilarini quyidagi amal orqali tanlab olishimiz mumkin:

Sonlar orasidan ketma ket kelgan 3 ta sonni tanlash va shu 3 ta son orasidan eng katta va eng kichigini o'chirish. Bu amal doskada 1 ta son qolguncha bajariladi.

Bu amalni har xil tartibda bajara olganimiz uchun bizda oxirida har doim har xil son qolishi mumkin. Sizning vazifangiz sonlar orasidan qaysilari oxirgi son bo'lishi mumkinligini aniqlash.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T(1≤T≤1000) - Testcaselar soni

Har bir T uchun: birinchi qatorda n soni (1≤n≤100) - doskadagi sonlar soni(n butun son).

ikkinchi qatorda n ta xar hil butun son \(a_1, a_2,...,a_n\)(1≤\(a_i\)≤n) - doskadagi sonlar

Chiquvchi ma'lumotlar:

Har bir T uchun oxirgi son bo'lishi mumkin bo'lgan sonlarni chop eting.

Izoh:

Har bir yechim bo'lishi mumkin bo'lgan elementlarni indexi bo'yicha o'sish tartibida chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 11 11 2 10 3 1 6 8 4 5 7 9	6 8 7 9
2	3 9 1 7 5 8 3 4 6 2 9 9 3 2 6 4 8 1 7 9 5 7 5 2 4 3 1 7 6	5 4 3 4 5 5 4 6
3	2 5 3 4 5 2 1 1 1	3 2 1

E. Ulug'bek uchun challenge

Xotira: 16 MB, Vaqt: 1000 ms

Masala

″Yaxshi yurishni ko'rsangiz, undan ham yaxshirog'ini qidiring.″ - Emanuel Lasker

Hammamiz shaxmat qanday o'ynalishi haqida bilsak kerak. Vengriya (Vengriyaning pul birligi - Forint) davlatida joylashgan bir g'ayrioddiy shaharchada shaxmatni juda ham ko'p odamlar o'ynagani uchun, shaxmat o'ynashni pullik qilib qo'yishdi. Shaxmatist do'stimiz Asadbek esa hozir o'sha mamlakatda.
Asadbek otini (a, b) nuqtadan (c, d) nuqtaga o'tkazish uchun (a * c) + (b * d) forint to'laydi.

Hozirgi kunda 1 Forint = 34.01 so'm. Siz hisoblayotganda 1 forintni 34 so'm deb hisoblang!

U o'z otini biror bir pazitsayadan boshqa bir paziysayaga o'tkazish uchun minimum necha so'm to'lashi kerakligini hisoblab bering.

E'tibor qarating:

Shaxmatning o'lchami 8x8, pastki chap katak indeksi (0, 0).

Ot faqat standart tarzda harakat qiladi, ya'ni 2 qator va 1 ustun yoki 1 qator va 2 ustun.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T\(\le\)100(Testcaselar soni)

Keyigi T ta qatorda a, b, c, d (0\(\le\)a, b, c, d \(\le\)7)

Chiquvchi ma'lumotlar:

Chiqish faylining T ta qatorda Asadbek minimum necha so'm pul to'lashi kerakligi chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 6 3 5 3 6 6 0 2 5 2 5	2686 2516 0