A. GCD va LCM
Xotira: 32 MB, Vaqt: 1000 msJavlonbek bugun darsda EKUB va EKUK mavzusini tushunib oldi. Bilimini sinash uchun sizga ikkita butun son M va N berdi. Sizning vazifangiz shunday ikkita butun son A va B ni topishdan iboratki, quyidagi shartlar bajarilsin:
- EKUB(A, B) = M
- EKUK(A, B) = N
- A + B qiymati minimal bo‘lishi lozim.
- Agar bunday A va B mavjud bo‘lmasa, -1 -1 chiqarilsin.
Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)
Keyingi T ta qatorda ikkita butun son A va B beriladi. \((1≤A,B≤10^{12})\)
Masala javobini chop eting.
1-test. CGD=2 LCM=30 da
A=2, B=30
A=6, B=10
sonlari qanoatlantiradi. Yig'indisi minimal degani uchun 6 va 10 ni olamiz.
GCD=6, LCM=9 da bunday sonlar mavjud emas. Shuning uchun -1 -1
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 2 30 6 9 |
6 10 -1 -1 |
| 2 |
17 82 1230 94 9212 25 1775 51 3621 97 1649 79 5846 7 154 84 6468 23 1449 19 1767 35 2765 43 688 17 170 76 228 28 308 18 972 80 1280 |
246 410 188 4606 25 1775 51 3621 97 1649 158 2923 14 77 588 924 161 207 57 589 35 2765 43 688 34 85 76 228 28 308 36 486 80 1280 |
B. TOQ yoki JUFT
Xotira: 32 MB, Vaqt: 1000 msA va B natural sonlar beriladi. Agar A va B ning umumiy bo‘luvchilar soni juft yoki toq ekanligini aniqlashingiz kerak.
Birinchi qatorda T testlar soni beriladi. \((1≤T≤10^5)\)
Keyingi T ta qatorda A va B sonlar beriladi. \((1≤A,B≤10^9)\)
Agar A va B ning umumiy bo'luvchilar soni juft bo'lsa “JUFT”, aks holda “TOQ” so'zlarini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 456 54 70 103 878 793 692 354 |
JUFT TOQ TOQ JUFT |
| 2 |
3 268 432 674 504 783 767 |
TOQ JUFT TOQ |
C. Almashtirishlar soni
Xotira: 256 MB, Vaqt: 1000 msImona matnni tahrirlashni yaxshi ko‘radi, ayniqsa, 110 ketma-ketliklarini 011 ga almashtirish bilan shug‘ullanishni yoqtiradi.
Imonaga akasi Javlonbek 0 va 1 dan iborat satr S berdi. S satrida 110 bo‘lakchasini 011 ga almashtirishni hohlaganicha bajara olishini aytdi. Imonaning vazifasi bu amalni qo'llab bo'lmas holiga kelguncha maksimal necha marta almashtirish bajara olishini hisoblash edi. Ammo sanashda adashib ketdi. Siz unga yordam bering.
Bir qatorda 0 va 1 lardan iborat S satr beriladi. \((1 ≤ len(S) ≤ 5 × 10^7)\)
Masala javobini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
0111000 |
3 |
| 2 |
110010111101001 |
12 |
D. Ikkita musbat butun son
Xotira: 32 MB, Vaqt: 1000 msImona kompyuterda Word dasturida ikkita 0 dan farqli musbat butun son \(A\) va \(B\) ni yozmoqchi bo'ldi. Sonlarni ajratib yozishni bilmasa edi. Ya'ni probel tugmasini hali bilmas edi. Shuning uchun sonlar orasidagi bo‘sh joy yo‘qligi uchun ular bitta butun son \(C\) sifatida yozilib qoldi. Imonani akasi Javlonbek \(C\)son qaysi \(A\) va \(B\) son ekanlini topaman deb topolmadi. Siz Javlonbekka yordam bering.
Musbat butun son \(C\) beriladi. \((10<C<10^{50})\)
\(C\) ni ikkita musbat butun son \(A\) va \(B\) sonlar sifatida ajratishning nechta mumkin bo‘lgan usulini chop eting.
1-testda.
1234 ni 1 va 234, 12 va 34, 123 va 4 kabi 3 xil yozish mumkin.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 1234 123 |
3 2 |
| 2 |
2 339 969 |
2 2 |
E. Qism yig'indilar umumiy yig'indisi
Xotira: 512 MB, Vaqt: 1000 msN ta elementdan iborat butun sonlar massivi \(A_1,A_2,…,A_N\)beriladi. Har qanday juftlik \((l,r)\) uchun quyidagi yig‘indini aniqlang:
\(S(l, r) = A_l + A_{l+1} + \dots + A_r\)
Barcha mumkin bo‘lgan \(S(l,r)\) qiymatlarining umumiy yig‘indisini hisoblang.
Birinchi qatorda N musbat butun son massiv elementlarining soni beriladi. \((1≤N≤5×10^6)\)
Ikkinchi qatorda N ta butun son massiv elementlari beriladi. \(A_1, A_2, \dots, A_N\)\((-10^6≤A_i≤10^6)\)
Barcha mumkin bo‘lgan \(S(l,r)\)yig‘indilarining umumiy yig‘indisini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 3 4 5 |
40 |
| 2 |
5 2 12 7 0 15 |
244 |
F. Kvadrat ildiz
Xotira: 32 MB, Vaqt: 1000 msBizga \(n\) soni beriladi. \(\sqrt{n}=a\sqrt{b}\) ekanligidan foydalanib \(a\) va \(b\) sonlarni topish dasturi tuzilsin.
\(n\) natural son beriladi. \((1≤n≤10^{18})\)
\(a\) va \(b\) sonlar topish kerak. Agar bunday qiymatlar ko'p bo'lsa, \(b\) ni eng kichik holini chop eting.
1-testda. \(24=2\sqrt{6}\) bunda a=2 va b=6
2-testda. \(16=4\sqrt{1}\) bunda a=4 va b=1
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
24 |
2 6 |
| 2 |
16 |
4 1 |
| 3 |
7 |
1 7 |
G. O'suvchi balandliklar
Xotira: 512 MB, Vaqt: 1000 msSizga N ta daraxtlarning balandligi berilgan. Siz ushbu daraxtlarni joyini o'zgartirolmaysiz (siljitolmaysiz), faqat ularning balandliklarini butun sonlar ichida o'zgartirishingiz mumkin. Sizning vazifangiz — barcha daraxtlar balandliklarini o'suvchi tartibda joylashishiqni ta’minlash va buning uchun sarflanadigan minimal umumiy masofani topish. Ya'ni A balandlik qiymati B ga o'zgartirgan bo'lsak masofa \(|A-B|\) ga teng bo'ladi
Birinchi qatorda daraxtlar balandliklari N natural son beriladi. \((1≤N≤10^6)\)
Ikkinchi qatorda N ta butun son \(Y_1, Y_2, ..., Y_N\) — daraxtlarning balandliklari beriladi. \((0≤Y_i≤10^5)\)
Masala javobini chop eting.
1-testda.
6
1 2 0 8 6 9 ketma-ketlikni 1 2 2 6 6 9 kabi almashtirsak o'suvchi bo'ladi. Demak \(|0-2|+|8-6|=2+2=4 \)ekan. 1 2 3 5 6 9 qilsak ham bo'ladi ammo bu minimal emas. \(|0-3|+|8-5|=3+3=6\) ga teng bo'lib qoladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
6 1 2 0 8 6 9 |
4 |
| 2 |
10 3 14 15 92 65 35 89 79 32 38 |
155 |
H. Raqamlar yig'indisi #4
Xotira: 256 MB, Vaqt: 1000 msBerilgan musbat butun sonlar orasida, raqamlar yig‘indisi N dan kichik yoki teng bo'lgan K-chi eng kichik musbat butun sonni toping.
Bitta qatorda N va K butun sonlar beriladi. \((1\le N,K \le 10^{18})\)
Raqamlar yig‘indisi N dan kichik yoki teng bo‘lgan K-chi eng kichik musbat butun sonni chop eting.
1-testda.
1, 2, 3, 10, 11, 12, 20, 21, 30, 100, 101, … Shuning uchun, 10-chi eng kichik son 100 ga teng.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 10 |
100 |
| 2 |
33 1000000000000000000 |
1020002210002200600501111300120 |
| 3 |
2 30 |
1000010 |