A. Qiziqarli taqqoslash

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjon doskaga ikkita son yozdi. Ikkalasi ham quyidagi formatda berilgan: $x$ musbat son va $p$ oxirdan qo'shish kerak bo'lgan nollar soni.

Endi sizdan Azimjon bu ikki sondi solishtirishingizni so'radi. Unga yordam bera olasizmi?

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida $x_1, p_1(1\leq x_1 \leq 10^6, 0\leq p_1\leq 10^6)$ birinchi sondi tavsifi. Ikkinchi satrda $x_2, p_2(1\leq x_2 \leq 10^6, 0\leq p_2\leq 10^6)$ ikkinchi sondi tavsifi beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida agar birinchi son katta bo'lsa ‘>’, agar ikkinchi son katta bo'lsa ‘<’, agar ikki son teng bo'lsa ‘=’ belgisini chop eting.

Izoh:

Birinchi misolda birinchi sondi oxiridan bitta nol qo'shiladi, ikkinchi sondi oxiridan nolta nol qo'shiladi taqqoslash 20 > 19.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 19 0	>
2	1999 0 2 3	<

B. Azimjon va ketma-ketlik yig'indisi

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjonda $3$ ta musbat butun sonlar $a_1, a_2, a_3$ massiv mavjud. U ushbu massivning barcha ketma-ketliklari yig'indisini hisoblab chiqdi, ular kamaymaslik bo'yicha saralandi va $b_1,b_2,...,b_7$ massivni hosil qildi.

Masalan, agar $a=[1,4,3]$ sonlar mavjud bo'lsa, 1, 4, 3, 1+4=5, 1+3=4, 4+3=7, 1+4+3=8 yig'indilardan so'ng, saralangan $b=[1,3,4,4,5,7,8]$ massiv hosil qilinadi.

Afsuski Azimjon dastlabki $a$ massivini yo'qotib qo'ydi, $b$ massivdan foydalangan holda Azimjonga o'zining dastlabki massivini tiklashda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida $7$ ta $b_i(1\leq b_i\leq 10^9)$ butun sonlar bitta satrda beriladi, Azimjon hosil qilgan yangi massiv.

Chiquvchi ma'lumotlar:

Chiqish faylida Azimjonning dastlabki massivini chop eting bitta satrda, agar yechimlar bir nechta bo'lsa istalganini, istalgan tartibda chop etishingiz mumkin.

Misollar:

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

C. Turli xil butun sonlar

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Sizga $n$ ta butun sonlar qatori beriladi $a_1, a_2, ..., a_n$ . Siz ushbu sonlarning kichik to'plamini tanlashingiz mumkin(ehtimol hech birini yoki hammasini) va ularning ishorasini o'zgartirishingiz mumkin(ya'ni o'zgartirish $x\rightarrow -x$ ). Bunday operatsiyadan kiyin eng ko'p turli xil sonlar qancha bo'lishi mumkin?

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida $n(1\leq n\leq 10^5)$ butun soni va kiyingi satrda $n$ ta butun son $a_1,a_2,...,a_n(-10000\leq a_i\leq 10000)$ massiv elementlari beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida jami bo'lib nechta turli xil son hosil qilish mumkin ekanligini chop eting.

Izoh:

Birinchi misolda massivning birinchi va oxirgi elementining ishorasini o'zgartirishingiz mumkin $[-1, 1, 2, -2]$ .

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 1 1 2 2	4

D. Ro'xlarning joylashuvi

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Sizda $n\times n$ o'lchamli shaxmat doskasi va $k$ ta ro'x mavjud. Sizning vazifangiz ro'xlarni shaxmat doskasiga quyidagi ikki shart asosida joylashtirishdan iborat:

Istalgan ikki ro'x bir birga hujim holatda bo'lmasligi kerak;
Istalgan ro'xni qo'shni $8$ ta katakchaning biriga ko'chirganda ikki ro'x bir biriga hujim holatiga tushmasligi kerak.

Ikki ro'x hujim holatiga tushadi, agar ular joylashgan koordinatalarining $x_1=x_2$ yoki $y_1=y_2$ shart bajarilib qolsa.

Kiruvchi ma'lumotlar:

