A. Sumalak toshlari

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dasturchialr Klubi jamoasi har yili birgalikda sumalak tayyorlash uchun bir joyga yig'ilishadi. Bu yil ham sumalak tayyorlash ishlari avjida. Ammo sumalakka solinadigan \(M\) ta toshlar yo'q edi. \(N\) ta bola tosh keltirish uchun jo'nab ketishdi va har biri \(a_i\) ta tosh keltirdi.
Sizning vazifangiz sumalakka \(M\) ta tosh solish uchun eng kamida nechta bolaning tergan toshlari tanlanadi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(M\) va \(N\) natural sonlari. Ikkinchi qatorda esa mos ravishta \(N\) ta bolaning keltirgan \(a_i\) toshlari soni. \((1 \le M, N, a_i \le 1000)\)

Chiquvchi ma'lumotlar:

Yagona qatorda sumalakka \(M\) ta tosh solish uchun kamida nechta boladan toshlar olinishini chiqaring. Agar toshlar yetarli bo'lmasa -1 chiqaring

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	20 7 2 6 9 4 5 7 1	3

B. Azimjon "Omad shou"da

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Azimjon "Omad shou"ga chiqish uchun tinmasdan "Jesco" limonadlarini ichmoqda! Bugun u do'konga borib, \(n\) shisha limonad sotib oldi. Har bir shishada \(t\) litrdan limonat bor. U shishalarni bir qator qilib qo'ydi va quyidagilarni qila boshladi:
1. U bitta shisha oladi, undan 1 litr ichadi.
2. Ichgan shishasini qatorning oxiriga qo'yadi va keyingi shishaga o'tadi. Bu 2 ta harakat 1 ta qadam deb hisonlanadi.

\(k\) ta qadamdan song Azimjon kamida bitta shishani bo'shata oladimi?

Kiruvchi ma'lumotlar:

Bitta qatorda \(n, t, k\) natural sonlari. \(( 1 \le n,k,t \le 1000)\)

Chiquvchi ma'lumotlar:

Azimjon \(k\) ta qadamda bironta shishani boshata olsa 1, aks holda -1 chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2 2	-1
2	2 1 1	1
3	4 3 7	-1
4	4 3 9	1

C. Devor bo'yash

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Azimjon va Maqsud devorni bo'yashga qaror qilishdi. Devor \(n\) dona taxtadan tashkil topgan.
Azimjon \(a\) - dan \(b\) - gacha bo'lgan, Maqsud esa \(c\) - dan \(d\) - gacha bo'lgan barcha taxtalarni bo'yaydi.
Sizning vazifangiz qancha taxtalar umuman bo'yalmaganligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta \(n (1 ≤ n ≤ 1000)\) butun soni.
Ikkinchi qatorda ikkita butun \(a\) va \(b (1 ≤ a ≤ b ≤ n)\).
Uchinchi qatorda ikkita butun \(c\) va \(d (1 ≤ c ≤ d ≤ n)\).

Chiquvchi ma'lumotlar:

Nechta taxta bo'yalmay qolishini toping.

Misollar:

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

D. Quyosh ko`p tutiladimi ?

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Astronomiya fanidan bilamizki, quyosh tutilishi hodisasi yiliga 2-4 marta sodir bo'ladi. (Istisno: 1693, 1758, 1805, 1823, 1870, 1935-yillarda 5 marta sodir bo'lgan va 2206-yili ham 5 marta sodir bo'lishi bashorat qilinmoqda) va har 18 yilda takrorlanadi. Ya'ni agarda K-yili 3 ta quyosh tutilishi bo`lgan bo`lsa, K+18 - yili ham 3 ta tutilish bo`ladi.

Quyosh tutilishi 2 xil bo`ladi: qisman yoki to`liq.
To`liq tutilish o`rtacha har 18 oyda bir marta sodir bo'ladi.

Olimlarga X-yili va undan keyingi 17 yilda quyosh necha marta tutilishi ma'lumdir.
Olimlarga yordam sifatida X yilining boshidan Y yilining oxirigacha jami quyosh tutilishlar,
to`liq tutilishlar va qisman tutilishlar sonini bilib beruvchi dastur tuzib bering.
X-1 yilning oxirgi quyosh tutilishi to`liq bo`lganligi kafolatlanadi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(T \le 100\) testlar soni kiritiladi.
Har bir test uchun birinchi qatorda sizga X yil beriladi.
Keyingi qatorda sizga mos ravishda X yili va undan keyingi 17 yildagi jami quyosh tutilishlari ro`yxati beriladi.
Oxirgi qatorda sizga Y yil beriladi. \((1600 \le X \le Y \le 2500)\)
Ro`yxatdagi sonlar \([2,5]\) oraliqda bo`ladi.

Chiquvchi ma'lumotlar:

