A. Begona o'simlik

Xotira: 1024 MB, Vaqt: 1000 ms

Masala

Javlonbek ekin dalalardan begona o'simlikdan tozalash uchun dorilardan foydalanadi. Javlonbek \(N\) ta yer maydoniga ega va har bir yerni begona o'simliklardan tozalash uchun ma'lum miqdorda dori talab qilinadi. Javlonbekda jami \(K\) dona dori bilan eng ko'p yerni tozalashga harakat qiladi. Javlonbek eng ko'p nechta yer maydonini begona o'simliklardan tozalashi mumkinligini hamda yer maydoni tozalangandan so'ng ortib qoladigan dorilar sonining maksimal qiymatini topmoqchi. Siz unga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son N va K (yerni soni va dorilar soni) beriladi. \((1≤N≤4×10^6)\), \((1≤K≤10^9)\)

Ikkinchi qatorda N ta har bir dalaga kerak bo'ladigan dorilar soni beriladi. \((1≤A_i≤10^9)\)

Chiquvchi ma'lumotlar:

Yagona qatorda eng ko'p begona osimlik'lardan tozalash mumkin bo'lgan yerlar soni va ortib qoladigan dorilar sonining maksimal qiymati chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 11 4 1 2 6 3	4 1
2	2 4 3 2	1 2

B. Tenglashtirish

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Javlonbek ukasi Ismoilga shunday vazifa berdi. 1 dan N gacha bo'lgan sonlarni ikkita guruhga shunday ajratish kerakki, ikkala guruhdagi sonlar yig'indisi teng bo'lsin. Ismoil 1 dan \(N\) gacha sonlarni har xil kombinatsiyalarni, guruhlashlarni hamda tanlash usullarini qo'llab ham masalani hal qilish algoritmni topolmadi. Birinchi guruhdagi sonlar 0 va ikkinchi guruhdagi sonlarni 1 deb hisoblasak, ikkiga bo'lingan sonlar ko'rinishi qanday bo'lishini hisoblashga yordam bering. Agar ikkinchi guruh sonini birinchi guruhga o'tkazsak 1 raqamida turaversin.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1 ≤ T ≤ 10^3)\)

Keyingi T qatorda N soni beriladi. \((1 ≤ N ≤ 10^5)\)

Chiquvchi ma'lumotlar:

Agar taqsimlash mumkin bo'lsa, birinchi guruhda iloji boricha kichik sonlar joylashsin va \(N\) uzunlikdagi satrni chop eting aks holda -1 ni chop eting.

Bunda. 0 sonni birinchi guruhga tegishli ekanligini, 1 sonni esa ikkinchi guruhga tegishli ekanligini bildiradi.

Izoh:

1-testda
1 ni hosil qilb bo'lmaydi.

3 ni 1+2 va 3 kabi yozish mumkin. Demak 001 ekan.

8 ni 1+2+4+5+6 va 3+7+8 kabi yozish mumkin. Demal 00100011 ekan.
Masalan: 8 da 5+6+7 va 1+2+3+4+8 kabi joylashtirish ham mumkin, ammo bundan birinchi guruhdagi sonlar katta bo'lib ketadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 3 8	-1 001 00100011

C. Yangi son

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Musbat butun son N beriladi. Sizning vazifangiz N ning boshiga, oxiriga yoki raqamlar orasiga bitta raqam qo'shish orqali nechta yangi son hosil qilish mumkinligini aniqlashdir.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son N beriladi. \((1≤N≤10^{1000000})\)

Chiquvchi ma'lumotlar:

Jami necha xil turli son hosil qilish mumkinligini chop eting.

Izoh:

1-testda
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 31, 41, 51, 61, 71, 81, 91 jami 18 ta mumkin.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1	18

D. Qoldiq (MOD) #2

Xotira: 32 MB, Vaqt: 1000 ms

Masala

\(10^{N}-1\) ni \(10^{M}+1\) ga bo‘lgandagi qoldiqni toping. Javob juda katta bo‘lishi mumkinligi sababli, natijani \(10^9+7\) ga bo‘lgandagi qoldiq topilsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)

Keyingi T ta qotorda N va M natural sonlar beriladi. \((1≤N,M≤10^9)\)

Chiquvchi ma'lumotlar:

Masala javobini alohida qatorlarda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 1 8 3 33 4	0 99 9

E. Qoldiq (MOD) #3

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Qandaydir \(X\) sonini \(A\) natural songa bo'lganda qoldiq \(a\) hamda shu \(X\) sonni \(B\) natural songa bo'lganda qoldiq \(b\) bo'ladigan\(X\) ning eng kichik butun son qiymatini toping.

Kiruvchi ma'lumotlar:

Bir qatorda A, B, a va b natural sonlar beriladi. \((1≤A,B≤10^{18})\), \((0≤a≤A)\), \((0≤b≤B)\)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Izoh:

Natija aniq yechim bo'lishi kafolatlangan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 5 1 2	7

F. Qo'shni sonlar

Xotira: 64 MB, Vaqt: 1000 ms

Masala

N sonini faqat ikkita qo‘shni butun sonlardan iborat bo‘lgan sonlar yig‘indisi sifatida ifodalashning mumkin bo‘lgan usullarining sonini toping. Bunda mavjud sonlar kombinatsiyasi bitta deb hisoblanadi. Masalan (1,2,2,2) bo'lsa, (2,1,2,2) yoki (2,2,2,1) lar bitta deb hisoblanadi. Ya'ni to'plamda qo'shni sonlar soni bir xil ammo joylashuvi har xil bo'lsa 1 ta deb hisoblaymiz.

Kiruvchi ma'lumotlar:

N natural son berialdi. \((1≤N≤10^{15})\)

Chiquvchi ma'lumotlar:

Masala javobini chop ering.

Izoh:

1-testda.

\((1,1,1,1,1,1,2)\), \((1,1,1,1,2,2)\), \((1,1,2,2,2)\), \((2,3,3)\) lar mumkin jami 4 ta.
\((1,1,1,2,3)\) mumkin emas. Sababi 1 va 3 qo'shni emas.

Misollar:

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