A. Saflanish

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Harbiy 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.

Kiruvchi ma'lumotlar:

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)$

Chiquvchi ma'lumotlar:

Askarlarni bo'ylari o'sish tartibida joylashtirish uchun ketadigan amallar sonini $10^9+7$ ga bo'lgandagi qoldiqni chop eting.

Misollar:

#	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 ms

Masala

Sizda 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Maksimal qoldirish mumkin bo‘lgan qopqonlar sonini chop eting.

Misollar:

#	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 ms

Masala

Ismoilning 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.

Kiruvchi ma'lumotlar:

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)$

Chiquvchi ma'lumotlar:

Bir vaqtning o‘zida maksimal nechta kinoning jonli efirini tomosha qilishini chop eting.

Misollar:

#	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 ms

Masala

Berilgan $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.

Kiruvchi ma'lumotlar:

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)$

Chiquvchi ma'lumotlar:

Agar bunday $X$ mavjud bo'lsa, uning eng kichik qiymatini, agar topilmasa -1 chi chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 11 23 2 3 8 16	1 -1 0

E. Darajali algebraik ifoda

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizda 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.

Kiruvchi ma'lumotlar:

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⁶)$

Chiquvchi ma'lumotlar:

Shartlarni qanoatlantiruvchi 4 ta sonni tanlashning nechta usuli borligini chop ering.

Izoh:

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.

Misollar:

#	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 ms

Masala

2 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.

Kiruvchi ma'lumotlar:

Bitta butun son N soni beriladi. $(1≤N≤10^{12})$

Chiquvchi ma'lumotlar:

Eng kichik $K$ ni chop eting.

Izoh:

N soni 2 ga ham 5 ga ham bo'linmasligi kafolatlangan.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3	1
2	9	1