SamCoding Round 3 (Div. 2)

A. Takroriy elementlar

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Berilgan \(n\) ta butun sondan iborat massivda kamida ikkita bir xil element bormi yoki yo'qmi, aniqlang.

Kirish ma'lumotlari

Kirish faylida \(n\) (\(1 \le n \le 2 \times 10^5\)) massiv elementlari soni beriladi.

Keyingi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) beriladi.
Chiqish ma'lumotlari

Agar massivda takroriy element bo'lsa YES, aks holda NO chop eting. (Harflarning katta yoki kichikligi ahamiyatsiz, javobni istalgan ko'rinishda chiqarishingiz mumkin: masalan, yes, YES, Yes yoki no, NO, No).

Misollar
# Input.txt Output.txt
1 
5
2 4 6 8 2
 
Yes
2 
5
1 2 3 4 5
 
no
3 
3
7 7 7
 
yEs

B. Goldbach juftligi

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 64 mb

Berilgan juft \(n\) sonini ikkita tub songa ajrating (\(p + q = n\) ikkalasi ham tub son). Shartni qanoatlantiruvchi bir nechta to'g'ri juftliklar bo'lishi mumkin — ulardan istalganini chiqarish mumkin.

Kirish ma'lumotlari

Kirish faylida bitta qatorda \(n\) (\(4 \le n \le 10000\), \(n\) juft son) beriladi.

Chiqish ma'lumotlari

\(p\) va \(q\) sonlarini bo'sh joy bilan ajratgan holda chop eting (\(p + q = n\)). Bir nechta mos juftlik mavjud bo'lsa, ulardan istalganini chiqarishingiz mumkun.

Misollar
# Input.txt Output.txt
1 
4
 
2 2
2 
6
 
3 3

C. Labirint

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Sizga \(W \times H\) o'lchamdagi (kengligi \(W\) ta katak, balandligi \(H\) ta katak) matnli ASCII formatda berilgan labirint taqdim etiladi. Labirintda kirishdan chiqishgacha bo'lgan aniq bitta yagona to'g'ri yo'l mavjud.

  • Har bir katak matnda maxsus ASCII simvollar yordamida chiziladi. Labirintning umumiy satrlar soni \(2\times H + 1\) tani, har bir satrdagi belgilar soni (kengligi) esa \(4\times W + 1\) tani tashkil qiladi. Devorlar \(+\), \(-\) va \(|\) simvollari orqali, yo'laklar esa bo'sh joylar yordamida ko'rsatiladi.
  • Kirish qismi labirintning yuqori chap burchagida, chiqish qismi esa pastki o'ng qismida joylashgan.

Sizning vazifangiz — berilgan labirintdagi kirish nuqtasidan chiqish nuqtasigacha bo'lgan yagona to'g'ri yo'lni topish va o'sha yo'lning har bir katakdagi markaziy qismiga nuqta \((.)\) belgisini qo'yib, labirintning yakuniy ko'rinishini ekranga chiqarishdan iborat. To'g'ri yo'lga kirmagan boshqa bo'sh joylar o'z holicha qolishi kerak (nuqta qo'yilmaydi).

Kirish ma'lumotlari

Birinchi qatorda ikkita butun son — labirintning kataklardagi kengligi \(W\) va balandligi \(H\) beriladi (\(1 \le W, H \le 100\)).

Keyingi qatorlarda esa labirintning devorlari va bo'sh joylarini aks ettiruvchi ASCII matnli ko'rinishi keladi.

Chiqish ma'lumotlari

Topilgan yagona to'g'ri yo'l katakchalarining markaziga (uchta bo'shliqning o'rtasiga) nuqtalar \((.)\) qo'yilgan holda, labirintning yakuniy matnli ko'rinishini ASCII formatda to'liq chop eting.

Misollar
# Input.txt Output.txt
1 
5 3
+---+---+---+---+---+
    |           |   |
+   +   +   +   +   +
|   |   |   |   |   |
+   +   +   +---+   +
|       |
+---+---+---+---+---+
 
+---+---+---+---+---+
  . | .   .     |   |
+   +   +   +   +   +
| . | . | . |   |   |
+   +   +   +---+   +
| .   . | .   .   .
+---+---+---+---+---+
2 
5 5
+---+---+---+---+---+
    |               |
+   +   +   +---+   +
|       |       |   |
+   +---+---+   +---+
|           |       |
+   +---+---+---+   +
|   |           |   |
+   +   +---+   +   +
|   |       |
+---+---+---+---+---+
 
+---+---+---+---+---+
  . | .   .         |
