A. Saflanish
Xotira: 128 MB, Vaqt: 1000 msHarbiy qism qo'mondoni barcha askarlarni zudlik bilan bo'ylari kichikdan kattaga qarab bir qator bo'lib saflanishga buyruq berdi. Askarlar buyruqni tezda bajarish uchun hamda barcha bir birini bo'ylarini uzunligini aniq bilmagani uchun hohlagan tartibda joylashib olishdi. Endi askarlarni to'g'ri joylashtirish uchun quyidagicha amal bajaradi. Agar chapdagi askar o'ngdagi askardan bo'yi uzun bo'lsa joylari almashtiriladi aks holda hech qanday amal bajarmaydi. Askarlar joylashuvini ko'rib nechta amal bajarib safni bo'ylarini o'sish tartibida joylashtira olishini hisoblayman deb qo'mondon eplayolmadi. Siz unga yordam bering.
Birinchi qatorda N natural son askarlar soni beriladi. \((1≤N≤5*10^5)\)
Ikkinchi qatorda N ta askar bo'ylari uzunligi beriladi. \((1≤A_i≤200)\)
Askarlarni bo'ylari o'sish tartibida joylashtirish uchun ketadigan amallar sonini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 1 2 4 3 |
1 |
| 2 |
6 6 3 1 2 4 5 |
7 |
B. Qopqon
Xotira: 128 MB, Vaqt: 1000 msSizda sichqonlar uchun N ta qopqon bor, ularning har biri koordinata tekisligida ma'lum bir joylashuvga ega. Chapdan o‘ngga qarab, i-chi qopqonning koordinatasi \(Aᵢ\) bo‘ladi.
Siz quyidagi shartlarga rioya qilgan holda ba’zi qopqonlarni olib tashlashingiz mumkin:
- Qolgan qopqonlarning har bir juftligi orasidagi masofa \(K\) yoki undan katta bo‘lishi kerak.
- Siz maksimal miqdordagi qopqonlarni qoldirishga harakat qilishingiz kerak.
Sizning vazifangiz – yuqoridagi shartlarga mos ravishda maksimal nechta qopqonni qoldirish mumkinligini aniqlash.
Birinchi qatorda ikkita butun son N va K sonlar berildi. \((1 ≤ N ≤ 3 × 10⁵, 1 ≤ K ≤ 10⁹)\)
Ikkinchi qatorda N ta butun son \(A₁, A₂, ..., Aₙ\) \((-10⁹ ≤ A₁ < A₂ < ... < Aₙ ≤ 10⁹)\),
ya'ni qopqonlar tartiblangan holda beriladi.
Maksimal qoldirish mumkin bo‘lgan qopqonlar sonini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 3 1 2 5 6 8 |
3 |
| 2 |
5 2 1 2 3 4 5 |
3 |
C. Kino
Xotira: 32 MB, Vaqt: 1000 msIsmoilning kino ko'rishni yoqtiradi. N ta yoqtirgan kinosini televizor orqali jonli tomosha qilmoqchi. Kun H soat davom etadi. Har bir i-kino \(A_i\) vaqtda jonli efirni boshlaydi va \(B_i\) vaqtda tugatadi. Ismoil bir vaqtning o‘zida bir nechta kinoning jonli efiriga to‘g‘ri kelgan bo‘lsa, ularning barchasini tomosha qiladi. U bir vaqtning o‘zida maksimal nechta kinoning jonli efirini tomosha qilishi kerakligini bilishni hohlaydi. Sizning vazifangiz Ismoilga yordam berish.
Birinchi qatorda N va H natural sonlar beriladi. \((1 ≤ N, H ≤ 10⁶)\)
Keyingi N ta qatorda har bir i-kino boshlanishi \(A_i \)va tugash vaqti \(B_i\) beriladi. \((0 ≤ Ai ≤ Bi < H)\)
Bir vaqtning o‘zida maksimal nechta kinoning jonli efirini tomosha qilishini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 5 0 2 1 4 2 3 |
3 |
| 2 |
7 10 8 9 3 6 2 4 1 8 7 9 0 4 5 6 |
4 |
D. Karrali
Xotira: 32 MB, Vaqt: 1000 msBerilgan \(A\)va \(B\) musbat butun sonlari uchun \(B+X\) ifodasi \(A+X \)ifodasining karrali bo'ladigan eng kichik \(X\) manfiy bo'lmagan butun sonini topish dasturini tuzing.
Birinchi qatorda T ta test soni beriladi. \((1≤T≤10^3)\)
Keyingi T ta qatorda A va B natural sonlar berialdi. \((1≤A≤B≤10^9)\)
Agar bunday \(X\) mavjud bo'lsa, uning eng kichik qiymatini, agar topilmasa -1 chi chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 11 23 2 3 8 16 |
1 -1 0 |
E. Darajali algebraik ifoda
Xotira: 64 MB, Vaqt: 1000 msSizda N ta butun sondan tashkil topgan massiv A = \((A₁, A₂, ..., Aₙ)\) berilgan.
Siz ushbu massivdan 4 ta turli butun son a, b, c, d ni tanlashning necha usuli mavjudligini topishingiz kerak. Tanlangan to'rtlik quyidagi shartlarni qanoatlantirishi lozim:
- \(10^a+ 9^b + 7^c + 5^d\) ifodasi \(P\) ga bo'linganda \(Q\) qoldiqni hosil qilishi kerak.
- \(a < b < c < d \)bo'lishi kerak.
Birinchi qatorda 3 ta butun son N, P, Q beriladi: \((4 ≤ N ≤ 800)\), \((2 ≤ Q < P ≤ 10⁵)\)
Ikkinchi qatorda N ta turlicha butun son \(A₁, A₂, ..., Aₙ\) lar beriladi: \((1 ≤ Aᵢ ≤ 2 × 10⁶)\)
Shartlarni qanoatlantiruvchi 4 ta sonni tanlashning nechta usuli borligini chop ering.
1-testda.
\((a,b,c,d)=(6,7,9,10)\) bo'lsa,\(10^6+9^7+7^9+5^{10}=55902201\)
Demak \(55902201\%7=5\) ekan.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 7 5 7 3 9 6 10 |
1 |
| 2 |
5 8 3 1 2 3 5 8 |
3 |
F. 2 va 5 emas
Xotira: 32 MB, Vaqt: 1000 ms2 ga ham, 5 ga ham bo‘linmaydigan musbat butun son \(N\) beriladi. Shu shartda, \(N\) soni \(10^K - 1\) ga bo‘linadigan musbat butun son \(K\) mavjud ekanligi ma’lum. Eng kichik \(K\) ni toping.
Bitta butun son N soni beriladi.\((1≤N≤10^{12})\)
Eng kichik \(K\) ni chop eting.
N soni 2 ga ham 5 ga ham bo'linmasligi kafolatlangan.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
1 |
| 2 |
9 |
1 |