A. Sandvich

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Zarif har kuni nonushta uchun sandvich yeyishni yaxshi ko'radi. U sandvichni faqat non, kolbasa va pishloqdan tayyorlaydi. Sandvich formulasi quyidagicha:

  • non bo'lagi
  • kolbasa yoki pishloq bo'lagi
  • non bo'lagi
  • . . .
  • kolbasa yoki pishloq bo'lagi
  • non bo'lagi

Bugun Zarifning muzlatkichida a bo'lak non, b bo'lak kolbasa va c bo'lak pishloq bor. Zarif eng ko'pida necha qavatli sandvich tayyorlay olishini chop eting

Kiruvchi ma'lumotlar:

Kirish faylida 3 ta butun son a, b, c (1 ≤ a, b, c ≤ 100) kiritiladi.

Chiquvchi ma'lumotlar:

Sandvichning maksimum balandligini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 1 1
 
3
2 
10 1 2
 
7
3 
9 4 4
 
17

B. Qorbola

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Zarif va Sunnat qadrdon do'stlar. Bugun ham ikkisi birga o'ynash uchun ko'chaga chiqishdi. Ko'cha oppoq qorga belangan va qorning hajmi x ga teng. Ular birgalikda qorbola yasashmoqchi bo'ldi.  Zarif telefonda  gaplashayotgan vaqt Sunnat k hajmli qor to'pi yasadi. Zarif endi shu to'pni ishlatgan holda qorbola yasashga majbur, aks holda Sunnat hafa bo'lishi mumkin. 

Qorbola 3 ta qorto'pidan yasaladi va pastdagi qorto'pi yuqoridagi qorto'pidan aynan 2 baravar katta bo'lishi kerak aks holda qorbola qulab tushadi.

x va k sonini bilgan holda maksimum qancha hajmli qorbola yasash mumkinligini aniqlang.

Eslatma! Zarif Sunnat yasagan qorto'pining hajmini o'zgartira olmaydi.

Kiruvchi ma'lumotlar:

yagona qatorda ikkita butun son - x va k kiritiladi

1 ≤ k ≤ x ≤ 100 000

Chiquvchi ma'lumotlar:

Yasash mumkin bo'lgan maksimum hajmdagi qorbolaning hajmini 1000 ga ko'paytirgan holda chop eting.

Izoh:

Agar qorbola yasash imkoniyati mavjud bo'lmasa 0 chop etilsin.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
10 2
 
7000
2 
16 2
 
14000

C. O'q

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Askar yerdan \(H\) metr yuqoridan turib yerga nisbatan\(\alpha^\text{o}\) burchak ostida o'q uzdi. O'q \(v \ m/s\) tezlik bilan otilib chiqdi. Agar yerni to'liq tekis hamda havoning qarshiligi yo'q deb tasavvur qilsak, o'q necha metr masofada yerga tushadi. (\(g=9.81 \ m/s^2\))

Kiruvchi ma'lumotlar:

Kirish faylida 3 ta butun son - \(H\), \(\alpha\), va \(v\) kiritiladi.

\(1 \le H \le 10^3\)

\(0 < \alpha < 90\)

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

Chiquvchi ma'lumotlar:

Yerga tushgan o'q va askar orasidagi masofani toping. Javobni nuqtadan keyingi 4 xona aniqligida chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 42 13
 
19.9888
2 
5 84 41
 
36.1449

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. Matematikani yomon ko'raman

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Biloliddin matematikani juda yomon ko'radi va matematika darsda har doim uxlaydi. Bugun ham xuddi shu ahvol: o'qituvchi "tagma-tag qo'shish" usulini o'rgatmoqda, Biloliddin esa shirin uyquda.  Endi doskadagi misolni ishlashi kerak. Biloliddin ushbu vazifani quyidagicha hal qildi:

ya'ni u ortiqcha sonlarni keyingi xonaga qo'shish o'rniga yonma-yon yozib qo'ydi. Ustozi esa Biloliddinni jazolash maqsadida n sonini berdi va u ishlagan usul yordamida yuqoridagi nomanfiy ikkita sonni necha xil usulda tanlash mumkinligini hisoblashni vazifa qilib berdi.  

Biloliddin sizdan yordam so'ramoqda. Unga yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida n soni kiritiladi.

1 ≤ n ≤ 10^18

Chiquvchi ma'lumotlar:

Tanlashlar sonini chop eting.

Izoh:

1-test uchun sonlarni quyidagicha tanlash mumkin: 

(0, 112), (1, 111), (2, 110), (3, 19), (4, 18), (5, 17), (6, 16), (7, 15), (8, 14), (9, 13), (10, 102), (11, 101), (12, 100), (13, 9), (14, 8), (15, 7), (16, 6), (17, 5), (18, 4), (19, 3), (20, 92), (21, 91), (22, 90), (30, 82), (31, 81), (32, 80), (40, 72), (41, 71), (42, 70), (50, 62), (51, 61), (52, 60), (60, 52), (61, 51), (62, 50), (70, 42), (71, 41), (72, 40), (80, 32), (81, 31), (82, 30), (90, 22), (91, 21), (92, 20), (100, 12), (101, 11), (102, 10), (110, 2), (111, 1) va (112, 0).