+   +   +   +---+   +
| .   . | .   . |   |
+   +---+---+   +---+
|           | .   . |
+   +---+---+---+   +
|   |           | . |
+   +   +---+   +   +
|   |       |     .
+---+---+---+---+---+

D. Token o'yini

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Ikki o'yinchi grafda o'ynaladigan quyidagi o'yinni o'ynashadi.

Berilgan yo'naltirilmagan oddiy graf \(N\) ta uchga (uchlar \(1\) dan \(N\) gacha raqamlangan) va \(M\) ta qirraga ega. Graf oddiy (ya'ni ikki uch orasida bir nechta qirra bo'lmaydi va uchning o'ziga o'ziga qirrasi yo'q) bo'lib, u albatta bog'langan bo'lishi shart emas — bir nechta alohida qismlardan (komponentalardan) iborat bo'lishi mumkin.

Grafning \(S\) uchida bitta token (belgi) joylashgan.

O'yinchilar navbat bilan yurish qilishadi, birinchi bo'lib \(1-\)o'yinchi yuradi. Har bir yurishda navbatdagi o'yinchi tokenni hozirgi turgan uchdan qirra orqali qo'shni bo'lgan, va o'yin boshidan buyon hali hech qachon token tashrif buyurmagan boshqa uchga ko'chiradi.

Uch bir marta ziyorat qilingandan so'ng u "band" hisoblanadi — token bu uchga ikkinchi marta hech qachon qaytmaydi (garchi qirra mavjud bo'lsa ham).

Navbati kelgan, ammo yura olmaydigan o'yinchi — ya'ni tokenning joriy turgan uchidan chiqadigan barcha qirralar allaqachon band bo'lgan uchlarga olib boradigan (yoki umuman bu uchdan qirra chiqmaydigan) o'yinchi — yutqazadi.

Ikkala o'yinchi ham optimal (eng yaxshi mumkin bo'lgan) strategiyada o'ynaydi, ya'ni har biri o'z g'alabasini ta'minlash imkoniyati bo'lsa, albatta undan foydalanadi.

Sizning vazifangiz — kim g'olib chiqishini aniqlash.

Kirish ma'lumotlari

Birinchi qatorda uchta butun son — \(N\), \(M\) va \(S\) (\(2 \le N \le 1000\), \(0 \le M \le \frac{N(N-1)}{2}\), \(1 \le S \le N\)) beriladi.

Keyingi \(M\) ta qatorning har birida ikkita butun son \(u_i, v_i\) (\(1 \le u_i, v_i \le N\), \(u_i \neq v_i\)) beriladi — bu \(i-\)qirra \(u_i\) va \(v_i\) uchlarini bog'lashini bildiradi. Graf oddiy bo'lgani uchun bir xil qirra takrorlanmaydi.

Chiqish ma'lumotlari

Agar ikkala o'yinchi ham optimal o'ynaganda birinchi o'yinchi g'olib chiqsa — first so'zini, aks holda (ikkinchi o'yinchi g'olib chiqsa) second so'zini chop eting (kichik harflarda).

Misollar
# Input.txt Output.txt
1 
4 3 1
1 2
2 3
3 4
 
first
2 
4 3 2
1 2
2 3
3 4
 
first
3 
2 0 1
 
second
Izoh

Birinchi testda token 1-uchda turibdi. 1-o'yinchi tokenni \(1 \rightarrow 2\) ga ko'chiradi, shunda 1-uch band bo'ladi. Keyin 2-o'yinchi \(2 \rightarrow 3\) ga yuradi va 2-uch band bo'ladi. Shundan so'ng 1-o'yinchi \(3 \rightarrow 4\) ga yuradi. Token 4-uchga kelganida, uning yagona qo'shni uchi (3-uch) allaqachon band bo'lgani uchun 2-o'yinchi yura olmaydi va yutqazadi. Natijada birinchi o'yinchi g'alaba qozonadi va first natijasi chiqariladi.

E. Mandat

Vaqt chegarasi: 2000 ms | Xotira chegarasi: 256 mb

