A. Farqlar ketma-ketligi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dilnura maktabda endi qo’shish va ayirishni o’rgandi. Kunlardan bir kun u maktabga o’qituvchi va boshqa bolalardan ertaroq borib qolganida doskada $N$ ta son bitta qatorda yozilganligini ko’rdi. U o’rgangan bilimlarini mustahkamlash maqsadida doskaga yozilgan sonlar ketma-ketligidan har yonma-yon joylashgan sonlarning farq (kattasidan kichigini ayirilgan qiymat)ini hisoblamoqchi bo’ldi. U barcha yonma-yon joylashgan sonlar uchun ularning farqini bir qator qilib yozib chiqdi, so’ngra dastlabki sonlar qatorini doskadan o’chirdi. Shundan so’ng doskada jami $N-1$ ta son qoldi, ya’ni Dilnura hisoblagan yonma-yon sonlar farqi doskada qoldi. U shu ishini doskada bitta son qolguniga qadar davom ettirdi.

Siz doskada qolgan sonning qiymatini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida bitta butun son, $N$ ( $2 \le N \le 2000$ ) soni kiritiladi, keyingi qatorda qiymati $[0,10^9]$ oralig’idagi $N$ ta butun son, ya’ni doskada yozilgan sonlar ketma-ketligi kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish oqimida yagona butun son, doskada qolib ketgan sonni chop eting.

Misollar:

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

B. Keramik idishlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Zilolada slindr shaklidagi radiuslari $R_1,R_2,...,R_N {\ } sm$ bo’lgan $N$ ta keramik idish bor. U idishlarini tokchaga terib chiqmoqchi, bunda idishlarning barchasi tokchaning bir tomoniga tegib turishi kerak. Zilola idishlarning barchasini tokchaga tera olishi uchun tokchaning uzunligi eng kamida necha sm bo’lishi kerakligini hamda idishlar tokchaga qaysi tartibda qo’yilishi kerakligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida bitta butun son, $N(1 \le N \le 8)$ soni, ya’ni idishlar soni kiritiladi.

Kirish oqimining ikkinchi satrida $N$ ta haqiqiy son, $R_i(1 \le i \le N, 0 < R_i < 100) -$ idishlarning radiuslari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish oqimining dastlabki satrida tokchaning mumkin bo’lgan eng qisqa uzunligi necha sm ekanligini eng kamida $10^{-4}$ aniqlikda chop eting, keyingi satrda esa aynan shu uzunlikdagi tokchaga idishlarning joylashtirilish tartibini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2.0 2.0 1.0	9.6568542495 1 3 2

C. Daryo

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Rectangulariston mamlakati to’rtburchak shaklida bo’lib bizga $H \times W$ to’rtburchakni eslatadi, ya’ni, bu mamlakat xaritasiga qaralganda $H$ ta qator va $W$ ta ustundan iborat mahallalardan iborat bo’lib, $i$ - qatorning $j$ - ustundagi mahallaning ixtiyoriy nuqtasi dengiz sathidan $A_{i, j}$ balandlikda joylashgan.

Mamlakat prezidenti mamlakat uzra juda katta o’zgarishlar qilmoqchi. U biron bir $k(1 \le k < W)$ - ustunni tanlaydi va xaritadan qaraganda mamlakatni $k$ va $k + 1$ - ustunlar orasidan daryo o’tkazadi. Shundan so’ng u mahallalarni birlashtiradi, agarda: mahallar o’zaro qo’shni(umumiy tomonga ega), dengiz sathidan bir xil balandlikda joylashgan hamda ularni yaqindagina o’tkazilgan dengiz ajratmasa.

Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan minimal mahallalar sonini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida ikkita butun son, $H(1 \le H)$ va $W(2\le W)$ sonlari beriladi. Keyingi $H$ ta qatorning har birida $W$ tadan butun son, $A_{i,j}(1\le i \le H, 1 \le j \le W, 1 \le A_{i, j} \le 10^9)$ har bir mahallaning dengiz sathidan balandligi kiritiladi. Bunda matritsa elementlar soni $H \times W \le 500000$ ekanligi kafolotlanadi.

Chiquvchi ma'lumotlar:

Chiqish oqimida yagona butun son, Rectangulariston mamlakati prezidenti o’z rejalarini bajarib bo’lganidan so’ng mamlakatda erishish mumkin bo’lgan eng kam mahallalar sonini chop eting.

Izoh:

1 - testga izoh. Daryo uchinchi va to’rtinchi ustun orasidan kesib o’tganda

1-mahallaga (1,1), (1,2), (1,3), (2,3), (3,2), (3,3) elementlardagi mahallalar birlashgan

2-mahallaga (2,1), (2,2), (3,1), (4,1), (4,2), (4,3) elementlardagi mahallalar birlashgan

3-mahallaga (1,4), (2,4), (3, 4) elementlardagi mahallalar birlashgan

4-mahallaga (4,4) elementdagi mahalla o’zi qolgan.

Misollar:

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

D. Uyga chiqish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dilnura 9 etajli binoning $N$ - etajida yashaydi. U yashaydigan binoda lift hamda zinapoya bor. 2 etaj oralig’idagi zinapoya 2 qismdan iborat, har bir qismda $K$ tadan zina mavjud, istalgan ikki qism oralig’ida bo’sh maydoncha mavjud. Dilnura har kun darsdan qaytganidan so’ng o’z uyiga zinapoya va (yoki) liftdan foydalangan holda chiqadi. Zinapoya orqali chiqishda Dilnura bir qadamda bitta yoki ikkita zina yuqorilay oladi. Dilnura uyga chiqishi davomida doim tepaga harakatlanadi. Dilnura darsdan qaytgandan so’ng o’z uyiga chiqishining necha xil usuli (harakat ketma-ketligi) mavjudligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining yagona satrida ikkita butun son, $N(1 \le N \le 9)$ va $K( 1 \le K \le 15)$ sonlari, ya’ni Dilnura yashaydigan etaj raqami hamda zinapoyaning har bir qismida nechta zina borligi kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish oqimida yagona butun son, Dilnura darsdan qaytgandan so’ng o’z uyiga chiqishining necha xil usuli (harakat ketma-ketligi) mavjudligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 6	170
2	3 4	677

E. Radio

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun $N$ ta Radio o’rnatilgan. Har bir radioning ovoz balandligi $K$ ga teng. Radioda yangilik eshittirilganda $A$ - koordinatada bo’lgan uyga $B$ -koordinatada joylashtirilgan radioning ovozi $max(K-|A-B|, 0)$ balandlikda eshitiladi. Sizga $M$ ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish oqimining dastlabki satrida uchta butun son, $N(1 \le N \le 250000)$ , $M(1 \le M \le 250000)$ va $K(1 \le K \le 10^9)$ sonlari kiritiladi. Ikkinchi satrda $N$ ta butun son, $B_i(1 \le i \le N, 0 \le B_i \le 10^9)$ Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, $A_i(1 \le i \le M, 0 \le A_i \le 10^9)$ uylarning joylashgan koordinatalari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 5 10 20 20 15 28 10 32	10 5 2 0 0
2	3 4 100 116 194 258 57 155 222 360	41 61 72 0