A. Talabalar jamoasi

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Har yili TATU universiteti ICPC musobaqasini tashkil qiladi. Har bir jamoa uchta talabadan iborat.
Bu yil har bir jamoa aynan ikki o‘g‘il va bitta qizdan iborat bo‘lishi belgilandi.
Bundan tashqari universitet dekani talabalardan K tasini uzoq davlatga amaliyotga yuborishga qaror qildi. Bu talabalar musobaqada qatnasha olmaydi.
Universitetdagi o'g'il va qiz bolalar soni, shuningdek amaliyotga yuborilishi kerak bo'lgan talabalar sonini bilgan holda, eng ko'p nechta jamoa musobaqada qatnashishi mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

Yagona qatorda uchta butun son N, M, K - mos ravishda o'g'il bola talabalar soni, qiz talabalar soni va amaliyotga yuboriladigan talabalar soni kiritiladi.

\(0 \le N, M \le 100\)

\(0 \le K \le N+M\)

Chiquvchi ma'lumotlar:

Maksimal jamoalar sonini chop eting.

Izoh:

1-test holati uchun: 2 ta o'g'il talaba va 1 ta qiz talaba amaliyotga jo'natilsa, 7 ta o'g'il va 3 ta qiz qoladi. Bunda 3 ta jamoa tashkil qilish mumkin (1 ta bola sheriksiz qoladi va jamoa hosil qila olmaydi).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
9 4 3
 
3
2 
2 1 1
 
0

B. Olma yig'ish

Xotira: 256 MB, Vaqt: 1000 ms
Masala

N ta savatcha ketma-ket qo'yilgan. Har bir savatchada ikkitadan olma bor. Olmalarning 5 xil navi mavjud.

Sardor imkon qadar ko'proq olmaga ega bo'lmoqchi. Bu uchun u quyidagi ishni qiladi: qaysidir \([l, r]\) oraliqni tanlaydi, oraliqdagi har bir savatchadan aynan 1 dona olma oladi. Yakunda u to'plagan barcha olma bir xil navli bo'lishi kerak. Sardor ko'pi bilan qancha olmaga ega chiqishi mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(N\) - savatchalar soni kiritiladi.

Har bir olma 1 dan 5 gacha butun son bilan ifodalanadi. Bunda bir xil raqamli olmalar bir xil navli hisoblanadi.

Keyingi N ta qatorning har birida ikkitadan butun son - savat ichidagi ikkita olma navi kiritiladi.

\(1 \le N \le 10^5\)

Chiquvchi ma'lumotlar:

Erishish mumkin bo'lgan maksimal olmalar soni va olmaning navini chop eting. Agar bir nechta javob mavjud bo'lsa, navi bo'yicha qiymati eng kichigini chop eting.

Izoh:

(l, r) oraliqni faqat bir martagina tanlash mumkin.

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

C. Kitoblarni taxlash

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Shohruhda 1 dan N gacha ketma-ket raqamlangan N ta kitobi bor. Har bir kitobning raqami turlicha. Hozir uning kitoblari javonda ustma-ust turibdi. Shohruh kitoblarni tartiblamoqchi. Buning uchun u quyidagi ishni qilishi mumkin:

  • Qaysidir kitobni olish va uni eng yuqoridagi kitob ustidan qo'yish.

Shohruhga kitoblarini o'sish tartibida taxlashi uchun minimal amallar sonini chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son N - kitoblar soni kiritiladi.

Keyingi N ta qatorning har birida 1 tadan butun son kiritiladi. Bunda birinchi kiritilgan son - eng yuqoridagi, eng oxirgi kiritilgan son esa eng pastdagi kitobning raqami hisoblanadi.

\(1 \le N \le 3 \times 10^5\)

Chiquvchi ma'lumotlar:

Minimal operatsiyalar sonini chop eting.

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

D. Omadli son

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Azizbek o'zi uchun bir nechta raqamlarni tanlab oldi. \(X\) soni faqatgina u tanlagan raqamlardan tashkil topgan bo'lsa omadli, aks holda omadsiz deb atadi. Azizbekning fikriga ko'ra K-musbat omadli sonni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son \(N\) - Azizbek tanlab olgan raqamlar soni.

Keyingi qatorda \(N\) ta raqam kiritiladi. Kiritilgan raqamlar \([1, 9]\) oralig'ida hamda raqamlar takrorlanmaydi.

Keyingi qatorda butun son \(K\) kiritiladi.

\(2 \le N \le 9\)

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

Chiquvchi ma'lumotlar:

Chiqish faylida bitta butun son - Azizbek o'ylagan K-omadli sonni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
5 8
4
 
