A. Antiqa kvadrat

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizga n soni beriladi va siz quyidagi kabi matritsa chiqarishingiz kerak. Markazda bitta n uning atrofini n-1, n-1 ning atrofini n-2 va h.k eng ustida 1.

Kiruvchi ma'lumotlar:

Bitta natural n son. n < 1001.

Chiquvchi ma'lumotlar:

2*n-1 ga 2*n-1 matritsa korinishida javob.

Misollar:

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

B. Oraliqdagi raqamlar yig'indisi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Bir kuni Jaxongir cheksiz doskaga L dan boshlab R gacha sonlarni yozib chiqdi va vergullar bilan ajratdi. Bunda L va R ham kiradi. Keyin esa vergullarni o'chirib har bir raqamlar orasiga qo'shish amalini qo'yib chiqdi. Va natijani hisoblamoqchi bo'ldi. Ammo u buni hisoblashni istamayapti. Bunda Jaxongirga yig'indini hisoblashga yordam bering.

Kiruvchi ma'lumotlar:

Bir qatorda ikki butun son L va R beriladi.

Bunda \(1 \le L \le R \le\)\(10^{18}\) va \(0 \le R - L \le 10^{17}\)

Chiquvchi ma'lumotlar:

Yig'indini chop eting. Yig'indi biroz katta bo'lishi mumkin shu sabab int64 dan foydalaning.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 9	45
2	1 10	46

C. Kevin o'yinchoqlar do'konida

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Kevin New Yorkda yolg'iz aylanib yurib ajoyib o'yinchoq do'koniga kirib qoldi. U yerda ko'plab o'yinchoqlar Kevinga yoqib qoldi. Ammo bu ancha ko'p pul bo'lishi aniq. Shu sababli o'yinchoq do'koni egasi unga bir imkoniyat berdi. Unga ko'ra u jammi pulning xohlagan joyiga plus amalini qo'yishi mumkin. Kevinga imkoni boricha kamroq pul to'lashida yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida natural son - jami qancha pul bo'lganligi. Bunda u 100 ming xonagacha uzunlikda bo'lishi mumkin.

Chiquvchi ma'lumotlar:

Chiqish faylida Kevin to'lashi mumkin bo'lgan eng kam pulni qiymatini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10000000001	2
2	1234	46
3	1231230000001	123124

D. Arrayni silliqlash

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Asadbek arraylarni yaxshi ko`radi qachonki ular silliqlangan bo'lsa.

Silliqlangan array bu elementlarining orasida boshqa bir array bo`lmagan to'plamdir. Masalan: [1, 2, 3] silliqlangan array, chunki elementlar tarkibida boshqa array yo'q. [1, 2, [3, 4]] esa silliqlanmagan array, chunki elementlari tarkibida [3, 4] array mavjud. Kunlarning birida Ibrohim Asadbekga yangi funksiyani o'rgatdi. Bu funksiya arrayning har bir elementini 1 pog'ona yuqoriga ko'tarib beradi, agar element 0 - pog'onada bo'lsa uning pog'onasi o'zgarmaydi.

Masalan:

[1, [2, 3], [3, 4, [1, 2]]] => [1, 2, 3, 3, 4, [1, 2]]

Ya'ni:

1 => 0 - pog'onada bo'gani uchun uning pog'onasi o'zgarmaydi.

[2, 3] => 2, 3.

[3, 4, [1, 2]] => 3, 4, [1, 2].

Asadbek bu funksiyani o'zi qaytadan tuzishga qaror qildi va sizga ham buni taklif qilmoqchi. Unga funksiya tuzishda yordam bering!

Kiruvchi ma'lumotlar:

Kirish faylida sizga bir qatorda k (0 < k < 10⁹) soni va string s (0 < |s| < 10⁵) ko'rinishida arrayning dastlabki holati beriladi. Bu yerda |s| - matnning uzunligi. Matnda ortiqcha probellar bo'lmasligi va array to'g'ri formatda berilganligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Siz dastlabki arrayni k marta silliqlashdan so'ng hosil bo'lgan yangi arrayni chop etishingiz kerak.

Izoh:

Agar silliqlanayotgan array allaqachon silliqlangan bo'lsa funksiya arrayning o'zini qaytaradi.

[1, 2, 3, 4, 5] => [1, 2, 3, 4, 5].

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 [1,[2,3],[3,4,[1,2]]]	[1,2,3,3,4,[1,2]]
2	200 [a,[b,c,[d,e]]]	[a,b,c,d,e]

E. Ibrohimning tangalari

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Interaktiv masala!

Ibrohim tangalardan kolleksiya qilishni juda yoqtiradi. Kunlardan bir kun u barcha tangalarini bir qatorga terib chiqdi va bir xil qiymatlilarini yonma-yon qo'ydi. Oxirida sezib qoldiki tangalar soni toq ekan. U biladiki har bir tanga 2 tadan bo'lishi kerak edi. Ammo qaysidir tanga yo'qolganga o'xshaydi. Unga bu tangani aniqlashda yordam bering. Uning tangalari soni N \(\le 100000\) va tanga qiymatlari x \(\le10^9\)