Kirish faylida $n,k(1\leq k\leq n\leq 40)$ butun sonlari mos ravishda shaxmat o'lchami va ro'xlar soni beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yuqorida aytilgan shartga mos holda $k$ ta ro'xni joylashtirishning iloji bo'lsa shaxmat doskasidagi joylashuvni chop eting(yechimlar bir nechta bo'lsa istalganini). Agar yechim mavjud bo'lmasa $-1$ ni chop eting.

Bo'sh katakchalar $'.'$ bilan, ro'xlar $'R'$ belgisi bilan tasvirlang.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 2	..... R.... ..... ....R .....
2	3 3	-1

E. Aylana stol

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Aylana stol atrofida $N$ ta do’st o’tirishibdi. Do’stlar $1$ dan $N$ gacha sonlar bilan raqamlab chiqilgan. Ular judaham zerikishdi shuning uchun bir qiziqarli o’yin o’ylab topishdi. O’yin sharti quyidagicha edi:

1-raqamli o’yinchidan boshlab ketma-ket sanashni boshlashadi;
Agar o’yinchi $K$ ga karrali sonni aytsa o’yinni tark etadi;
O’yinni tark etgan o’yinchidan so’ng sanash navbati kiyingi o’yinchiga o’tadi;
Sanash navbati oxirgi o’yinchiga kelsa kiyingi navbat yana boshiga ko’chiriladi.

Ushbu o’yin toki 1 kishi qolgunga qadar davom etadi. Sizning vazifangiz yakunda stol atrofida qolishi kerak bo’lgan o’yinchini tartib raqamini chop etishdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida $N,K(1\leq N,K\leq1000)$ butun sonlari beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida o'yin yakunida stol atrofida qolishi kerak bo'lgan o'yinchining tartib raqamini chop eting.

Izoh:

1-test:
Do'stlar 1 dan 4 gacha raqamlar bilan raqamlab chiqiladi [1, 2, 3, 4]. O'yinchilardan 2 ga karrali sonlarni aytganlar navbat bilan o'yinni tark etishi quyidagicha [1, 3, 4] → [1, 3] → [1]. Yakunda stol atrofida 1 raqamli o'yinchi qoladi.

2-test:
Do'stlar 1 dan 5 gacha raqamlar bilan raqamlab chiqiladi [1, 2, 3, 4, 5]. O'yinchilardan 3 ga karrali sonlarni aytganlar navbat bilan o'yinni tark etishi quyidagicha [1, 2, 4, 5] → [2, 4, 5] → [2, 4] → [4]. Yakunda stol atrofida 4 raqamli o'yinchi qoladi.

Misollar:

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

F. Arqonlar

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjonda $N$ ta arqon bor, bu arqonlar uzunligi mos ravishda $S_1,S_2,...,S_n$ ga teng. Azimjonning dadasi bu arqonlardan uzunligi maksimal bo’ladigan bir xil $K$ ta arqon kesib olishini aytdi.

Azimjon bu ishni uddalay olmaganligi sababli sizdan yordam so’rashga qaror qildi. Ushbu masalani yechishda Azimjonga dastur tuzib bering.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida $N(1\leq N\leq 10^4)$ butun son, Azimjondagi arqonlar soni. Kiyingi satrda $N$ ta butun son $S_1,S_2,...,S_n$ arqon uzunliklari, uzunlik $10^7$ dan oshmaydigan musbat butun son. Kiyingi satrda $K(1\leq K\leq 10^4)$ butun soni beriladi.

Chiquvchi ma'lumotlar:

Chiqish faylida Azimjon qirqib olishi mumkin bo'lgan $K$ ta bir xil maksimal uzunlikka ega bo'lgan arqon uzunligini $eps=10^{-6}$ aniqlikda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 802 743 457 539 11	200.500000
2	4 16 8 6 11 7	5.333333

G. Azimjon va daraxt

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjon daraxtlarga qiziqganligi sababli, hozida daraxtlar mavzusini o'rganmoqda. U bir qiziqarli masalaga duch keldi, masala sharti quyidagicha:

Uchlari $1$ dan $n$ gacha raqamlangan daraxt berilgan bo'lib, qirralari soni $n-1$ ta. Masalaning asosiy sharti daraxtdan shunday ikki uchni aniqlash kerakki bu uchlar o'rtasidagi masofada maksimal sonda qirralar mavjud bo'lsin.

Azimjon daraxtlar mavzusini endi o'rganayotganligi sababli ushbu masalani yechida qiynalayabdi. Siz Azimjonga yordam beraolasizmi?

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida $n(2\leq n\leq 10^5)$ butun soni, daraxt uchlari soni. Kiyingi $n-1$ ta satrda $u_i,v_i(1\leq u_i, v_i\leq n;u_i\neq v_i)$ juftliklar, ikki uch o'rtasida qirra mavjudligini ifodalaydi. Berilgan ma'lumotlarda daraxt berilishi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida daraxtning shunday ikki uchini chop etingki, ushbu uchlar o'rtasidagi masofada maksimal sondagi qirralar mavjud bo'lsin. Javoblar bir nechta bo'lsa istalgan javobni chop etishingiz mumkin, istalgan tartibda $(u,v)$ yoki $(v, u)$ ko'rinishida.

Misollar:

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