A. Puzzle

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga \(n*n\) jadval beriladi. Berilgan jadvalga \(1\) dan \(n^2\) gacha bo'lgan sonlarni shunday joylashtirish kerakki, bunda har bir juft sonning barcha qo'shnilari toq son, toq sonning qo'shnilari esa juft son bo'lishi kerak.

Jadvaldagi elementga qo'shni element deb, unga gorizontal yoki vertikal yo'nalishda tutashgan elementlarga aytiladi.

Agar \(n*n\) jadvalni yuqoridagi usulda to'ldirishning imkoni bo'lsa “YES”, aks holda “NO” chiqaring

Kiruvchi ma'lumotlar:

Bitta qatorda \(n\) natural soni.

\(3 \leq N \leq 10^{2}\)

Chiquvchi ma'lumotlar:

Bitta qatorda agar jadvalni yuqoridagi usulda to'ldirish mumkin bo'lsa “YES”, aks holda “NO” chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	100	YES

B. Play Off

Xotira: 32 MB, Vaqt: 1000 ms

Masala

O'zbekiston va Qatar terma jamoalari futbol bo'yicha Al-Xorazmiy turnirining yarim finalida birga o'ynashmoqda. Jamoalar 2 ta o'yin o'tkazishlari kerak. O'yinlarning biri O'zbekistonda ikkinchisi esa Qatarda bo'lib o'tishi kerak. Bu jamoalar ishtirokidagi 1-o'yinda O'zbekiston terma jamoasi a ta, Qatar terma jamoasi esa b ta gol urgan.
Ayni damda 2-o'yinning 88 daqiqasi ortda qoldi. Bu o'yinda hozircha O'zbekiston x ta, Qatar esa y ta gol urdi.
Turnir shartlariga ko'ra agar umumiy xisob durrang bilan tugasa, ammo qaysidir jamoa mehmonda ko'proq gol urgan bo'lsa, o'sha jamoa keyingi bosqichga chiqadi. Agar hisoblar aynan bir xil bo'lgan bo'lsa, o'yin durrang hisoblanadi va qo'shimcha (Extra) bo'limlar qo'shib beriladi va hisob o'zgarmasa penaltilar seriyasi o'tkaziladi.
Savol: O'tgan o'yindagi va hozirgi o'yindagi hisoblardan kelib chiqqan holda, sizdan so'ralgan jamoa o'yinda penaltilar seriyasiga bormasdan g'olib bo'lishi uchun kamida nechta gol urishi kerak.

Kiruvchi ma'lumotlar:

Kiruvchi ma'lumotlar quyidagicha beriladi:
Team1_Name Team1_Gol2 - Team2_Gol2 Team2_Name (Team1_Gol1 - Team2_Gol1)

Bu yerda Team1_Name 2-o'yindagi mezbon jamoa, Team2_Name esa 2-o'yindagi mehmon jamoa. Team1_Gol2 2-o'yinda mezbon jamoaning urgan gollari, Team2_Gol2 2-o'yinda mehmon jamoaning urgan gollari. Team1_Gol1 1-o'yinda hozirgi mezbon jamoaning urgan gollari, Team2_Gol1 1-o'yinda hozirgi mehmon jamoaning urgan gollari. Qaysi jamoa nomi ekranda birinchi bo'lib kelsa, o'sha jamoa 2-o'yinning mezboni hisoblanadi. Ikkinchi qatorda esa TeamS - sizdan so'raladigan jamoa.

O'zbekiston jamoasining nomi UZB shaklida, Qatar jamoasining nomi esa QAT shaklida beriladi. Bir jamoa bir o'yinda 10 tagacha gol urishi mumkin.

Chiquvchi ma'lumotlar:

Yagona qatorda TeamS jamoa finalga chiqishi uchun urishi kerak bo'lgan minimal gollar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	QAT 1-6 UZB (4-8) UZB	0
2	UZB 9-0 QAT (7-5) QAT	11

C. Shaxboz va 8-mart

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Shaxboz va uning \(n-1\) ta do'sti 8-mart “Xalqaro xotin-qizlar kuni” munosabati bilan, kursdosh qizlariga sovg'a olish uchun do'konga kelishdi. Ular do'kondan jami \(p\) ta sovg'a olishdi. Do'konda \(1\) dan \(k\) gacha raqamlangan \(k\) ta kassa bor. Har bir i-kassa sotuvchisi bitta sovg'ani hisoblash uchun \(x_i\) vaqt sarflaydi, i-kassa sotuvchisi barcha xaridlar uchun \(y_i\) vaqt ichida xaridordan to'lovni qabul qilib bo'ladi, ayni paytda Shaxboz yoki uning do'stlariga i-kassadagi navbat kelishi uchun \(t_i\) vaqt ketadi.

Shaxboz va uning do'stlari kassalarga shunday navbatda turishlari va sovg'alarni shunday bo'lib olishlari kerakki, ular do'kondan to'liq chiqib ketishlari uchun eng minimal vaqt sarflashlari kerak. (Sovg'asiz turgan xaridor kassa oldidan vaqt sarflamasdan o'tib ketishi mumkin.)
Sizning vazifangiz ularning barchasi do'kondan chiqib ketishlari mumkin bo'lgan eng minimal vaqtni hisoblashdan iborat.

Kiruvchi ma'lumotlar:

Birinchi satrda \(k\) butun soni do'kondagi kassalar soni kiritiladi.