(3, 19) va (19, 3) alohida kombinatsiya hisoblanadi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
112
 
50
2 
366
 
196

F. Batalyon

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Harbiy bazada N ta batalyon mavjud. i-batalyon A[i] ta askardan tashkil topgan. Batalyonlar tartib bilan joylashgan, ya'ni 1-batalyon eng oldinda, N-batalyon esa eng oxirida joylashadi. Harbiy bazaga Q kun davomida dushmanlar bostirib keladi, ya'ni j-kuni B[j] ta qo'shindan tashkil topgan dushman askarlari hujumga keladi. Batalyonlar birin-ketin dushmanga qarshi chiqadi. Agar dushman soni batalyondagi askarlar sonidan kam bo'lmasa, batalyon butunlay yo'q bo'lib ketadi va keyingi batalyon dushman tomon boradi. Agar barcha batalyon qirilib ketsa (dushman askarlari g'alaba qildim deb o'ylab bu jang maydonini tark etishadi), kun oxirida ular o'rniga xuddi shuncha askarlardan tashkil topgan batalyonlar tashkil qilinadi .  Har bir kun uchun kun oxirida nechta batalyon qolganini chop eting.

Bitta askar faqat bitta dushmanga qarshi chiqa oladi va ikkisi ham halok bo'ladi, ya'ni 4 ta dushman askari bo'lsa va batalyondagi askarlar soni 10 ta bo'lsa, hujumdan so'ng batalyonda 6 kishi tirik qoladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va Q batalyon va hujum kunlari soni kiritiladi.

Keyingi qatorda N ta butun son Ai elementlari kiritiladi.

Keyingi qatorda Q ta butun son Bi elementlari kiritiladi.

1 ≤ N, Q ≤ 100 000

1 ≤ Ai ≤ 1 000 000 000

1 ≤ Bi ≤ 10^18

Chiquvchi ma'lumotlar:

Har bir kun uchun kun so'ngida nechta batalyon tirik qolganini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8 4
2 10 5 9 9 4 5 8 
18 19 12 2
 
5
3
1
1
2 
4 4
2 3 1 2
6 1 4 4
 
1
1
4
3

G. Good binary tree

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Full binary tree - har bir tugun uchun bolalari 0 yoki 2 ta bo'lgan va har bir tuguni 1 dan K gacha raqamlangan tree hisoblanadi. Bunda K - daraxtdagi tugunlar soni.

A tugun B tugundan katta deyiladi - agar A tugunning tartib raqami B tugunning tartib raqamidan katta bo'lsa.

Tugunning balandligi deb shu tugundan boshlab ildiz tugungacha bo'lgan masofaga aytiladi.

Good binary tree deb quyidagicha xususiyatli tree ga aytiladi:

  • Har bir tugun uchun, agar uning bolalari mavjud bo'lsa, shu tugun bolalaridan kichik;
  • Har bir tugun uchun, agar uning bolalari mavjud bo'lsa, shu tugunning chap tomonidagi eng katta tugun o'ng tomonidagi eng kichik tugundan kichik;

Sizga Good Binary tree barglarining balandliklari berilgan. Good Binary Tree qanday bo'lishini aniqlang.

Kiruvchi ma'lumotlar:

1-qatorda N butun soni - barglar soni kiritiladi.

Keyingi qatorda N ta butun son har bir barg balandligi berilgan. E'tibor bering barglar chapdan o'ngga qarab tartiblangan.

2 ≤ N ≤ 50 000

Kiritilgan ma'lumotlarda har doim javob mavjudligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Birinchi qatorda daraxtdagi tugunlar sonini chop eting.

Keyingi qatorda daraxtni chop eting. Bunda i-raqam i-tugunning otasi bo'lishi kerak. Ildiz tugunning otasi bo'lmaganligi sababli ildiz ning otasini 0 deb oling.

Izoh:

2-test uchun Good Binary Tree ning vizual ko'rinishi:

rasmda 4 bilan 3 ni joyi almashib qolgan. Keyin to'g'rilaymiz!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
1 2 2
 
5
0 1 1 3 3
2 
7
2 2 2 5 5 4 3
 
13
0 1 2 2 1 5 5 7 8 9 9 8 7
3 
8
1 3 4 4 3 4 5 5
 
15
0 1 1 3 4 4 6 6 3 9 9 11 11 13 13

H. Satrni tiklash

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga satr berilgan. Satr ustida quyidagi amalni istalgancha bajarish mumkin:

  • Satrning boshidan k ta belgini o'chiring
  • Satrning oxiriga istalgan k ta belgini qo'shing (belgining satr ichida bor-yo'qligi muhim emas)

Ushbu amaldan istalgan miqdorda - foydalanishga ruxsat berilsa, minimum necha qadamda satrni dastlabki holatga qaytarish mumkin?

