A. Kuchli shoh

Xotira: 16 MB, Vaqt: 1000 ms
Masala

\(8 × 8\) shaxmat doskasida “Kuchli shoh” figurasi \(v_1\) katakda turibdi. “Kuchli shoh” figurasi oddiy shohdan farqi shundaki, uning bir yurishi 2 barobar kattaroqdir. To‘liqroq tushunish uchun rasmga qarang. Bu rasmda d4 katakda turgan “”Kuchli shoh” ning mumkin bo‘lgan barcha yurishlari tasvirlangan.

U \(v_2\) katakka minimal necha yurishda bora oladi?

Kiruvchi ma'lumotlar:

Yagona qatorda ikkita satr - \(v_1\) va \(v_2\), \(8 × 8\) doskadagi kataklar beriladi.

Chiquvchi ma'lumotlar:

Bitta butun son — “Kuchli shoh” \(v_1\) katakdan \(v_2\) katakka borishi uchun kerak bo‘ladigan minimal yurishlar sonini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
d4 f6
 
1
2 
a1 g6
 
3

B. Satr yasash

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Quyidagi shartlarning barchasini qanoatlantiruvchi satr yasang:

  1. Satr faqat ingliz alifbosining kichik harflaridan tashkil topgan bo’lsin;

  2. Satrda ketma-ket kelgan bir xil harflar uchramasin;

  3. ‘a’ harfi \(a_1\) marta, ‘b’ harfi \(a_2\) marta, ... ‘z’ harfi \(a_{26}\) marta qatnashsin.

Shartlarni qanoatlantiruvchi istalgan satrni chiqarishingiz mumkin.

\(1 ≤ a_1 + a_2 + a_3 + ... + a_{26} ≤ 1000\) ekanligi va shartlarni qanoatlantiruvchi satr mavjudligi kafolatlanadi.

Kiruvchi ma'lumotlar:

Yagona qatorda 26 ta butun son - \(a\) massiv elementlari kiritilad

Chiquvchi ma'lumotlar:

Shartlarni qanoatlantiruvchi istalgan satrni chiqaring.

Izoh:

.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
 
axyza

C. Billiard

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Billiard bu uzunligi \(M\) va balandligi \(N\) bo‘lgan to‘g‘ri to‘rtburchakdir. Shar chap tepa tomondan (1-teshikdan) \(45^∘\) burchak ostida uriladi. Urilgan sharcha teshikka tushmaguncha harakatda bo‘ladi. Sharcha harakatlanishi davomida necha marta devorga urilishi va qaysi teshikka tushishini aniqlovchi dastur tuzing. Teshiklar billiardning 4 chekkasida joylashgan va rasmdagidek raqamlangan.

Kiruvchi ma'lumotlar:

Yagona qatorda ikkita butun son - \(M\) va \(N(1 ≤ M, N ≤ 2 * 10^{9})\) kiritiladi.

Chiquvchi ma'lumotlar:

Ikkita butun son — shar necha marta devorga urilishi va qaysi teshikka tushishini chiqaring.

Izoh:

.

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

D. Metrodan foydalanish

Xotira: 32 MB, Vaqt: 1500 ms
Masala

Metro \(N\) ta bekatdan va \(M\) ta bekatlarni o‘zaro bog‘lovchi yo‘llardan tashkil topgan. Agar \(u\) va \(v\) bekatlar orasida yo‘l mavjud bo‘lsa, unda \(u\) dan \(v\) ga yoki \(v\) dan \(u\) ga 1 daqiqada yetib borsa bo‘ladi.

Toshkent shahriga ko’chib kelgan Davlatbek metrodan ko‘p foydalana boshladi. Xususan bugun, Davlatbek \(Q\) marta metrodan foydalanmoqchi. \(i\)-foydalanishida \(a_i\) bekatdan \(b_i\) bekatga borishi haqida aniq reja qildi. Agar metroni kutish va metro almashtirish vaqti inobatga olinmasa, Davlatbek har bir metrodan foydalanishida minimal necha daqiqa vaqtini metroda o‘tkazadi? Agar \(i\)-foydalanishi imkonsiz bo‘lsa −1 chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(N\) va \(M\) \((2≤N≤300,1≤M≤ \dfrac{N(N−1)}{2})\) bekatlar soni va bekatlar orasidagi yo‘llari soni kiritiladi.

