A. Common Divisors of Two Numbers
Xotira: 32 MB, Vaqt: 2000 msGiven two integer numbers, the task is to find count of all common divisors of given numbers?
Numbers A and B are entered
Print the answer
Naive Solution
A simple solution is to first find all divisors of first number and store them in an array or hash. Then find common divisors of second number and store them. Finally print common elements of two stored arrays or hash. The key is that the magnitude of powers of prime factors of a divisor should be equal to the minimum power of two prime factors of a and b.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
13 99 |
1 |
| 2 |
20 36 |
3 |
| 3 |
3 17 |
1 |
B. Massiv tengligi
Xotira: 16 MB, Vaqt: 1000 msSizga N ta sondan tashkil topgan A massivi berilgan. Siz massiv ustida quyidagi amalni cheksiz marotaba bajarishingiz mumkin.
- A massiv orasidan K ta ketma-ket kelgan sonlarni tanlang va ularni hammasini shu ketma-ketlikning minimum soniga tenglang.
Topshiriq esa massivni minimal amallar orqali hamma elementlarini bir-biriga tenglashdir.
Kirish faylining birinchi qatorida T (1 ≤ T < \(10^5\))
Har bir T uchun birinchi qatorida N va K butun sonlari (1 ≤ K≤ N ≤ \(10^5\)) N - massiv elementlari soni va K - ketma-ketlik uzunligi. T ta N ning umumiy yig'indisi ≤\(10^6\)..
Har bir T uchun ikkinchi qatorida N ta sondan tashkil topgan A massivi, \(a_1, a_2,...,a_N\), (1 ≤ \(a_i\) ≤ \(10^5\)) - massiv elementlari.
Agar tenglashni iloji bo'lsa minimal amallar sonini, agarda iloji bo'lmasa -1 chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 11 4 1 16 20 7 1 9 3 16 17 16 13 11 5 17 15 11 1 8 20 14 9 18 11 4 8 2 15 2 11 16 6 18 3 16 |
3 3 7 |
| 2 |
1 5 2 2 4 10 15 1 |
4 |
| 3 |
4 10 3 16 10 2 15 5 7 7 16 10 11 4 3 20 4 18 1 9 5 12 5 14 16 14 16 10 4 4 6 3 13 19 4 8 3 16 |
5 2 2 3 |
C. Shifr
Xotira: 16 MB, Vaqt: 1000 msTizim mustahkamligini ta'minlash maqsadida tizimda yangi shifrlash algoritmi ishlab chiqildi.
Unda 4 ta \(A, B, C, D\) belgilar qatnashishi mumkin. Faqat bunda bir nechta shartlar mavjud:
- Ikkita bir xil belgi yonma-yon bo'lmasligi kerak.
- \(A\) va \(D\) belgilari yonma-yon bo'la olmaydi.
- B va C belgilar yonma-yon bo'la olmaydi.
- BAC yoki CAB ko'rinishidagi qism satr ham mavjud bo'lmasligi kerak.
- Simmetrik shifrlar bir xil shifrlar deb hisoblanadi. Ya'ni ABC vs CBA bitta shifr hisoblanadi.
Sizning vazifangiz \([L, R]\) uzunlikda nechta yuqoridagi shifrlarni qanoatlantiruvchi shifrlar mavjudligini aniqlash.
Kirish faylida 2 ta natural son \(L, R\) beriladi. \(L, R \le 10^9\)
Chiqish faylida masala javobini \(1000000007\) ga bo'lgandagi qoldiqni chop eting.
1-test:
Uzunligi 3 bo'lgan shifrlar:
BAB, BDB, BDC, CAC, CDC, ABA, ABD, ACA, ACD, DBD, DCD
Uzunligi 4 bo'lgan shifrlar:
BABA, BABD, BDBA, BDBD, BDCA, BDCD, CACA, CACD, CDBA, CDBD, CDCA, CDCD
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 4 |
23 |
| 2 |
5 6 |
64 |
| 3 |
3 3 |
11 |
D. Ketma-ketlik
Xotira: 16 MB, Vaqt: 1000 msSizga quyidagi ketma-ketlik berilgan:
3, 4, 7, 10, 16, 21, 30, ...
Ketma-ketlikning \(n\)-hadini toping.
Kirish faylining yagona satrida butun son \(n (1≤n≤50)\) ni kiriting.
Chiqish faylida so'ralgan javobni chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 |
3 |
| 2 |
30 |
832153 |
E. A+B
Xotira: 32 MB, Vaqt: 1000 ms2 sonning yi'g'indisi chop eting.
a va b bir qatorda kiritiladi
Masala javobini chop eting
Buni hamma yechishi kerak
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 3 |
5 |
| 2 |
0 0 |
0 |
F. Do'st elflar
Xotira: 128 MB, Vaqt: 1500 msShimoliy qutbda so'nggi yillarda dasturlashga e'tibor ancha kuchayib qoldi. Bu yili Qorbobo dasturchi elflarni bir joyga yig'ish maqsadida ular uchun ofis qurdirdi.
Dasturchi elflar oldindan alohida-alohida ishlagani uchun hech qaysi dasturchi elf bir-birini tanimaydi. Qorbobo esa jamoada hamma bir-birini tanishi muhim deb hisoblaydi. Shuning uchun u dasturchi elflarning ofisiga har kuni kelib ularni kuzata boshladi. U kuzatuvlarini yon daftariga quyidagicha yozib boradi.
- \(!\space a \space b\) - a va b elfni birga yurganini ko'rsa shu ko'rinishda belgilab qo'yadi va ularni do'stlashgan deb hisoblaydi. Bu yerda a va b natural sonlardir, chunki Qorbobo elflarini raqamlab chiqqan (Kim ham minglab elf ismlarini eslab qolardi).
- \(?\space a \space b\) - Qorbobo a va b elf do'stlashganmi deb o'ylab qolganda shu ko'rinishda belgilab qo'yadi. Bunda a elf b elf bilan va b elf c elf bilan do'st bo'lsa a elf c elf bilan ham do'st hisoblanadi (ya'ni do'stimning do'sti mening ham do'stim).
Siz Qorboboning yon daftaridagi har bir so'rovga javob bering. \(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st yoki do'st emasligini aniqlang.
Brinchi qatorda N va Q sonlari \((1<N\leq 2*10^5; 1\leq Q \leq 2*10^5)\), mos ravishda dasturchi elflar soni va Qorboboning yon daftaridagi so'rovlar soni. Keyingi Q ta qatorda so'rovlar:
\(!\space a \space b\) yoki \(?\space a \space b\) ko'rinishida \((a \not= b)\), kamida bitta \(?\space a \space b\) ko'rinishida so'rov borligi kafolatlanadi.
\(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st bo'lsa 1 aks holda 0 chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 5 ! 1 2 ! 3 4 ! 2 4 ? 1 3 ? 3 5 |
1 0 |
| 2 |
5 3 ? 1 2 ! 1 2 ? 1 2 |
0 1 |
G. Shaxzodning yangi yil sovg'asi
Xotira: 128 MB, Vaqt: 1000 msQorbobo Shaxzodga Yangi yilda yangi MacBook PRO 14 sovg'a qildi. Endi Shaxzod eski MacBookidagi hamma ma'lumotlarini yangisiga ko'chirishi kerak. Buning uchun u qo'shimcha SSD diskidan foydalanmoqchi. Lekin diskga uning hamma ma'lumotlari sig'mas ekan. Azimjonning hisob-kitobiga ko'ra Shaxzod ma'lumotlarini 2 martada o'tkaza olar ekan. Buning uchun u papkalarining o'lchamini iloji boricha bir-biriga yaqin qilib 2 ga ajratishi kerak. Bu ishni Azimjon osongina bajara oldi, siz ham urinib ko'ring ;)
Shaxzodning eski MacBookida hamma papkalari 0 dan boshlab raqamlab chiqilgan. 0 papka root hisoblanadi, ya'ni barcha fayl va boshqa papkalar 0 papkada joylashgan. 2 qismga ajratayotganda faqat 1 ta papkani 1 marta ko'chirish mumkin, ko'chirishda papkaning ichidagi barcha fayllar va papkalar birgalikda ko'chadi. Fayllarni ko'chirish yoki bir nechta papkani ko'chirish ma'lumotlar chalkashib ketishiga olib keladi.
N natural soni va ikkinchi qatorda N ta butun sondan iborat A massiv beriladi. A massivning i-elementi i-papka qaysi papkaning ichida turganligini bildiradi, 0 papka uchun bu qiymat har doim -1 ga teng.
Keyingi N ta qatorning har birida \(K_j\) soni va \(K_j\) ta nomanfiy butun son, mos ravishda j-papkadagi fayllar soni va fayl o'lchamlari beriladi. Fayl o'lchamlari \(10^9\) dan oshmaydi.
\(0<N\leq10^4; \space 0\leq K_j \leq 100; \space 0\leq j <N.\)
Ma'lumotlarni ajratganda hosil bo'ladigan eng kichik farqni toping.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 -1 0 0 0 1 13 2 3 10 |
0 |
| 2 |
3 -1 0 0 1 1 1 13 2 3 10 |
1 |
H. Eeeelffff
Xotira: 512 MB, Vaqt: 2000 msQorboboda sovg'a ulashishi kerak bo'lgan N ta bolaning ro'yxati bor edi. Qorbobo bu ro'yxatni ko'zdan kechirar ekan ro'yxat N o'lchamdagi P permutatsiya ekanligini tushunib qoldi. Qorbobo sovg'alarni ro'yxatdagi tartibda ulashishga qaror qildi va permutatsiyani yordamchi elfga saqlash uchun berdi.
Elf bekorchi vaqtida P permutatsiyadan foydalanib A massivini yasadi. Har bir \(A_i\) \((1\leq i \leq N)\) ning qiymati \(i\) son uchun P permutatsiyada \(i\) sondan o'ng tarafdagi o'zidan katta eng yaqin sonning qiymatini, agar bunday son mavjud bo'lmasa -1 qiymatni saqlaydi. Yaxshiroq tushunish uchun izohga qarang!
Lekin elf A massivni yasash uchun P permutatsiyani bo'yab tashladi. Endi u Qorbobodan gap eshitmasligi uchun permutatsiyani qayta tiklashi kerak. Elfga yordam bera olasizmi ?
Birinchi qatorda N \((1 \leq N \leq 2*10^{5})\) natural son kiritiladi.
Ikkinchi qatorda N ta sondan iborat A massiv kiritiladi.
N uzunlikdagi P permutatsiyani chiqaring.
P={2,3,1}
1 soni uchun o'zidan o'ng tarafda 1 dan katta son yo'q, demak \(A_1=-1;\)
2 soni uchun o'zidan o'ng tarafda 2 dan katta 3 soni mavjud, demak \(A_2=3;\)
3 soni uchun o'zidan o'ng tarafda 3 dan katta son yo'q, demak \(A_3=-1.\)
A={-1,3,-1}.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 -1 3 -1 |
2 3 1 |
| 2 |
3 3 -1 -1 |
1 3 2 |
I. Shimoliy city
Xotira: 256 MB, Vaqt: 4000 msQuruvchi elflar va nihoyat Shimoliy citydagi barcha binolarni qurib bitkazishdi, endigi vazifa esa bu binolarni yo'llar orqali bog'lab chiqish. Qiyin tarafi esa yo'llarni Yangi yil bayramigacha bitkazish kerak, chunki Shimoliy qutbda asosiy bayramlarni yangi Shimoliy cityda o'tkazish rejalashtirilgan. Yo'llarni iloji boricha tez bitirish uchun esa hamma binolarni birlashtiruvchi eng qisqa yo'lni topish kerak.
Sizga \(N\) natural soni va keyingi \(N\) ta qatorda \(X_i\), \(Y_i\) sonlari beriladi. \(X_i\), \(Y_i\) bu i-binoning joylashgan koordinatalari. Binolar 1 dan N gacha raqamlangan.
\(1\leq N \leq 1000;\) \(-10^9 \leq X_i, Y_i \leq 10^9, \space i=\{1...N\}.\)
Quruvchi elflarga eng qisqa yo'l uchun qaysi binolar o'rtasida yo'llar qurish kerakligini yozib bering. O'rtasida yo'l qurilishi kerak bo'lgan bino juftliklari sonini va keyingi qatorlarda juftliklarni probel bilan ajratgan holda alohida qatorlarda chop eting.
Agar bir necha xil javob mavjud bo'lsa, istalganini chop eting.
Siz bergan javob va muallif javobidagi yo'l uzunliklari farqi \(10^{-6}\) dan katta bo'lganda javobingiz noto'g'ri deb hisoblanadi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 0 0 0 4 4 0 2 2 4 4 |
4 1 4 2 4 3 4 4 5 |
| 2 |
9 -10 5 -3 6 8 6 -4 1 4 2 0 0 -5 -8 2 -8 7 -9 |
8 4 6 5 6 2 4 8 9 3 5 7 8 1 2 6 8 |
J. Shpion Azimjon
Xotira: 16 MB, Vaqt: 1000 msDasturchilar Klubi a'zosi Azimjon shu kunlarda shubhali harakatlar qilmoqda. Maqsud Azimjondan Klubning qilayotgan ishlari haqida boshqa raqiblarga ma'lumot yetkazib berayotgani borasida shubhalanib qoldi, va Maqsudning qo'liga Azimjon tomonidan yozilgan maktub tushib qoldi. Ammo maktub uddaburonlik bilan shifrlangan bo'lib uni o'qish mushkul edi. Azimjon maktubni DK algoritmi yordamida shifrlagan edi.
DK algoritmida har bir harf (belgilar hisob emas) ASCII jadvali boyicha bitta oldingi va bitta keyingi harflar birlashmasiga o'zgaradi va har bir o'zgargan so'z teskarisiga yoziladi. Azimjon Lotin alifbosidagi z va Z harflaridan so'ng yana mos ravishta a va A harflari bor deb hisoblagan, Huddi shu holat teskarisiga ham amal qiladi - a va A harflaridan oldin z va Z harflar bor deb hisonlanadi.
Maqsudga Azimjonning "Shpionlik" xatini o'qishda yordam bering.
Bitta qatorda katta va kichik lotin alifbosi harflari yordamida yozilgan uzunligi 100 ta belgidan oshmaydigan shifrlangan matn.
Bitta qatorda Maqsudning deshifrlagan matnini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
Fazliddin Yaxshi Bola |
mohjcecehjkmaazzEG hjgirtwyzzXZ zzkmnpAC |
| 2 |
Dasturchilar juda ham erinchoq bolishadi |
qszzkmhjgibdqstvsurtzzCE zzcetvik lnzzgi prnpgibdmohjqsdf hjcezzgirthjkmnpac |
K. Sub satrlar yig'indisi #1
Xotira: 16 MB, Vaqt: 1000 msSizga \(s\) satr berilgan bo'lib, sizning vazifangiz satrni barcha turli xil(bir biridan farqli) quyi satrlari uzunliklari yig'indisini aniqlashingiz kerak bo'ladi.
Misol: \(s = "BOBR"\) satr uchun barcha turli xil sub satrlar \(B\), \(O\), \(R\), \(BO\), \(OB\), \(BR\), \(BOB\), \(OBR\), \(BOBR\). Bu sub satrlar uzunliklari yig'indisi \(19\) ga teng.
Kirish fayilida lotin alfbosining katta harflaridan tashkil topgan \(s(1\leq |s|\leq 100)\) satr berilgan.
Chiqish fayilida barcha turli xil sub satrlar uzunliklari yig'indisini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
BOBR |
19 |
| 2 |
ROBOCONTEST |
283 |
L. "Juda qo'rqinchli" ko'paytma
Xotira: 64 MB, Vaqt: 1000 msMAXAB va MINAB topshiriqlarini hal qilgandan so'ng, Sardor Azimjonga yanada qiyin topshiriq berish haqida o'ylab qoldi va quyidagi topshiriqni berishga qaror qildi.
\(N\) ta butun sondan iborat massiv berilgan. Bu massiv elementlarini ko'paytmasi qandaydir butun sonning kvadrati bo'la oladimi yoki yo'qligini tekshirish talab etiladi.
Azimjon bu topshiriqni hal qilishni uddalay olmadi. Sizchi buni hal qila olasizmi 😉?
Birinchi qatorda sizga \(N\) natural soni beriladi.
Keyingi qatorda \(N\) ta butun son \(A\) massiv elementlari beriladi.
\(N ≤ 2*10^5 , |A_i|≤10^6\)
Agar massiv elementlari masala shartini qanoatlantirsa "Yes", aks holda "No" so'zini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 1 2 3 4 6 |
Yes |
M. Ajoyib oraliq
Xotira: 16 MB, Vaqt: 1000 msN natural soni berilgan. 1 dan N gacha bo'lgan sonlar ichida armstrong sonlarini i- va j- nchi o'rindagilari uchun sizdan EKUK / EKUB ni topish talab etiladi.
Armstrong sonlari deb, shu sonning raqamlarini sonning uzunligiga teng darajaga ko'tarib yig'indisini hisoblaganimizda o'ziga teng bo'lgan sonlarga aytiladi. Masalan, 153 = 13 + 53 + 33 = 1 + 125 + 27 = 153.
Birinchi qatorda N butun soni (1 ≤ N ≤ 109) kiritiladi.
Ikkinchi qatorda i < j shartni qanoatlantiruvchi i va j sonlari (1 ≤ i, j ≤ 31) beriladi.
Masala shartida so'ralgan natijani 10-3 aniqlikda chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 1 2 |
2.000 |
| 2 |
5 2 5 |
10.000 |
N. Bayram stoli
Xotira: 16 MB, Vaqt: 1000 msBitvoy do'stlari bilan bayram uyushtirmoqchi. Ammo u do'stlari uchun to'g'ri to'rtburchak shaklidagi stol buyurtma qilmoqchi. U juda sahiy. Shuning uchun iloji boricha ko'proq mehmon o'tirishi mumkin bo'lgan stol buyurtma qilmoqchi. Bunda stol sig'imi uning perimetri bilan bir xil. Bitvoy eng ko'pi bilan necha nafar do'stini taklif qilishi mumkinligi aniqlang. Stolda o'zi ham o'tirishi kerak.
Kirish faylida birinchi qatorda Bitvoyning uyini o'lchamlari kiritiladi. N, M\((1\le N, M \le 400)\).
Keyingi N qatorda Bitvoy uyining xaritasi M tadan belgi, bunda X -> bu joy allaqachon band, nuqta(.) -> bo'sh joyni anglatadi.
Chiqish faylida Bitvoy nechta do'stini chaqirishi mumkin ekanligini chop eting.
1-testda:
Demak eng ko'pi bilan 2x2 o'lchamli stol buyurtma qilishi mumkin.
P = 2 * (1 + 1) = 4
O'zi ham borligi uchun 4 - 1=3.
2-testda:
Demak eng ko'pi bilan 10x4 o'lchamli stol buyurtma qilishi mumkin.
P = 2 * (4 + 10) = 28
O'zi ham borligi uchun 28 - 1=27.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 1 . |
3 |
| 2 |
10 10 ....X..... X......... .......... .......... .......... .......... .......X.. .......... ..X....... ...X...... |
27 |