A. Tikanvoy va topshiriq

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Bugun tipratikan Tikanvoy birinchi marta maktabga bordi! O'qituvchi unga uy vazifasini berdi, afsuski, tipratikan sizning yordamingizsiz qila olmaydi.

Tikanvoy \(a_1, a_2, ..., a_n\) manfiy bo'lmagan butun sonlar massiviga ega. U avvaliga ixtiyoriy bitta musbat butun son x ni tanlaydi, shundan so‘ng x ni massivdagi ba’zi raqamlarga qo‘shadi (massivning har bir elementi uchun bir martadan ko‘p bo‘lmaydi), ba’zilaridan x ni ayiradi (massivning har bir elementi uchun bir martadan ko‘p bo‘lmaydi) ) va ba'zi raqamlarni buzmasdan qoldiradi. Shu tarzda bir xil sonlar massivini yasash mumkinmi?

Tikanvoy x ni shunday tanlash mumkinmi yoki yo'qligini bilmoqchi va keyin shunday harakatlarni bajaringki, natijada massiv bir xil sonlardan iborat bo'lsin.

Kiruvchi ma'lumotlar:

Kirishning birinchi qatorida butun n \((1 ≤ n ≤ 10^5)\) - Tikanvoy massividagi raqamlar soni mavjud. Ikkinchi qatorda n ta butun \(a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9)\) — massiv elementlari mavjud.

Chiquvchi ma'lumotlar:

Chiqish faylida, shunday x ni topishning imkoni bo'lsa ″YES″, aks holda ″NO″ yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 3 3 2 1	YES
2	5 1 2 3 4 5	NO

B. Abrakadabra

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Abrakadabra - lotin harflaridan iborat satr bo'lib, quyidagi qonun asosida yasaladi. Birinchi qadamda satr bo'sh. Keyingi qadamlarda mavjud satr ikki marta ko'payib, unga chap tomoniga keyingi lotin alifbosida joylashgan (a, b, c, …) belgi qo'shiladi. Abrakadabra satrning yasash bosqichidan misol:

Qadam 1. ;

Qadam 2. a;

Qadam 3. baa;

Qadam 4. cbaabaa;

Qadam 5. dcbaabaacbaabaa;

Barcha lotin harflaridan hosil bo'lgan abrakadabra satrning N– o'rinda turgan belgini ekranga chiqaruvchi dastur tuzing. Masala shartida so'ralgan natijani chop eting.

Kiruvchi ma'lumotlar:

Bitta qatorda N (1 ≤ N < 2²⁶ - 1) soni kiritiladi.

Chiquvchi ma'lumotlar:

Masala shartida so'ralgan natijani chop eting.

Izoh:

Misollar testlar bilan bir xilligi kafolatlanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1	z
2	67108863	a

C. Noodatiy dasturlash musobaqasi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Noodatiy dasturlash musobaqasida \(N\) ta o'quvchi ishtirok etmoqda. Uning boshqa musobaqalardan farqi shundaki bu musobaqa bir nechta raunddan tashkil topgan bo'ladi. Bunda masalani birinchi bo'lib ishlagan o'quvchi \(N\) ballni undan keyingilar mos ravishda 1 balldan kam ball olib boradi va har bir o'quvchi berilgan masalalarni ishlay olishi kafolatlanadi. Oxirgi bo'lib ishlagan ishtirokchi mos ravishda 1 ballni qo'lga kiritadi. Hozir sizga o'sha \(N\) nafar o'quvchining oxirgi raund oldidan ballari beriladi. Ulardan nechtasida g'oliblikni qo'lga kiritish imkoniyati borligini aniqlang.

Hech bir ikki o'quvchi bir vaqtda masalani ishlay olmaydi.

Agarda bir nechta o'quvchilarda ballar teng bo'lsa ularning barchasi g'olib deb topiladi.

Kiruvchi ma'lumotlar:

Kirish faylining 1-qatorida \(N(3 \le N \le 300 000)\) soni kiritiladi.