58
2 
9
1 2 3 4 5 6 7 8 9
10
 
11
3 
4
3 8 1 4
10
 
33

E. Kim ko'p go'sht yeydi?

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Kim ko'p go'sht yeyish musobaqasida ishtirokchilar 1 dan N gacha raqamlangan. Bu odamlar allaqachon ko'p go'sht iste'mol qilishgan: \(k-\) odam hozirgacha \(A_k\) kilogramm go'sht iste'mol qilgan. Zarif go'shtni \(B_1 : B_2 : … : B_N\) nisbatida odamlarga aynan shu tartibda tarqatadi, lekin u tarqatadigan go'shtning umumiy miqdorini hali bilmaydi. .
Musobaqa oxirida “yilning eng go'shtxo'r odamlari reytingi” e'lon qilinadi. Reyting ro'yxati ishtirokchilar iste'mol qilgan go'shtning umumiy vazniga qarab tuziladi. Zarif tarqatish uchun go'sht miqdorini tanlash orqali ushbu ro'yxatga ta'sir qilishi mumkin. Zarifga ko‘p marta pora taklif qilingan bo‘lsa-da, u har safar halol inson ekanini aytib, rad javobini bergan.

Natijalar quyidagicha hisoblanadi: ko'p go'sht yegan inson teparoqda bo'ladi, agar ikki ishtirokchi yegan go'sht miqdori bir xil bo'lsa, tartib raqami kichikroq ishtirokchi yuqoriroqda deb hisoblanadi.
Zarif tartib haqida o'ylaydi, shu sabab mos ravishda \(i-\)o'rinni olgan ishtirokchining raqami  \(i\) ga teng bo'lishi kerak. Zarifga niyatiga erishish uchun tarqatadigan go'sht miqdorini (yuqorida aytib o'tilgan nisbatda) tanlashga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda N butun soni kiritiladi.

Keyingi N ta qatorning har birida 2 tadan butun son - \(A_i\) va \(B_i\) kiritiladi.

\(2 \le N \le 1000\)

\(0 \le A_i, B_i \le 10^6\), kamida bitta 0 dan katta \(B_i\) bo'lishi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida go'shtning kerakli miqdorini 5 xona aniqlikda chop eting. Agar yechim mavjud bo'lmasa -1 ni chop eting. Bir nechta javob mavjud bo'lsa, istalganini chop eting. Siz chop etgan javob qiymati \(10^9\) dan katta bo'lmasligi zarur.

Izoh:

1-testda: 10,5 kilogramm go'sht \(1: 2: 0\) nisbatda taqsimlanadi, bu bizga mos ravishda 3,5, 7 va 0 kilogramm ga taqsimlanadi. Agar buni allaqachon iste'mol qilingan go'sht miqdoriga qo'shsak, ishtirokchilar jami 10,5, 10 va 10 kilogramm iste'mol qilishgan bo'ladi, bu to'g'ri tartibdir.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
7 1
3 2
10 0
 
10.5
2 
5
15 4
6 7
12 5
9 6
1 7
 
87
3 
3
2 1
4 0
0 3
 
-1

F. Xafalik darajasi

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Bolalar bog'chasiga saxiy amaki N ta konfet solingan katta qop sovg'a qildi. Konfetlar M nafar bolaga tarqatilishiga qaror qilindi.
Har bir bola o'zi xohlagan konfetlar sonini aytdi. Agar bolaga kerakli miqdordagi konfet berilmasa, u xafa bo'ladi. Aniqroq aytganda, u qo'lga kirita olmagan har bir konfet uchun xafa bo'ladi. Ba'zilarning fikriga ko'ra, bolaning xafalik darajasi mahrum bo'lgan konfetlar sonining kvadratiga teng bo'ladi. Misol uchun, agar Shahzoda 32 ta konfet xohlasa, lekin atigi 29 ta olsa, unga 3 ta konfet yetmaydi, shuning uchun uning xafaligi 9 ga teng bo'ladi.
Afsuski, barcha bolalar uchun yetarli miqdorda konfet mavjud emas. Shuning uchun, konfetlar bolalarning xafaligi yig'indisi minimal bo'ladigan tarzda taqsimlanishi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son N va M - konfetlar soni va bolalar soni kiritiladi.

Keyingi N ta qatorning har birida bittadan butun son - har bir bola xohlagan konfet miqdori kiritiladi. Kiritilgan sonlarning umumiy qiymati \(2 \times 10^9\) dan oshmaydi va har doim N dan katta bo'ladi.

\(1 \le N \le 2 \times 10^9\)

\(1 \le M \le 10^5\)

Chiquvchi ma'lumotlar:

Bolalarning minimum xafalik darajasini chop eting.

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

G. Toshlar bilan o'yin

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Shohruh va Farrux sevimli mashg'uloti matematik o'yin o'ynashmoqda. Bu safar ular n ta toshni qopga solib, quyidagicha o'ynashdi:

  • Shohruh birinchi bo'lib boshlaydi, keyin Farrux, keyin yana Shohruh, keyin Farrux va hokazo;
  • Shohruh birinchi harakatida qopdan istalgan miqdordagi toshlarni (1 dan N gacha) olishi mumkin;
  • Keyingi yurishlarning har birida o'yinchi kamida 1 ta tosh olishi kerak va oldingi yurish paytida olingan toshlar miqdoridan ko'pi bilan ikki baravar ko'p olishiga ruxsat beriladi; tabiiyki, qopda qolgan miqdordan ko'proq tosh olish mumkin emas;
  • Oxirgi toshni olgan o'yinchi g'olib hisoblanadi.

Shohruh ham, Farrux ham optimal o'ynashadi (agar bir o'yinchi ikkinchisini mag'lub etishi mumkin bo'lsa, u o'yinchi doimo g'alaba qozonadi). Biz Shohruhning o'yinda g'alaba qozonishi kafolatlaydigan birinchi yurishi uchun minimal toshlar sonini topishimiz kerak.