Keyingi \(M\) ta qatorda ikkitadan butun son - \(u_i\) va \(v_i(1 ≤ v_i, u_i ≤ N )\) kiritiladi. Bu \(u_i\) va \(v_i\) bekatlar orasida yo‘l mavjud ekanligini anglatadi.

So‘ng yangi qatorda yagona butun son - \(Q(1 ≤ Q ≤ 300)\) Davlatbekning bugun metrodan foydalanishlari soni kiritiladi.

Keyingi \(Q\) ta qatorda ikkitadan butun son - \(a_i\) va \(b_i(1 ≤ a_i, b_i ≤ N )\), \(i\)-foydalanishdagi kirish va chiqish bekatlari kiritiladi.

Chiquvchi ma'lumotlar:

\(i\)-foydalanish uchun \(i\)-qatorda \(a_i\) bekatdan \(b_i\) bekatga yetib borish uchun ketadigan minimal vaqtni chiqaring. Buning imkoni bo‘lmasa \(−1\) chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 1
1 2
2
1 2
1 2
 
1
1
2 
3 3
1 3
1 2
2 3
5
2 1
1 2
3 2
2 1
2 2
 
1
1
1
1
0

E. Yangi yil sovg‘alari

Xotira: 64 MB, Vaqt: 3000 ms
Masala

Qorbobo va Qorqiz \(n\) ta yangi yil sovg‘asini bolalarga yetkazishi kerak. \(i\)-sovg‘ani Qorqiz \(a_i\) daqiqada tayyorlaydi, Qorbobo tayyor bo’lgan sovg’ani egasiga yetkazib berish uchun \(b_i\) daqiqa vaqt sarflaydi. Qorboboning xaltasiga bittadan ortiq sovg‘a sig‘maydi. Qorqiz ham bir vaqtni o‘zida bitta sovg‘ani tayyorlay oladi. Qorbobo va Qorqiz eng minimal qancha daqiqada barcha sovg‘alarni yetkaza olishadi?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(n (1 ≤ n ≤ 2 * 10^5)\) kiritiladi.
Ikkinchi qatorda \(n\) ta butun son - \(a\) massiv elementlari \((1 ≤ a_i ≤ 10^9)\) kiritiladi.
Uchinchi qatorda \(n\) ta butun son - \(b\) massiv elementlari \((1 ≤ b_i ≤ 10^9)\) kiritiladi.

Chiquvchi ma'lumotlar:

Bitta butun son - barcha sovg‘alarni yetkazish uchun ketadigan minimal vaqtni chiqaring.

Izoh:

1-testga izoh:

Birinchi navbatda, Qorqiz 1-sovg‘ani tayyorlaydi. So‘ng Qorbobo sovg‘ani yetkazadi, bu vaqtda esa Qorqiz 3-sovg‘ani tayyorlaydi. Qorbobo 3-sovg‘ani yetkazayotgan payti esa Qorqiz 2-sovg‘ani tayyorlaydi. Va nihoyat Qorbobo 2-sovg‘ani o‘z egasiga eltadi. Bunda ular 17 daqiqa vaqt sarflashadi. Bu eng minimal vaqt ekanligini isbotlasa bo‘ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
1 3 4
4 2 10
 
17
2 
5
4 4 30 6 2
5 1 4 30 3
 
47

F. Qurilmalar yetkazish

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Asilbekning maktabida yangi kompyuter sinfi tashkillashtirildi. Ushbu xonani jihozlash maqsadida maktab ma’muriyati umumiy miqdori \(N\) ta: kompyuter, monitor, printer, skaner, proyektor kabi yangi qurilmalar buyurma qildi.

Endilikda yetkazish xizmati bu qurilmalarning barchasini maktabga yetkazib berishi lozim.

Qurilmalarni bezarar yetkazish uchun, yetkazib berish xizmati, bitta ishchi avtomobiliga ko‘pi bilan \(K\) ta qurilma joylashtira oladi. Bunda qurilma turi muhim emas. Barcha qurilmalarni bir qatnashda yetkazish uchun, yetkazib berish xizmati eng kamida nechta avtomobilni ishga tushirishi lozim?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(N(1 ≤ N ≤ 10^9)\) kiritiladi.
Ikkinchi qatorda bitta butun son - \(K(1 ≤ K ≤ 10^9)\) kiritiladi.

Chiquvchi ma'lumotlar:

Ishga tushirish kerak bo‘lgan eng kam ishchi avtomobillar sonini chiqaring.

Izoh:

.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
12
3
 
4
2 
5
2
 
3