Davlat Test Markazi (Agentlik) \(n\) ta abituriyent va \(m\) ta yo'nalish bo'yicha mandat (grant va kontrakt o'rinlarini) taqsimlashi kerak.

Har bir \(i-\)yo'nalish uchun grant o'rinlari soni \(g_i\) va kontrakt o'rinlari soni \(c_i\) oldindan ma'lum.

Har bir abituriyent quyidagi ma'lumotlarga ega:

  • ball — uning test balli (butun son);
  • ustuvorlik turi — \(0\) (grant-ustuvor) yoki \(1\) (yo'nalish-ustuvor);
  • \(1\) dan \(5\) gacha bo'lgan tanlovlar ro'yxati — abituriyent tanlagan yo'nalishlar, ustuvorlik tartibida (ro'yxatdagi birinchisi eng afzal).

Taqsimlash tartibi

1. Barcha abituriyentlar ball bo'yicha kamayish tartibida navbatga qo'yiladi. Agar ballari teng bo'lsa, kirish faylida oldinroq berilgan abituriyent ustun turadi.

2. Har bir abituriyent navbatga yetganda, o'z ustuvorlik turiga qarab quyidagicha joylashtiriladi:

  • Grant-ustuvor (\(0\)): avval o'zining barcha tanlovlarini tartib bo'yicha ko'rib chiqadi va bo'sh grant o'rni bor birinchi yo'nalishga joylashadi. Agar birorta tanlovda ham bo'sh grant o'rni topilmasa, tanlovlarini yana boshidan tartib bo'yicha ko'rib chiqadi, bo'sh kontrakt o'rni bor birinchi yo'nalishga joylashadi.
  • Yo'nalish-ustuvor (\(1\)): tanlovlarini tartib bo'yicha birma-bir ko'rib chiqadi; har bir tanlov uchun avval grant o'rni bo'rligini tekshiradi (bo'sh bo'lsa — o'sha yerga grant asosida joylashadi va to'xtaydi), bo'lmasa kontrakt o'rnini tekshiradi (bo'sh bo'lsa — kontrakt asosida joylashadi va to'xtaydi). Agar bu tanlovda ikkalasi ham band bo'lsa, keyingi tanlovga o'tadi.

3. Agar abituriyentning barcha tanlovlaridagi o'rinlar band bo'lsa, u hech qayerga joylashmaydi.

Har bir abituriyent uchun (kirishda berilgan asl tartibda) qaysi yo'nalishga va qanday asosda (grant yoki kontrakt) joylashganini aniqlang.

Kirish ma'lumotlari

Birinchi qatorda ikkita butun son \(n, m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^4\)) beriladi.

Keyingi \(m\) qatorning har birida ikkita butun son \(g_i, c_i\) (\(0 \le g_i, c_i \le 10^5\)) — \(i-\)yo'nalishning grant va kontrakt o'rinlari soni beriladi.

Keyingi \(n\) ta abituriyentning har biri uchun \(2\) qatordan iborat ma'lumot beriladi:

  • \(1-\)qatorda: ball, turi (\(0\) yoki \(1\)) va \(k\) (\(1 \le k \le 5\)) — ball, ustuvorlik turi va tanlovlar soni;
  • \(2-\)qatorda: \(k\) ta son — tanlangan yo'nalishlar raqamlari (\(1\) dan \(m\) gacha), ustuvorlik tartibida, takrorlanmaydi.
Chiqish ma'lumotlari

Har bir abituriyent uchun (kirishdagi tartibda), alohida qatorda:

  • agar u biror yo'nalishga joylashgan bo'lsa — yo'nalish raqami va grant yoki kontrakt so'zini bo'sh joy bilan ajratib;
  • aks holda — yagona \(-1\).
Misollar
# Input.txt Output.txt
1 
4 3
1 1
1 0
0 1
90 0 3
2 1 3
85 1 2
1 2
80 0 2
1 3
70 1 2
3 2
 
2 grant
1 grant
1 kontrakt
3 kontrakt
2 
1 1
1 0
150 0 1
1
 
1 grant
Izoh

