A. Kvadrat sonlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

N butun son berilgan bo'lsa, kvadrati N dan oshmaydigan natural sonlarning barcha kvadratlarini o'sish tartibida chop eting.

Kiruvchi ma'lumotlar:

Kirish faylida natural N soni berilgan \((N \le 10^9)\).

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	65	1 4 9 16 25 36 49 64

B. Ot

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Koordinatalar sistemasining \((x_1, y_1)\) katagida shaxmatdagi ot figurasi turibdi. U bir harakat bilan \((x_2, y_2)\) katagiga o'ta oladimi?

Kiruvchi ma'lumotlar:

Kirish faylida bo'sh joy bilan ajratilgan 4 ta butun son - \(x_1, y_1, x_2, y_2\) kiritiladi. Barcha sonlar [1, 8] oralig'ida ekanligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Agar bir urinishda borishning iloji bo'lsa “YES”, aks holda “NO” yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 5 2 7	YES
2	3 5 1 7	NO

C. Qutilar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ikkita quti mavjud Birinchisining o'lchami \(A_1*B_1*C_1\), ikkinchisiniki esa \(A_2*B_2* C_2\). Bir qutini ikkichisining ichiga to'liq joylashtirish mumkinmi?

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida birinchi quti o'lchamlari bo'sh joy bilan ajratilgan holda kiritiladi. Keyingi qatorda ikkinchi quti o'lchamlari kiritiladi. Sonlar orasi bo'sh joy bilan ajratiladi. Barcha sonlar butunligi va \(10^3\) dan oshmasligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Agar qutilar o'lchami bir xil bo'lsa “Qutilar o'zaro teng”;

Agar ikkinchi quti birinchi qutiga joylasha olsa “Birinchi quti ikkinchisidan katta”;

Agar ikkinchi quti birinchi qutiga joylasha olsa “Birinchi quti ikkinchisidan kichik”;

Boshqa har qanday holatda “Qutilarni solishtirib bo'lmaydi” jumlasini chop eting.

Izoh:

E'tibor bering, qutilarni faqatgina \(90^0\) gradusga aylatirish mumkin.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 3 2 1 3	Qutilar o'zaro teng
2	4 5 6 4 4 3	Birinchi quti ikkinchisidan katta
3	4 5 6 5 6 8	Birinchi quti ikkinchisidan kichik
4	4 5 6 7 2 4	Qutilarni solishtirib bo'lmaydi

D. Piter Pen

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Kapitan Hookning kemasida \(n\) ta sandiq ketma-ket qo'yilgan. Ma'lumki yonma-yon sandiqlar bir vaqtda ochilsa xavfsizlik tizimi ishga tushadi. Har bir sandiq ichida qanchadir miqdorda oltin bor. Piter Pen kemaga o'g'irlikka tushdi hamda u yerdan imkon qadar tezroq chiqib ketishi zarur. U 1 marta sandiqlarning oldidan uchib o'tish orqali maksimum miqdorda oltin yig'ishni xohlaydi. Shuni ham unutmangki, vaqt tig'izligi sabab Piter Pen hech bir sandiqni yopishga ulgurmaydi.

Piter Pen yig'ishi mumkin bo'lgan maksimum oltinni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) - sandiqlar soni kiritiladi.

Keyingi qatorda \(n\) ta butun son har bir sandiq ichidagi oltin miqdorlari - \(A_i (1 \le i \le n)\) kiritiladi.

\(1 \le n \le 10^6\)

\(1 \le A_i \le 10^9\)

Chiquvchi ma'lumotlar:

Maksimum yig'ish mumkin bo'lgan oltinni chop eting.

Izoh:

1-test uchun quyidagi sandiqlardan oltinni olish maksimal foyda keltiradi:

1 10 2 2 6 1 6 6 6 1

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 1 10 2 2 6 1 6 6 6 1	28
2	5 7 9 6 9 3	18

E. Daraxtdagi LIS

Xotira: 64 MB, Vaqt: 1000 ms

Masala

N ta tugundan tashkil topgan daraxt mavjud. \(i-\)yo'l \(u_i\) va \(v_i\) tugunlarni o'zaro bog'laydi va qiymati \(a_i\) ga teng. 1 dan N gacha bo'lgan har bir k butun soni uchun quyidagini aniqlang:

Yo'llarga yozilgan butun sonlarni 1-yo'ldan k-yo'lgacha bo'lgan eng qisqa yo'l bo'ylab ular paydo bo'ladigan tartibda qatorlab ketma-ketlik hosil qilamiz. Ushbu ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi (LIS)ining uzunligini toping.

Bu yerda uzunligi \(L\) boʻlgan \(A\) ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi \(M\) ning mumkin boʻlgan eng katta qiymatiga ega boʻlgan \(A_{i_1}\) ,\(A_{i_2}\) ,...,\(A_{i_M}\) qatori boʻlib, \(1≤i_1 <i_2 <...<i_M ≤L\) va \(A_{i_1} < A_{i_2} <...< A_{i_M}\) bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N butun soni kiritiladi.

Keyingi qatorda N ta butun son a massiv elementlari kiritiladi

Keyingi N-1 ta qatorning har birida 2 tadan butun son \(u_i\) va \(v_i\) kiritiladi.

\(2 \le N \le 2*10^5\)
\(1 \le a_i \le 10^9\)
\(1 \le u_i, v_i \le N\)
\(u_i \neq v_i\)
Graf daraxt ekanligi kafolatlanadi.
Barcha qiymatlar butun sonlardir.

Chiquvchi ma'lumotlar:

N qatorni chop eting. k-chi qator, 1-yo'ldan k-yo'lgacha bo'lgan eng qisqa yo'ldan olingan ketma-ketlikning eng uzun o'sib boruvchi pastki ketma-ketligi uzunligini chop eting.

Misollar:

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