G. Sonlar va bitlar

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga \(n\) soni beriladi. Siz shunday \(a\) sonini topingki, u \(n = a + \text{popcount}(a)\) shartni qanoatlantirsin. Bunda \(\text{popcount}(x) - x\) sonining ikkilik sanoq sistemasida ifodalanishidagi 1 lar sonidir.

Kiruvchi ma'lumotlar:

Yagona qatorda bitta butun son - \(n(1 ≤ n ≤ 10^{18})\) kiritiladi.

Chiquvchi ma'lumotlar:

Shartni qanoatlantiruvchi istalgan butun \(a\) sonini chiqaring. Bunday son mavjud bo‘lmasa -1 chiqaring.

Izoh:

1-testda, shartni qanoatlantiruvchi \(a\) soni yo‘q ekanligini isbotlash mumkin.
2-testda, \(9_{10}\) = \(1001_2\). Ko‘rinib turibdiki, \(\text{popcount}(9)\) = \(2\). \(11 = 9 + 2\). Demak, 9 soni shartni qanoatlantiradi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
 
-1
2 
11
 
9

H. Antiqa satr

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Quyidagicha antiqa satr mavjud:

\(11010010001000010000010000001000000010...\)
(\(...\) bu yerda satr cheksiz davom etishini anglatadi).

Sizning vazifangiz juda oddiy, shu satrning \(k\)-belgisini topish.

Kiruvchi ma'lumotlar:

Yagona qatorda bitta butun son - \(k(1 ≤ k ≤ 10^{18})\) kiritiladi.

Chiquvchi ma'lumotlar:

Antiqa satrning \(k\)-belgisini ekranga chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
 
1
2 
6
 
0

I. Tosh uloqtirish

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Tosh uloqtirish sporti bo‘yicha sportsmen Asilbek hozirda musobaqaga tayyorgarlik ko‘rayapti.
Navbatdagi mashq sifatida u toshni uzoqlikka otish, aniqrog‘i 0 nuqtadan turib \(x\) nuqtaga otishni tanladi. Va albatta u buni 1 otishda bajarishi kerak. Asilbek toshni uzoqlikka otish uchun 3 ta: yo‘nalishni, \(a\) hamda \(b\) parametrlarni tanlaydi. Bunda u toshni tanlagan yo‘nalishida (o‘ngga yoki chapga) \(a * b\) masofaga otadi.

Lekin bu mashq oson bo‘lmasligi uchun Asilbek \(a\) va \(b\) parametrlarni, \(l_1 ≤ a ≤ r_1\) va \(l_2 ≤ b ≤ r_2\) shartlarni qanoatlantirishini istaydi.

Sizning vazifangiz Asilbek 0 nuqtadan turib 1 urinishda toshni \(x\) nuqtaga ota olishi uchun parametrlarni tanlab berish. To‘g‘ri javob bir nechta bo‘lsa istalganini chiqaring. Agar shartlarni qanoatlantiradigan parametrlarni tanlashning iloji bo‘lmasa “Impossible” deb chiqaring.

Kiruvchi ma'lumotlar:

Yagona qatorda beshta butun son - \(x(−10^{12} ≤ x ≤ 10^{12})\), \(l_1,r_1(0 ≤ l_1 ≤ r_1 ≤ 10^{14})\), \(l_2, r_2(0 ≤ l_2 ≤ r_2 ≤ 10^{14})\) kiritiladi.

Chiquvchi ma'lumotlar:

Shartlarni qanoatlantiruvchi 3 ta: yo‘nalishni, \(a\) va \(b\) parametrlarni chiqaring.
Birinchi qatorda yo‘nalishni ingliz tilida chiqaring: Chapga - Left, O‘ngga - Right.
Ikkinchi qatorda \(a\) va \(b\) butun sonlarni chiqaring.
Shartlarni qanoatlantiruvchi parametrlar bir nechta bo`lsa, istalganini chiqaring. Bunday parametrlar mavjud bo‘lmasa “Impossible” deb chiqaring.

Izoh:

1-testda, \(x\) manfiy bo‘lgani uchun Asilbek chap tomonga otishi aniqdir. Bunda u \(a = 6\) va \(b = 1\) ni tanlay oladi. Chunki \(3 ≤ 6 ≤ 7\) va \(1 ≤ 1 ≤ 4\). Xuddi shu sabab bilan u \(a = 3\) va \(b = 2\) ni tanlashi mumkin edi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
-6 3 7 1 4
 
Left
6 1
2 
4 2 2 3 4
 
Impossible
3 
0 0 12 3 4
 
Right
0 3

J. Muzqaymoq do‘konidagi avtomat

Xotira: 16 MB, Vaqt: 1000 ms
Masala

“Ice&Dance” muzqaymoq do‘koni o‘z mahsulotlari shirinligi tufayli bugungi kunda juda mashhur. Bu do‘konda \(N\) turdagi muzqaymoq turlari mavjud (mevali muzqaymoq, qaymoqli muzqaymoq, shokoladli muzqaymoq va h.k.). \(i\)-turdagi muzqaymoqning narxi mos ravishda \(c_i\) dir.

Do‘kondagi muzqaymoqlar shunchalik mazzaliki, xaridorlar iloji boricha barcha pulini muzqaymoq xaridiga ishlatishga harakat qiladi. Lekin so‘nggi kunlarda xaridorlar muzqaymoq tanlashda qiynalayotgani sababli do‘konda xizmat ko‘rsatish jaroyoni sekinlashib ketdi.

Yaqinda, do‘kon egasining buyurtmasiga ko‘ra, do‘konga maxsus avtomat olib kelishdi. Ushbu avtomatga xaridor hamyonidagi pul miqdorini kiritishi bilan unga pulini maksimal darajada sarflovchi xaridni ko‘rsatadi.

Bugun do‘konga \(Q\) nafar xaridor kelishi ma’lum, hamda k-xaridor o‘zi bilan ak miqdorda pul olib keladi. Bunda har bir xaridor maxsus avtomatdan foydalanishi aniq.

Sizning vazifangiz shu avtomat dasturini yaratishdir. Boshqa so‘zlar bilan aytganda, har bir xaridor uchun uning pulini maksimal darajada sarflovchi xaridga misol keltirishdir. Agar xaridor pulini maksimal darajada ishlatuvchi xaridlar bir nechta bo‘lsa, istalganini chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(N(1 ≤ N ≤ 100)\) muzqaymoq turlari soni kiritiladi. Keyinga qatorda \(N\) ta butun son - \(c\) massiv elementlari kiritiladi. \(c_i(1 ≤ c_i ≤ 1000)\) mos

ravishda \(i\)-turdagi muzqaymoqning narxi.
Bundan so‘ng yangi qatorda bitta butun son - \(Q(1 ≤ Q ≤ 100)\) xaridorlar soni kiritiladi.

Keyingi qatordan \(Q\) ta butun son - \(a\) massiv elementlari kiritiladi. \(a_k\)\((1 ≤ a_k ≤ 3000)\) mos ravishda \(k\)-inchi xaridorning hamyonidagi pul miqdori.

Chiquvchi ma'lumotlar:

Har bir xaridor uchun 2 qator natija chiqaring: 

  • birinchi qatorda \(a_k\) pul miqdoridan sarflash mumkin bo‘lgan eng maksimal pul miqdori;
  • ikkinchi qatorda \(N\) ta butun son. \(i\)-son shu xaridor \(i\)-turdagi muzaqaymoqdan nechta olishi kerakligi.

Agar xaridor pulini maksimal darajada sarflovchi xaridlar bir nechta bo‘lsa, istalganini chiqaring.

Izoh:

1-testda:
Birinchi xaridor 4 birlik pul olib keladi. U pulini to‘liq sarflovchi turli xil xaridlar qilishi mumkin. U muzqaymoqning 5-turidan bitta yoki 2-turidan ikkita olishi mumkin. Yoki 2- turidan bitta hamda 4-turidan bitta xarid qilishi mumkin.
Uchinchi xaridor olib kelgan pul miqdori hech qaysi muzqaymoqga yetmaydi, shuning uchun uning xarid turi yagona: muzqaymoqning barcha turidan 0 dona, yani olmaslik.

2-testda:
Birinchi xaridor 7 birlik pul bilan keladi. Afsuski, u hech qanday usul bilan barcha 7 birlik pulini ishlata olmaydi. Ammo 4 birlik ishlatishi mumkin. Buning uchun istalgan muzqaymoqdan bitta olishi kerak.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
3 2 12 2 4
7
4 4 7 1 9 3 16
 
4
0 0 0 0 1 
4
0 1 0 1 0 
7
1 0 0 2 0 
0
0 0 0 0 0 
9
1 2 0 1 0 
3
1 0 0 0 0 
16
0 2 1 0 0
2 
3
4 4 4
2
7 16
 
4
0 1 0 
16
1 1 2
Kitob yaratilingan sana: 05-May-24 05:42