Kiruvchi ma'lumotlar:

Yagona qatorda lotin alifbosining kichik harflaridan iborat S satri kiritiladi. Satr uzunligi 1 000 000 dan oshmaydi

Chiquvchi ma'lumotlar:

0 ga teng bo'lmagan minimum amallar sonini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
abcabacd
3
 
3
2 
abacaba
3
 
2

I. Qalamlar

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Zarif juda injiq bola. Bugun unga onasi N ta qalam olib berdi. Zarif ulardan uchburchak shaklini yasashni xohlaydi. Bunda qalamlar uchburchak tomonlari bo'lib xizmat qiladi. Agar u tanlagan qalamlaridan uchburchak yasay olmasa injiqligi boshlanadi. Shu sabab onasi undan bir nechta qalamlarni bildirmasdan olib qo'ymoqchi, shundan so'ng Zarifda iloji boricha ko'proq qalam qoladi va istalgan 3 ta qalamdan uchburchak yasash mumkin bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son N - qalamlar soni kiritiladi.

Keyingi qatorda N ta butun son kiritiladi, bunda i-son i-qalamning uzunligini anglatadi.

5 ≤ N ≤ 100 000

1 ≤ A[i] ≤ 1 000 000 000

Chiquvchi ma'lumotlar:

Yuqoridagi shartlar bajarilsa, Zarifda maksimum nechta qalam qolishini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8
16 7 14 13 11 20 13 7
 
6
2 
20
18 89 74 86 48 12 58 80 60 31 47 100 64 12 21 70 25 75 86 36
 
12
3 
5
27 26 52 29 26
 
4

J. O'quv mashg'uloti

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Bugun N ta askarlar o'quv-mashg'ulot maydoniga amaliyot uchun kelishdi. Maydonning omborxonasida 1 dan M gacha raqamlangan M turdagi avtomat mavjud. Har bir askar A[i] turdagi avtomatda mashg'ulot o'tkazishni xohlaydi. Maydonda K ta otish maydonchasi mavjud. Kichik maydonchalarning har birida 1 kishi faqatgina bitta avtomatdan foydalangan holda mashg'ulot o'tkaza oladi. Boshida hamma kichik maydonchalar bo'sh. 

i-askarning navbati kelgan vaqt agar kichik maydonchalarning birortasida u yoqtirgan turdagi avtomat bo'lsa, shu maydonchada mashg'ulot o'tkazadi. Mavjud bo'lmasa, omborxonadan o'zi yoqtirgan turdagi avtomatni olib chiqadi hamda istalgan bo'sh maydonga joylashtiradi. Agar hamma maydoncha band bo'lsa, istalgan birorta maydonchada turgan qurolni omborxonaga qo'yib o'zi istagan turdagi qurolni joylashtirishi mumkin. Eski qurolni omborxonaga qo'yish va yangisini olib kelish uchun bir marta borib kelish kifoya (borishda eskisini tashlab, qaytayotganda yangisini olib keladi). Mashg'ulotni tugatgandan so'ng, qurol shu maydonchada qoladi.

Har bir askar navbatma-navbat mashg'ulot o'tkazsa va optimal harakat qilishsa, eng kamida necha marotaba omborxonaga borish kerak bo'ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda 3 ta butun son M, K, N - qurollar soni, kichik maydonchalar soni va askarlar soni kiritiladi.

Keyingi qatorda M ta butun son kiritiladi, i-son i-askar qaysi avtomatni yoqtirishini ifodalaydi.

1 ≤ M ≤ 500 000

1 ≤ K ≤ N  ≤ 100 000

Chiquvchi ma'lumotlar:

Barcha askar optimal harakat qilsa, minimum necha marta omborxonaga borish kerak bo'lishini chop eting.

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

K. Qo'yxona

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Cho'ponning N ta qo'yxonasi bor. Qo'yxonalar \(1\) dan \(N\) gacha raqamlangan. Har bir qo'yxona qo'ylarni o'g'ri va bo'rilardan himoyalash maqsadida qalin devor bilan o'ralgan, va eshiklari qulflangan. Har bir qo'yxonaning kaliti boshqa bir qo'yxonaga joylangan. Kalitni olish uchun, agar u qo'yxona eshigi yopiq bo'lsa, devordan oshib o'tish orqali olish mumkin.

Qo'ylarning hammasini tashqariga chiqarish uchun kamida nechta devor oshishga to'g'ri keladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N (1 \le N \le 10^6)\) - qo'yxonalar soni kiritiladi.

Keyingi \(N\) ta qatorning har birida bittadan butun son kiritiladi. \(i\)-son \(i\)-qo'yxona kaliti qaysi qo'yxonada joylashganini anglatadi.

Chiquvchi ma'lumotlar:

Buzilishi kerak bo'lgan minimal devor oshishlar chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
2
1
2
4
 
2
Kitob yaratilingan sana: 22-Nov-24 20:27