Abituriyentlar ball bo'yicha kamayish tartibida ko'riladi: \(90, 85, 80, 70\).

  • \(90\) ball (grant-ustuvor, tanlovlar: \(2, 1, 3\)): avval barcha tanlovlaridan grant izlaydi — \(2-\)yo'nalishda grant bo'sh (\(1\) ta) \(\to\) shu yerga grant bilan joylashadi.
  • \(85\) ball (yo'nalish-ustuvor, tanlovlar: \(1, 2\)): \(1-\)yo'nalishda grant bo'shligini tekshiradi — bo'sh (\(1\) ta) \(\to\) shu yerga grant bilan joylashadi.
  • \(80\) ball (grant-ustuvor, tanlovlar: \(1, 3\)): grant izlaydi — \(1-\)yo'nalish grant band, \(3-\)yo'nalishda grant yo'q (\(0\) ta) \(\to\) grant topilmadi. Qayta ko'rib, kontrakt izlaydi — \(1-\)yo'nalishda kontrakt bo'sh (\(1\) ta) \(\to\) shu yerga kontrakt bilan joylashadi.
  • \(70\) ball (yo'nalish-ustuvor, tanlovlar: \(3, 2\)): \(3-\)yo'nalishda grant yo'q, kontrakt bo'sh (\(1\) ta) \(\to\) shu yerga kontrakt bilan joylashadi.

F. Xavfsiz parol

Vaqt chegarasi: 2000 ms | Xotira chegarasi: 256 mb

Alisher o‘zining sevimli EduPortal ta’lim platformasiga kirmoqchi, lekin ro‘yxatdan o‘tishda qaysi parolni tanlaganini eslay olmayapti. Uning kompyuterida saqlangan \(n\) ta turli xil parol mavjud bo‘lib, ulardan faqat bittasi to‘g‘ri — aynan shu parol bilan u tizimga muvaffaqiyatli kirgan edi.

Alisher parollarni uzunligi bo‘yicha o‘sish tartibida (eng qisqasidan boshlab) terib chiqadi. Agar bir nechta parol bir xil uzunlikka ega bo‘lsa, u bu parollarni o‘zaro ixtiyoriy tartibda sinab ko‘radi (ya'ni, bir xil uzunlikdagi parollarning aniq ketma-ketligi oldindan noma'lum — shu sababli eng yaxshi va eng yomon holatlarni hisoblab chiqish talab etiladi). To‘g‘ri parolni kiritgan zahoti u tizimga kiradi va jarayon darhol to‘xtaydi.

Har bir parolni terish va kiritish uchun \(1\) soniya vaqt sarflanadi.

Xavfsizgik tizimi talablariga ko‘ra (bu real hayotdagi brute-force hujumlardan himoya mexanizmiga o‘xshaydi): agar Alisher ketma-ket \(k\) marta noto‘g‘ri parol kiritsa, xavfsizlik tizimi uni vaqtincha bloklaydi va u keyingi urinishni faqatgina \(5\) soniya kutgandan keyingina amalga oshirishi mumkin bo‘ladi.

Sizning vazifangiz — Alisherga tizimga kirish uchun eng kam va eng ko‘p qancha soniya vaqt ketishini aniqlashdan iborat.

Kirish ma'lumotlari

Birinchi qatorda ikkita butun son — \(n\) va \(k\) beriladi (\(1 \le n, k \le 100\)) — parollar soni va bloklanishdan oldingi ketma-ket noto‘g‘ri urinishlar chegarasi.

Keyingi \(n\) ta qatorning har birida bitta matn — lotin harflari va raqamlardan iborat, bo'sh joylarsiz, juft-jufti bilan har xil (takrorlanmaydigan) parollar beriladi. Har bir parol uzunligi \(100\) ta belgidan oshmaydi.

Oxirgi qatorda Alisherning haqiqiy (to‘g‘ri) paroli beriladi. Kafolatlanadiki, bu parol yuqoridagi \(n\) ta parolning biriga teng.

Chiqish ma'lumotlari

Alisherga tizimga kirish uchun kerak bo‘ladigan minimal va maksimal vaqtni (sekundlarda) yagona qatorda chop eting.

Misollar
# Input.txt Output.txt
1 
1 1
a
a
 
1 1
2 
4 1
a
bb
ccc
dddd
dddd
 
19 19
3 
5 2
ab
cd
hi
efg
jkl
efg
 
9 15

G. Avtoturargoh

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Turargoh tarifi quyidagicha belgilangan:

  • Birinchi \(1\) soat — bepul.
  • \(2-\)soatdan \(5-\)soatgacha (ya'ni har bir mashina uchun \(2, 3, 4, 5\)-soatlar) — har bir soat uchun \(p\) so'mdan olinadi.
  • \(5\) soatdan ortiq turgan mashinalar uchun, \(6-\)soatdan boshlab, har bir keyingi soat yarim narxda (\(p / 2\) so'm) hisoblanadi.

\(n\) ta mashinaning turargohda turgan soatlari berilgan. Har bir mashina uchun to'lov yuqoridagi qoida bo'yicha hisoblanadi, so'ngra barcha mashinalardan yig'ilgan jami tushum topilishi kerak.

Kirish ma'lumotlari

Birinchi qatorda ikkita butun son \(n, p\) (\(1 \le n \le 100\), \(2 \le p \le 1000\), \(p\) — juft son) beriladi.

Ikkinchi qatorda \(n\) ta butun son — har bir mashinaning turargohda turgan soatlari \(h_i\) (\(1 \le h_i \le 24\)) beriladi.

Chiqish ma'lumotlari

Yagona qatorda — barcha mashinalardan yig'ilgan jami tushumni chop eting.

Misollar
# Input.txt Output.txt
1 
3 200
1 3 8
 
1500
2 
1 2
1
 
0