Har bir test uchun yagona qatorda probellar bilan ajratilgan uchta sonni chiqaring, X yilining boshidan Y yilining
oxirigacha jami quyosh tutilishlar, to`liq tutilishlar va qisman tutilishlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1693 5 2 3 3 4 3 2 2 3 4 3 2 3 2 4 2 2 3 2022	956 53 903
2	1880 3 4 3 5 2 3 5 3 5 3 5 2 2 5 4 3 3 5 2119	865 48 817

E. Azimjonning sovg'asi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Azimjon bosh qotirmalarga qiziqadi. U bir kuni akasi bilan shunday o'yin o'ynadiki o'yinda \(n\) ta uy bor, uylar 1 dan \(n\) gacha raqamlangan, bu uylarning ichida \(k\) tadan tuzoq bor. Azimjonning akasi \(A\) raqamli uyga sovg'a yashirgan. Azimjon sovg'ani olguncha eng kamida nechta tuzoqni bosib utishi kerak. Azimjon bu o'yinda optimal (eng yaxshi) o'yinchi deb hisoblansin.
Azimjonga yordam sifatida, akasi sovg`ali xonadan tashqari hamma xonaga \(>\) yoki \(<\) belgili plakat ilib chiqdi, \(>\) belgisi qidirilayotgan xona teparoqda \(<\) belgisi qidirilayotgan xona pastroqda ekanligini anglatadi.
Uy raqamlari tartiblangan holda bo'ladi. Azimjonnig uzi bu ishni uddalay olmaydi, siz Azimjonga yordam bering.

Kiruvchi ma'lumotlar:

Bitta qatorda \(n\), \(k\) va \(A\) butun sonlari. \((1 \le A \le n \le 10^{18}, 1 \le k \le 5000)\)

Chiquvchi ma'lumotlar:

Bitta qatorda Azimjonning eng yaxshi usul bilan tushungan tuzoqlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	21 5 20	20

F. Bunaqasidan nechta ?

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga elementlari natural sonlar dan tashkil topgan hamda uzunligi \(N\) bo`lgan \(A\) massiv beriladi. Siz quyidagi shartlarni bajaruvchi uzunligi \(N\) bo`lgan har xil B massivlar sonini topuvchi dastur tuzing
- \(A[i] \ge B[i]\)
- \(B[i] \neq B[j] \space (i \neq j)\)
- \(B[i] \in \mathbb{N}\)

Kiruvchi ma'lumotlar:

Birinchi qatorda testlar soni \(T \leq 1000\) kiritiladi.
Har bir test uchun birinchi qatorda massiv uzunligi \(N \leq 10^4\) kiritiladi. Ikkinchi qatorda esa \(N\) ta natural son - massiv elementlari. Elementlar qiymati \(2^{63}\)-1 dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda har xil \(B\) massivlarning sonini chiqaring. Bu son o`ta katta bo`lishi mumkin shuning natijani \(13301411\) ga bo`lingandagi qoldig`ini toping

Izoh:

Birinchi testda quyidagicha \(B\) massivlarni tuzsa bo`ladi: [1,2,3] [1,2,4] [1,2,5]

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 3 1 2 5	3
2	2 2 5 4 2 1 1	16 0

G. Haqiqatmi yo yolg`on ?

Xotira: 16 MB, Vaqt: 2000 ms

Masala

Ko`pchilik dasturchilar yaxshi biladiki dasturlash tillarida mantiqiy amal operatorlari sifatida ba'zi tillarda \(!\) (emas) \(\&\) (va) \(|\) (yoki) kabilar ishlatiladi. Sizga N ta o`zgarmaslar sifatida lotin alifbosining bosh harflari (A, B...) va ularning qiymatlari beriladi. Beriladigan mantiqiy ifodaning qiymatini chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda testlar soni \(T\leq1000\) kiritiladi. Har bir test uchun birinchi qatorda \(0\leq N \leq26\) soni, ikkinchi qatorda mos ravishda o`zgarmaslar qiymati (A, B, ... jami \(N\) ta) beriladi. Uchunchi qatorda esa uzunligi \(2500\) dan kichik bo`lgan ifodaning algebraik ko`rinishi beriladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda ifodaning qiymatini \([0,1]\) chiqaring

Izoh:

\(N =0\) da o`zgarmaslar qiymati berilmaydi. U qatorni o`qimang !

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 3 0 0 1 A&(B&C) 1 1 (A&0)\|(!0)	0 1
2	2 5 1 1 1 1 1 !((!((A))&(B\|(!C\|(D&E))))) 0 !(0\|(!(1&0)))	1 0

H. Kim birinchi ?

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Samina va Sevinch sonlar o`qida \(0\) nuqtada joylashgan tosh bilan o`ynashyaptilar. O`yin sharti quyidagicha: Samina toshni ko`pi bilan \(X\) birlik chapga, Sevinch esa toshni ko`pi bilan \(Y\) birlik o`ngga sura oladi. Yurishni o`tkazish ham mumkin. Samina toshni \(A\) nuqtaga Sevinch esa \(B\)nuqtaga olib kelishi kerak. Optimal o`yinda kim g`olib bo`ladi? Yurishni Samina boshlaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(T \leq 10^5\) testlar soni. Har bir test uchun yangi qatorda \(1 \leq x,y\leq 10^9\) va \(A,B \leq|10^9|\) koordinatalari kiritiladi. Barcha sonlar butundir.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda optimal o`yinda g`olibning ismi chiqaring. O`yin cheksiz davom etadigan bo`lsa "Durrang" deb chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 3 3 -2 1 5 5 -10 10	Samina Durrang
2	2 4 5 -10 18 3 1 -25 -12	Sevinch Durrang