A. G'alati tadbirkor
Xotira: 128 MB, Vaqt: 1000 msYaqinda do'stim Javlonbek katta supermarket ochdi. Javlonbekni yoshligidan qiziq odati bor edi va buni savdoda ham qo'lladi. Savdo qilgan mijozlarga qaytim qaytarishda 100, 1000, 5000 so'mliklari bo'lsa ham faqat 25, 10, 5 va 1 so'mlik puldan beradi. Hohlasa 25 so'mlik, hohlasa 1 so'mlik, hohlasa 10 so'mlik yoki 5 so'mlikdan qaytim qaytarishi mumkin. Sizga qancha qaytarish kerak bo'lsa doim mana shu mayda so'mlardan foydalanadi. Bitta mummo shundaki mijozlar pullar sonini ko'payib ketishini hohlashmaydi. Agar pullar soni \(M\) tadan oshib ketsa hafa bo'lishadi. Javlonbek o'zi dasturchi bo'lgani uchun kombinatorikaga oid algoritmlar qo'llab dastur tuzdi ammo natija olish juda uzoq bo'lgani uchun mijozlar ko'p kutib qolishdi. Mijozlar ko'pligi sababli uzoq hisoblab o'tirmaslik uchun tezroq ishlaydigan dastur yozib berishga sizdan yordam so'radi. Javlonbekka yordam bering.
Birinchi qatorda \(T\) testlar soni beriladi. \((1≤T≤10^5)\)
Keyingi T ta qatorda N qaytarish kerak bo'lgan pul miqdori va M pullar soni beriladi. \((1≤N≤10^6)\), \((1≤M≤4*10^5)\)
Masala yechimga ega bo'lsa alohida qatorlarda har bir puldan necha donadan berishini chop eting aks holda -1 ni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 7 3 16 3 8 3 |
0 0 1 2 0 1 1 1 -1 |
B. ABS
Xotira: 32 MB, Vaqt: 1000 msS satrda Javlonbek A, B va S harflari ketma-ket kelsa juda xursand bo'ladi. Ketma-ket deganda yonma yon bo'lishi shart emas. Masalan \(aldamabsiz\) da yonma yon, \(arabmisiz\) da yonma-yon emas lekin ketma-ketlik bor. Shuning uchun ham xursand bo'ladi. Agar \(asab\) bo'lsa mumkin emas ASB tartib bo'lib qolyapti. Berilgan S satrda minimal ABS bo'ladigan oraliq uzunligini hisoblang.
Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^4)\)
Keyingi T ta qatorda kichik inglzi harflarida S satr beriladi. \((1≤len(S)≤10^4)\)
Masala javobini alohida qatorlarda chop eting. Agar bunday hol mavjud bo'lmasa -1 ni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 aldamabsiz asab arabmisiz |
3 -1 5 |
C. 5
Xotira: 16 MB, Vaqt: 1000 ms\(1\) dan \(N\)-gacha bo'lgan sonlarda raqam sifatida 5 necha marta qatnashganini topish kerak.
Dastlabki qatorda \(T\) butun soni \(T(1≤T≤10^6).\)
Keyingi \(T\) ta qatorda \(N\) butun soni \(N(1≤N≤10^{18}).\)
Har bir so'rov uchun natijalarni yig'indisini chop eting. Natija katta bo'lib ketishi mumkinligi uchun \(10^9+7 \) ga bo'lgandagi qoldiqni chop eting..
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
7 51 88 89 10 7 18 69 |
66 |
| 2 |
9 75 70 68 76 60 26 68 11 71 |
124 |
D. Oraliqdagi yig'indi
Xotira: 128 MB, Vaqt: 1000 msSizga \(A\) massiv va \(N\) ta manfiy bo'lmagan elementlar berilgan. Massiv elementlarini\(K\) va \(M\) (K va M index va ular ham oraliqqa tegishli) oraliqdagi massiv elementlar yig'indisini hisoblang.
Birinchi qatorda massiv elementlar soni \(N\) va so'rovlar soni \(T\) natural sonlar beriladi. \((5≤N≤10^6), (1≤T≤10^5)\)
Ikkinchi qatorda N ta massiv elementlari beriladi. \((0\le a_i \le 10^5)\)
Keyingi qatorda T ta qatorda k va m sonlar beriladi. \((0≤K<M≤10^6-1)\)
Masala javobini alohida qatorlarda chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 5 1 10 100 1000 10000 2 3 0 3 2 4 3 4 0 4 |
1100 1111 11100 11000 11111 |
E. Ajoyib sumka
Xotira: 32 MB, Vaqt: 1000 msSizda N ta taqinchoq bor. Har bir taqinchoqning go'zalligi \(Vᵢ\) va og'irligi \(Wᵢ\) berilgan \((1 ≤ i ≤ N)\). Siz ko'proq taqinchoqni tanlab, sumkaga joylashtirishni rejalashtirganiz. Sumkaning og'irlik chegarasi M ga teng. Ya'ni, sumkadagi taqinchoqlarning og'irligi umumiy hisobda M dan oshmasligi kerak.
Sumkaning "kengligi" (G) quyidagicha hisoblanadi:
- G = (sumka joylashtirilgan taqinchoqlarning go'zalligining eng kichik qiymati) × (sumkaga joylashtirilgan taqinchoqlarning go'zalligining umumiy summasi).
Agar sumkaga hech qanday taqinchoq joylashtirib bo'lmasa, uning kengligi 0 ga teng bo'ladi.
Sizdan talab qilinadigan narsa – sumkaga taqinchoqlarni tanlab, ularning og'irliklari jami M dan oshmasligi sharti bilan, kenglik (G) ning maksimal qiymatini topish.
Birinchi satrda ikkita butun son N va M beriladi:
- N – taqinchoqlar soni \((1 ≤ N ≤ 2*10^4)\).
- M – sumkaning maksimal og'irligi (\((1 ≤ M ≤ 10^5)\).
Keyingi N satrda har bir taqinchoqning go'zalligi va og'irligi beriladi:
- Vᵢ – taqinchoqning go'zalligi \((1 ≤ Vᵢ ≤ 10⁶)\).
- Wᵢ – taqinchoqning og'irligi \((1 ≤ Wᵢ ≤ 10^5)\).
Masala javobini chop eting.
1-testda. 1, 2 va 5 taqinchoqlar tanlansa
11 11
13 3
9 7
lar olinadi. Taqinchoqlarning go'zalligini eng kichik qiymati 9 va umumiy yig'indisi 11+13+9=33 ga teng. Demak 9*33=297 ekan.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 25 11 11 13 3 2 7 1 3 9 7 |
297 |
| 2 |
5 1 100 1000 100 1000 100 1000 100 1000 100 1000 |
0 |
F. Tub sonlar #3
Xotira: 512 MB, Vaqt: 1200 ms\(p_0<p_1<p_2<⋯\) tub sonlar bo'lsin. Ya'ni \(p_0=2, p_1=3, p_2=5\) va hokazo. Sizga butun sonlar berilgan N, A va B. Shunday X va Y sonini toping va chop eting. Bu yerda X \(N\) gacha mavjud tub sonlar soni, Y esa shu tub sonlar orasida \(p_{A_y+B} \le N\) shartni qanoatlantiradigan tub sonlar soni. Bunda \(y\) manfiy bo'lmagan butun sonlar.
Bir qatorda Natural N, A va B sonlar beriladi. \(1≤N≤5×10^8\), \(0≤B<A≤N\)
Birinchi qatorda X va Y chop eting.
Ikkinchi qatorda \(p_{A_y+B} \le N\) shartni qanoatlantiradigan tub sonlar o'sish tartibida chop eting.
Izoh: 1-testda.
100 gacha 25 ta tub son mavjud. Shulardan 8 tasi \(p_{A_y+B} \le N\) shartga to''gri keladi.
- \(i=0: p_{3⋅0+1}=p_1=3\)
- \(i=1: p_{3⋅1+1}=p_4=11\)
- \(i=2: p_{3⋅2+1}=p_7=19\)
- \(i=3: p_{3⋅3+1}=p_{10}=31\)
- \(i=4: p_{3⋅4+1}=p_{13}=43\)
- \(i=5: p_{3⋅5+1}=p_{16}=59\)
- \(i=6: p_{3⋅6+1}=p_{19}=71\)
- \(i=7: p_{3⋅7+1}=p_{22}=83\)
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
100 3 1 |
25 8 3 11 19 31 43 59 71 83 |