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 o'sish tartibida 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