A. 1 ga tenglash
Xotira: 32 MB, Vaqt: 1000 msN natural son berilgan. K = N bo'lib K ni K = 1 ga tenglash lozim. Buning uchun quyidagi amallardan foydalanishingiz mumkin:
- K ni \(\frac{K}{ 2^M}\) ga o'zgartirish, bunda M ixtiyoriy musbat butun son bo'lib, \(\frac{K}{ 2^M}\) butun son bo'ladi. Bu operatsiyani faqat K ni 2 ga bo'linishi mumkin bo'lgan holatlarda amalga oshirish mumkin.
- K ni \(K*M + 1\) ga o'zgartirish, bunda m musbat butun son bo'ladi.
Birinchi qatorda T testlar soni berialdi. \((1≤T≤10^5)\)
Keyingi T ta qatorda N natural son beriladi. \((2 ≤ N ≤ 10^{18})\)
K=1 ga erishish uchun eng kam operatsiya soni alohida qatorlarda chop eting.
1-testda
K=4 da
1-qadamda \(\frac{K}{ 2^M}\) qo'llab \(\frac{4}{ 2^2}=1\) qila olamiz 1 qadamda. Demak 1 urunishda erishamiz.
K=3 da
1-qadamda \(K*M+1\) qo'llab \(3*1+1=4\) qilamiz.
2-qadamda \(\frac{K}{ 2^M}\) qo'llab \(\frac{4}{ 2^2}=1\) qila olamiz. Demak 2 urunishda erishamiz.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 4 3 6 |
1 2 3 |
B. Oxirgi son
Xotira: 32 MB, Vaqt: 1000 msDoskada dastlab N musbat butun son yozilgan. Siz quyidagi amalni doskadagi son 0 hosil bo'lguncha bajarishingiz kerak:
- Doskada yozilgan son x uchun d(x) ni hisoblang. d(x) bu x ning musbat bo‘luvchilar sonidir.
- Doskadagi sonni x−d(x) ga almashtiring.
Ushbu amalni doskadagi son 0 hosil bo'lguncha takrorlang. Amalni bajarish jarayoni doskadagi son 0 bo'lganida to'xtaydi. Doskadagi son 0 bo'lishidan oldin yozilgan oxirgi sonni toping.
Birinchi qatorda T testlar soni beriladi. \((1\le T\le10^5)\)
Keyingi T ta qatorda ikkita musbat butun son N soni kiritiladi: \((1 ≤ N ≤ 10^{18})\)
Masalani javobini alohida qatorlarda chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 6 12 |
2 2 |
C. Ikkilikda almashtirish #3
Xotira: 32 MB, Vaqt: 1000 ms10 lik sanoq sistemasida N soni beriladi. Siz shunday K sonni topishingiz kerak:
- K son 10 likdan ikkilikka o'tkaziladi;
- hosil bo'lgan sonni birinchi raqamidan boshqa barcha raqamlar 1 bo'lsa 0 ga, 0 bo'lsa 1 ga almashtirilib, so'ngra 10 likka o'tkazilaib M soni hosil qilinadi.
Hosil bo'lgan yangi M son va K son yig'indisi N sondan katta bo'lmagan eng katta K sonni topish dasturi tuzilsin.
Birinchi qatorda T testlar soni beriladi. \((1≤T≤5*10^4)\).
Keyingi T ta qatorda N natural son beriladi. \((2≤N≤10^{18})\)
Masalani javobini alohida qatorlarda chop eting.
1-testda.
Biz izlayotgan K soni 15 bo'lsa, ikkilikda \(1111_2\) ga teng. Shartga binoan \(1000_2\) ga aylanadi va bu 10 likda 8 ga teng. 15+8=23 ga teng. Demak 25<23 shartga mos.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 25 78 342 |
15 31 127 |
D. Ajoyib ehtimollik
Xotira: 128 MB, Vaqt: 1000 msBilamizki, tangada ikkita tomon bor. Birinchisi gerb tomoni, ikkinchisi so’m tomoni. Ikkita qalbakitanga ishlovchi firibgar qimorbozlar bittadan tanga yasashdi: ularning bittasining tangasi qur’atashlanganda gerb tomoni bilan tushishi \(P\)% ehtimollik bilan, ikkinchisiniki esa \(Q\)% ehtimollikbilan tushadi. Ikkita firibgar nimagadir bahslashib qolishdi. Ularning bahsi bo’yicha, agar ikkitatangadan ixtiyoriy bittasi olinib ikki marta qur’a tashlansa ikki martada ham gerb tomon tushishikerak. Ular shunday qilishdi ham. Birinchi qur’a tashlanganda gerb tomon tushdi. Endi ularniikkinchi marta qur’a tashlanganda gerb tomon tushishi qiziqtiryapti. Sizdan ikkinchi qur’atashlanganda necha foiz ehtimollikda gerb tomon tushishini hisoblash so’raladi.
Bitta qatorda \(P\) va \(Q\) butun sonlari. \(P,Q(0 ≤ P,Q ≤ 100, P+Q > 0)\).
Yagona qatorda masala javobini \(10^{-4}\) aniqlikda chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
50 50 |
0.5000 |
E. Qalamlar
Xotira: 128 MB, Vaqt: 1000 msSizga bir nechta qalamchalar berilgan va ularning balandliklari ro‘yxat ko‘rinishida keltirilgan. Shu qalamlardan ketma-ket bo‘lgan bo‘laklarni tanlab, quyidagi shartlarga mos keladigan bo‘laklar sonini aniqlang.
Quyidagi shartlar:
- Tanlangan bo‘lakda faqat 3 ta novda bo‘lishi kerak.
- Tanlangan qalamlar balandliklari quyidagi ketma-ketliklardan biriga mos kelishi kerak:
- katta → kichik → katta (masalan, 3, 1, 4).
- kichik → katta → kichik (masalan, 1, 4, 2).
- 3 ta qalamning balandliklari bir-biridan farqli bo‘lishi kerak (bir xil balandlikdagi qalamlar qabul qilinmaydi).
Birinchi qatorda T testlar soni berialdi. \((1≤T≤10^3)\)
Keyingi T ta qatorda:
- Birinchi qatorda N \((3 ≤ N ≤ 10^4)\) — qalamlar soni.
- Ikkinchi qatorda N ta \(1\le A_1, A_2...A_N \le1000\) butun son — qalamlarning balandliklari.
Shartga mos keladigan barcha kombinatsiyalar sonini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 5 1 3 4 1 2 5 1 4 2 4 1 3 1 2 3 |
2 2 0 |
F. Antiqa amal
Xotira: 256 MB, Vaqt: 1000 msSizga \(N\) natural soni beriladi. \(1\)dan\(N\)gacha bo'lgan sonlarni maxsus \(⊗\) amali yordamida ketma-ket hisoblash kerak. Bu \(⊗\) amali quyidagicha bajariladi:
- Ikki sonni \(⊗\) bilan hisoblash uchun:
- Sonlar o'nlik sanoq sistemasida yoziladi
- Mos raqamlar ustma-ust qo'yiladi
- Har bir ustundagi raqamlar qo'shilib, \(10 \)ga bo'lgandagi qoldiq olinadi
Masalan: \(5294 ⊗ 7164 = 2358\) chunki:
(5+7)%10=2, (2+1)%10=3, (9+6)%10=5, (4+4)%10=8
Yagona qatorda \(N\) butun soni \(N(1≤N≤10^{18}).\)
Yagona qatorda masala javobini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
6 |
| 2 |
7 |
8 |
G. Ingliz tili
Xotira: 128 MB, Vaqt: 2000 msTATUning talabasi O'tkir ingliz tilini o‘rganmoqda. Unga ingliz tili o‘qituvchisi yangi so‘zlarni yodlashni topshirdi. Shu kunlarda O'tkir ingliz tilidan tashqari boshqa fanlardan ham ko‘p topshiriq olgan. Shuning uchun u ingliz tilidagi topshiriqlarni bir oz qisqartirishga qaror qildi va so‘zdagi harflardan \(k\) tasini kamaytirishni rejalashtirdi.
O'tkirning fikriga ko‘ra, o‘rganmoqchi bo‘lgan so‘zida turli xil harflar soni kam bo‘lsa, uni eslab qolish osonroq bo‘ladi. Ingliz tilidan yod olmoqchi bo‘lgan so‘zlari juda ko‘p bo‘lgani sababli, u har birini tekshirib chiqishga vaqt topolmayapti. Shu sababli, u yaqin do‘sti Shohruhdan yordam so‘radi.
Shohruh esa bu ishni qiyinlashtirmaslik uchun O'tkirga bu vazifa uchun dastur tayyorlashni maslahat berdi. Ammo Shohruhning vaqti yo‘qligi sababli sizdan yordam so‘rashga qaror qildi.
Sizdan O'tkirning vazifasini hal qilish uchun dasturni yozib berishingizni so‘raymiz. Bu dastur O'tkirning so‘zdagi turli harflar sonini kamaytirib, uni oson yod olishga yordam berishi kerak.
Birinchi qatorda O'tkirga berilgan so'z \(S\). \(|S|\)→so'z uzunligi. \(|S|(1≤|S|≤10^6).\)
Ikkinchi qatorda \(K\)butun soni \(K(1≤K≤10^6).\)
Birinchi qatorda har xil harflar sonini chop eting.
Ikkinchi qatorda hosil bo'lgan so'zni chop eting.
Iloji boricha kamroq harf qolishi kerak. Agar harflar soni teng bo'lsa, natija leksigrafik jihatidan kichik bo'lishi kerak.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
aaaaa 4 |
1 aaaaa |
| 2 |
mmsuz 2 |
2 mms |
H. YES or NO
Xotira: 256 MB, Vaqt: 3000 msBilamizki saralash algoritmlarining turlari juda ham ko’p. Lekin bu algoritmlar faqat sonlarni hech qanday qonuniyatga bo’ysunmasdan saralay oladi. Lekin savol tug’iladi, agarda sonlarni almashtirishlarda cheklovlar bo’lsa, bunday sonlarni qanday saralash mumkin?
Sizga \(N\) soni va \(1\) dan \(N\) gacha bo’lgan sonlardan tashkil topgan perestanovka berilgan. \(i\) – son o’zidan \(a[i]\) masofada turgan element bilan almasha oladi holos, ya’ni \(i\) – o’rinda turgan son \(j\) – o’rindagi son bilan almashtirilishi mumkin, qachonki \(|i - j| = a[i]\). Siz ushbu cheklovlar orqali perestanovkaning \(1\)-leksikografik ko’rinishiga olib kelish mumkin yoki yo’qligini tekshirishinggiz kerak bo’ladi.
Birinchi satrda \(N\) soni \(N(1 ≤ N ≤ 10^6)\) beriladi. Ikkinchi satrda \(1\) dan \(N\) gacha bo’lgan sonlar bitta probel bilan ajratilgan holda beriladi. Uchinchi satrda esa \(N\) ta elementdan tashkil topgan \(a[]\) massivi elementlari bitta probel bilan ajratib beriladi.
Agarda perestanovkani so’ralgan holatga olib kelib bo’lsa \(“YES”\) so’zini, aks holda \(“NO”\) so’zini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 4 3 2 1 1 1 1 1 |
YES |
| 2 |
7 4 3 5 1 2 7 6 4 6 6 1 6 6 1 |
NO |