Kiruvchi ma'lumotlar:

Har bir so'rovda k-indeksdagi tanga qiymatini "? k" ko'rinishida so'rashingiz mumkin. Bunda k ning qiymati \(1\le k \le 10^9\) shartni qanoatlantirishi kerak.

Inekslash 1 dan boshlanadi. Ko'pi bilan 55 ta so'rov yuborishingiz mumkin.

Javobni topganda esa "! X" ko'rinishida yuborishingiz kerak bo'ladi.

Har bir so'rvdan so'ng qatorni tugatishingiz kerak!

Chiquvchi ma'lumotlar:

Har bir so'rovga mos holda o'sha indeksdagi tanga qiymati chiqariladi. Agar k-indeks mavjud bo'lmasa "-1" javobini qaytaradi.

Izoh:

ESLATMA: Interaktiv masalada sizning javobingizni hakamlar hay’ati qabul qila olishi uchun siz har bir so’rovingiz oxirida

Agar Pascal tilida ishlagan bo’lsangiz: flush(output)
Agar C/C++ tilida ishlagan bo’lsangiz fflush(stdout) yoki cout.flush()
Agar Java tilida ishlagan bo’lsangiz System.out.flush()
Agar pythonda ishlagan bo’lsangiz sys.stdout.flush()
Agar C# tilida ishlagan bo’lsangiz Console.Out.Flush()

Buyruqlardan birini yozishingiz kerak bo’ladi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	359 -1 499	? 1 ? 101 ? 9 ! 499

F. Farxod o'ylagan sonni top!

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Interaktiv masala.

Farxod bir son o'yladi. Va u bu sonni sehrli ekanligini aymoqda lekin bu son qaysi son ekanligini aytmayapti. Ammo u faqat bir narsani aytishga rozi bo'ldi. Uning raqamlar yig'indisi. Har safar Farxoddan savol so'rashingiz mumkin. U o'ylagan songa siz aytgan sonni qo'shadi va uning raqamlar yig'indisini aytadi. Har safar son qo'shganda avvalgi natijaga qo'shadi o'zi o'ylagan songa emas.

Kiruvchi ma'lumotlar:

Har bir so'rovdan keyin natijaning raqamlar yig'indisi chiqariladi. Farxod o'ylagan son 1 milliarddan oshmaydi.

Chiquvchi ma'lumotlar:

"+ x" ko'rinishida so'rov yuborishingiz mumkin bunda \(0 \le x \le 10^{9}\)

Javobni topgach esa "! ans" ko'rinishida javob berishingiz kerak bo'ladi. So'rovlar soni 100 dan oshmasligi kerak.

Izoh:

ESLATMA: Interaktiv masalada sizning javobingizni hakamlar hay’ati qabul qila olishi uchun siz har bir so’rovingiz oxirida

Agar Pascal tilida ishlagan bo’lsangiz: flush(output)
Agar C/C++ tilida ishlagan bo’lsangiz fflush(stdout) yoki cout.flush()
Agar Java tilida ishlagan bo’lsangiz System.out.flush()
Agar pythonda ishlagan bo’lsangiz sys.stdout.flush()
Agar C# tilida ishlagan bo’lsangiz Console.Out.Flush()

Buyruqlardan birini yozishingiz kerak bo’ladi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	13 5 6	+ 0 + 1 + 1 ! 49
2	6 2	+ 1 + 5 ! 14

G. Oraliq vazni

Xotira: 64 MB, Vaqt: 1500 ms

Masala

Sizga n o’lchamli v massiv va so’rovlar beriladi (massiv 1dan indekslangan)

So’rovlar \(l \space r \space x \space y\) ko’rinishida.

Yani \(v[l:r]\) sonlardan nechtasi \(x≤v_i≤y (l≤i≤r)\) shartini qanoatlantiradi.

Kiruvchi ma'lumotlar:

Kirish fayida birinchi qatorda \(n\) va \(q (1≤n≤10^5, 1≤q≤10^5)\)

Ikkinchi qatorda \(n\) ta massiv elementlari.

Keyingi \(q\) ta qatorda so’rovlar \(l r x y (1 ≤ l ≤ r ≤ n, -10^9 ≤ x ≤ y ≤ 10^9)\)

Chiquvchi ma'lumotlar:

\(q\) ta qatorda mos ravishda har bir so’rov uchun javob

Izoh:

\(v[l:r]=\{v_l, v_l+1, v_l+2, …, v_r\}\) ni anglatadi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 4 2 6 5 2 1 3 5 8 1 5 1 5 4 5 4 5	1 4 1