Kiruvchi ma'lumotlar:

Yagona qatorda butun son N - toshlar soni kiritiladi.

\(2 \le N \le 10^{15}\)

Chiquvchi ma'lumotlar:

Minimal toshlar sonini chop eting.

Izoh:

1-test:

Biz barcha toshlarni olgan holda g'alaba qilishimiz mumkin. Lekin bu minimal emas. Agar biz 1 ta tosh oladigan bo'lsak, keyingi yurishda raqib nechta tosh olishidan qat'iy nazar g'alaba qilamiz.

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

H. Muharrir

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Farhod RealSoft kompaniyasida kichik bir dasturchi bo'lib ishlaydi. Uning har kungi qiladigan ishi eski kodlarni ochish va ularni boshliq aytganidek qaytadan formatlash. Formatlash quyidagicha: dastlab N qatorli eski kod olinadi. Koddagi har bir satr oldidan bir nechta bo'shliq mavjud (O'qishga oson bo'lishi uchun). Ba'zi bo'shliqlarni qo'shish yoki o'chirish orqali uni bosh dasturchi aytgan holatiga keltirishi zarur. Bu ish juda zerikarli.
Yaxshiyamki, uning muharriri ketma-ket qatorlar guruhini tanlash va har birining boshidan belgi qo'shish yoki o'chirish buyrug'iga ega. Farhodga kodni iloji boricha tezroq formatlashga yordam bering.
Sizga N qatorlar soni, har bir satr boshidagi bo'shliqlar sonini ko'rsatuvchi ketma-ketlik va har bir satr boshida kerakli sonli bo'shliqlarni ko'rsatuvchi ketma-ketlik beriladi.
Farhod quyidagi buyruqni istalgancha bajarishi mumkin:

  • istalgan qator ketma-ket qatorlarni tanlash
     
  •  tanlangan satrlarning har birining old qismiga bitta yorliq qo‘shish yoki o‘chirish
    Yuqoridagi ikkita amal tanlangan qatorlar sonidan qat'i nazar, bitta buyruqni o'z ichiga oladi.

Shuni ta'kidlash kerakki, satr boshida mavjud bo'lgandan ko'proq bo'shliqlarni satrdan o'chirish taqiqlanadi, chunki muharrir bo'shliqdan boshqa belgilarni o'chirishni boshlaydi.
Sizdan kodni tartibga solish uchun zarur bo'lgan minimal buyruqlar sonini hisoblashingiz so'raladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son N - koddagi qatorlar soni kiritiladi.

Keyingi qatorda N ta butun son \(A_i\) - har bir satr oldidagi bo'shliqlar soni kiritiladi.

Keyingi qatorda N ta butun son \(B_i\) - bosh dasturchi tomonidan aytilgan ketma-ketlik kiritiladi.

\(1 \le N \le 1000\)

\(0 \le A_i, B_i \le 80\)

Chiquvchi ma'lumotlar:

Kodni formatlash uchun ketuvchi minimal operatsiyalar sonini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
3 4 6
8 9 11
 
5
2 
4
5 1 3 4
3 4 1 0
 
9
3 
4
3 4 6 2
5 1 0 3
 
9
Kitob yaratilingan sana: 22-Nov-24 19:57