Keyingi \(N\) qatorda o'quvchilarning oxirgi raungacha to'plagan ballari.

Bunda ularning qiymatlari nomanfiy butun sonlar hamda 2000000 dan oshmaydi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son nechta o'quvchida g'olib bo'lish imkoniyati borligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 8 10 9	3
2	5 15 14 15 12 14	4

D. Kamondan o'q otish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

R – radiusli doira shaklidagi nishon taxtasi berilgan. Ushbu nishon taxtasi 1/2, 1/4, 1/6 kichik radiusli aylanalarga ajratilgan bo‘lib, mos ravishda A, B, C ballga ega. Ravshan bobosi yasab bergan kamon yordamida ushbu taxtaga N ta o‘q otdi. O‘qlar nishon taxtasining (x_i, y_i) nuqtalariga tegdi. Ravshanbek jami N ta o'q yordamida necha ball to'plaganini topib beruvchi dastur tuzing.

Kiruvchi ma'lumotlar:

Birinchi qatorda N (1 ≤ N ≤ 10⁵) va R (1 ≤ R≤ 10⁹) mos ravishda o'qlar soni hamda nishon taxtasi radiusi

Ikkinchi qatorda A, B, C (1 < A < B < C < 10⁹) aylanalarga tekkanda beriluvchi ballar

N ta qatorda o'q tekkan koordinata x_i,y_i (-10⁹ ≤ x_i,y_i≤ 10⁹) kiritiladi.

Chiquvchi ma'lumotlar:

Masala shartida so'ralgan natijani chop eting.

Izoh:

Agarda o‘q chiziq ustiga tekkan bo‘lsa kichikroq aylanaga tegishli bo‘ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 12 2 3 6 0 2 5 0	8

E. Noodatiy so'rov

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Davron massivlar bilan o'yin o'ynashni juda yaxshi bo'radi. Davronda N uzunlikka ega \(c_1, c_2, ..., c_N\)massivi bor. Bir kuni u quyidagi o'yinni o'ynamoqchi bo'ldi, massivning [L, R] oralig'ini kesib oladi va summasi 0 ga teng bo'ladigan va bir biri bilan kesishmaydigan qism massivlar sonini aniqlaydi. Lekin bu ishni bajarish juda ko'p vaqt olgani uchun Davron sizlardan yordam so'ramoqda. Davronning ishini tezlashtiruvchi dastur tuzing.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N natural soni mavjud \((1 \le N \le 4*10^5)\).

Keyingi qatorda N ta butun son - massiv elementlari joylashgan \((-10^9 \le c_i \le 10^9)\).

Uchinchi qatorda so'rovlar soni - Q kiritiladi \((1 \le Q \le 4*10^5)\).

Keyingi Q ta qatorning har birida ikkita butun son L va R mavjud \((1 \le L \le R \le N)\).

Chiquvchi ma'lumotlar:

Chiqish fayliga har bir so'rov uchun alohida qatorda massivning [L, R] oralig'ida yig'indisi 0 ga teng bo'lgan qism massivlar sonini chop eting.

Izoh:

Qism massiv - massivning o'ng va chap tomonidan 0 yoki bir nechta elementlarini qirqib tashlashdan hosil bo'lgan massiv.

Masalan bizga berilgan massiv [1, 2, 3, 4, 5] bo'lsin. Bunday holatda ushbu massivning qism massivlari deb quyidagilarni aytishimiz mumkin: [1, 2], [3, 4, 5], [2, 3, 4] ... . [1, 2, 4], [3, 5] lar esa qism massiv bo'la olmaydi.

Birinchi misolga izoh:

1-so'rovda: [{1, 2, -3}, {0}, {1, -4, 3}, 2, {-1, 1}]

2-so'rovda: [{1, 2, -3}, {0}, 1]

3-so'rovda: [2, -3, {0}, {1, -4, 3}, 2, -1, 1]

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 1 2 -3 0 1 -4 3 2 -1 1 3 1 10 1 5 2 9	4 2 2