Keyingi \(k\) ta satrda 3 tadan butun sonlar \(x_i\) - \(i\)-kassa sotuvchisi har bir sovg'ani ro'yxatdan o'tkazishi uchun ketadigan vaqt, \(y_i\) - i-kassa sotuvchisi hozirgi xaridordan xaridlar uchun to'lovni qabul qilishi uchun ketadigan vaqt, \(t_i\) - i-kassadagi navbat tugashi uchun ketadigan vaqt.

Keyingi qatorda Shaxboz va do'stlarining umumiy soni \(n\) va ular olgan sovg'alar soni \(p\) kiritiladi.

\(1\leq n , k \leq 10^{5}\)

\(1 \leq x_i , y_i , t_i \leq 10^{5}\)

\(1 \leq p \leq 10^{6}\)

Chiquvchi ma'lumotlar:

Shaxboz va do'stlari do'konni tark etishlari uchun kerak bo'ladigan minimal vaqt miqdorini chop eting.

Izoh:

Pythonda ishlaydiganlar uchun PyPy ishlatish tavsiya qilinadi.

Misollar:

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

D. Shashka o'yini

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Shashka o'yinida donalar diagonal bo'yicha bitta katakka yurishini bilasiz. Agar sizning shashka donangizning diagonal yo'nalishidagi birinchi katakda raqib donasi turgan bo'lsa va shu diagonal bo'yicha ikkinchi katak bo'sh bo'lsa, demak siz raqib donasini urib olishingiz mumkin. Bu vaziyatda urib olingan dona katakdan olib tashlanadi, sizning donangiz esa diagonal bo'ylab ikkinchi katakka qo'yiladi.
Agar siz raqib donasini urib olganingizdan so'ng yana raqib donasini urib olish imkoniyati bo'lsa, bir yurishning o'zida navbatdagi donalarni ham urib olishda davom etishingiz mumkin. (Masalada “Damka” holati mavjud emas deb hisoblanadi)

Sizga shashka o'yinidagi qaysidir holat beriladi. Sizning vazifangiz shu holatda yurish sizda bo'lganida eng ko'pi bilan nechta raqib donasini urib olishingiz mumkinligini topishdan iborat. (Holatlardagi donalar soni haqiqiy shashka o'yini bilan mos kelmasligi mumkin.)

Kiruvchi ma'lumotlar:

\(8\) ta qatorda \(8*8\) shashka taxtasidagi holat beriladi. Bu yerda '#' bo'sh joylarni, '@' sizning donangizni, '&' esa raqib donasini bildiradi.

Chiquvchi ma'lumotlar:

Bir urinishda maksimum nechta raqib donalarini urib olishingiz mumkinligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	#&###### ######## #####&## ##&###&# ###&#### &#&##### ###@###& ##@#@###	2

E. So'z top!

Xotira: 128 MB, Vaqt: 1000 ms

Masala

O'sha mashhur so'z top o'yini o'ynamagan odam bo'lmasa kerak. Shu o'yindan ilhomlanib ajoyib masala yaratdik. Sizga bitta so'z va lotin alifbosining kichik harflaridan tashkil topgan jadval beriladi. Siz jadvaldagi belgilarni bir biri bilan tutashtirish orqali berilgan so'zni hosil qilishingiz kerak bo'ladi.

Siz harakatni jadvalning istalgan katakchasidan boshlashingiz mumkin. Siz turgan katakchadan vertikal va gorizontal harakat qilib faqat bitta katakcha oldinga yura olasiz. Siz harakatlangan katakchalardagi belgilar bir biri bilan tutatishib so'z hosil qilinadi. Harakatni istalgancha davom etish mumkin, ammo bir marta bosib o'tgan katakchadan yana yurish mumkin emas.

Kiruvchi ma'lumotlar:

Dastlabki \(5\) qatorda \(5*5\) o'lchamdagi lotin alifbosining kichik belgilaridan iborat jadval beriladi.

Keyingi qatorda bitta so'z kiritiladi.

Chiquvchi ma'lumotlar:

Agar so'z jadvaldagi belgilar yordamida berilgan so'zni yasash mumkin bo'lsa “Yes”, aks holda “No” so'zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	somet almah malli emmmn thing something	Yes
2	aaaaa aaaaa aaaaa aaaaa aaaab aaaaaaaaaabax	No

F. Ajoyib shakllar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Maktab doskasi tomoni \(a\) va \(b\) bo'lgan to'g'ri to'rtburchak shakliga ega. O'quvchilarda esa doira va kvadrat shaklidagi magnitli yopishtirgichlar mavjud. Sizning vazifangiz o'quvchilar qo'llaridagi barcha yopishtirgichlarni doska ichiga yopishtirish mumkinligini aniqlashdan iborat. Shakllarni umumiy sohaga ega qilib va doska sirtidan chiqib ketadigan qilib yopishtirish mumkin emas.

Kiruvchi ma'lumotlar:

Birinchi qatorda maktab doskasining tomonlari \(a\) va \(b\) beriladi. Ikkinchi qatorda doira shaklidagi yopishtirgichlar soni \(n\) va kvadrat shaklidagi yopishtirgichlar soni \(m\) beriladi.

Uchinchi qatorda \(n\) ta son doira diametrlari beriladi.

To'rtinchi qatorda esa \(m\) ta son kvadrat tomonlari beriladi.

\(1\leq a , b \leq 100\)

\(1\leq n , m \leq 10\)

Doira diametrlari va kvadrat tomonlari, qiymati 200 dan oshmaydigan natural sonlar bilan beriladi.

Chiquvchi ma'lumotlar:

Agar berilgan shakllarning barchasini joylashtirishning imkoni bo'lsa “YES”, aks holda esa “NO” chiqaring.

Misollar:

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