A. ShoxRUX

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Shoxruxga NxN shahmat doskasi berilgan. U bu shahmat doskada N ta ruxni joylashtirishi kerak-ki, ular bir-birini hujumi ostida bo'lmasin. Shoxrux bunday holatdagi barcha kombinatsiyalar sonini topmoqchi, unga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda 1 ta natural son, N\((1≤N≤10^3)\).

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1	1
2	2	2

B. C+=

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Isamatdin yangi dasturlash tilini, C+=, ishlab chiqdi. C+= tilida butun son o'zgaruvchilarini faqat "+=" amali yordamida o'zgartirish mumkin, ya'ni chap tomondagi o'zgaruvchiga o'ng tomondagi qiymat qo'shiladi. Masalan, "a += b" amalini bajarsak, agar a = 2 va b = 3 bo'lsa, a ning qiymati 5 ga o'zgaradi (b ning qiymati o'zgarmaydi).

Isamatdin katta butun sonlarni qayta ishlashni sinab ko'rmoqchi va a yoki b qiymati berilgan n qiymatidan katta bo'lishini xohlaydi. Isamatdin bu holatda nechta "+=" amali bajarilishi kerakligini aniqlamoqchi.

Kiruvchi ma'lumotlar:

Birinchi qatorda yagona butun son T \((1 ≤ T ≤ 100) \)— testlar soni beriladi.

Keyingi T qator har biri uchta butun sonni o'z ichiga oladi: a, b va n\( (1 ≤ a, b ≤ n ≤ 10^9)\) — a va b ning dastlabki qiymatlari hamda ularning biri oshirilishi kerak bo'lgan qiymat n.

Chiquvchi ma'lumotlar:

Har bir test uchun eng kam sonli "+=" amallarni ko'rsatib, natijani chiqarish kerak. Natijalarni alohida qatorlarga chiqaring.

Izoh:

Birinchi holda, biz o'zgaruvchini 3 dan oshib ketolmaymiz bitta operatsiyada. Ikki amalda bunga erishishning bir usuli "b += a" ni ikki marta bajarishdir.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 2 3 5 4 100	2 7

C. Taksi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Darslardan so'ng maktab o'quvchilarining n guruhi tashqariga chiqib, uning tug'ilgan kunini nishonlash uchun Robolandiyaga tashrif buyurishga qaror qilishdi. Biz bilamizki, i-guruh s[i] do'stlardan \(( 1 ≤ s[i] ≤ 4 )\) iborat va ular Robolandiyaga birga borishni xohlashadi. Ular u erga taksida borishga qaror qilishdi. Har bir mashina ko'pi bilan to'rtta yo'lovchini tashishi mumkin. Agar har bir guruhning barcha a'zolari bitta taksida yurishi kerak bo'lsa (lekin bitta taksi bir nechta guruhga borishi mumkin) bolalarga eng kam qancha mashina kerak bo'ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda butun son n \(( 1 ≤ n ≤ 10^5 )\) - maktab o'quvchilari guruhlari soni. Ikkinchi qatorda s[1] , s[2] , ..., s[n] \(( 1 ≤ s [i] ≤ 4 )\) butun sonlar ketma-ketligi mavjud. Butun sonlar bo'sh joy bilan ajratiladi, s[i] bu i-guruhdagi bolalar soni .

Chiquvchi ma'lumotlar:

Yagona raqamni chop eting - barcha bolalarni Robolandiyaga olib borish uchun zarur bo'lgan minimal taksilar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 2 4 3 3	4
2	8 2 3 4 4 2 1 3 1	5

D. Garov

Xotira: 32 MB, Vaqt: 1000 ms

Masala

“Saxovat” deb nomlangan o‘yinni besh kishi o‘ynamoqda. Har bir kishi dastlabki garov sifatida nolga teng bo'lmagan miqdordagi tangalarni beradi . Barcha o'yinchilar o'z tikishlarini b tangaga qo'ygandan so'ng, quyidagi operatsiya bir necha marta takrorlanadi: tanga bir o'yinchidan boshqa o'yinchiga uzatiladi.

Sizning vazifangiz, o'yin oxirida har bir o'yinchiga ega bo'lgan tangalar sonini hisobga olgan holda, dastlabki garovning b hajmini aniqlay oladigan yoki o'yinning bunday natijasini har qanday ijobiy raqam uchun olish mumkin emasligini aniqlaydigan dastur yozishdir. tangalar b dastlabki tikishda.

Kiruvchi ma'lumotlar:

Kirish beshta butun sondan iborat c 1 , c 2 , c 3 , c 4 va c 5 - mos ravishda birinchi, ikkinchi, uchinchi, to'rtinchi va beshinchi o'yinchilar o'yin oxirida ega bo'lgan tangalar soni\( (0≤ c[1], c[2], c[3], c[4], c[5] ≤100)\).

Chiquvchi ma'lumotlar:

Bitta musbat butun son b bo'lgan yagona qatorni chop eting - har bir o'yinchining dastlabki garovidagi tangalar soni. Agar b ning bunday qiymati bo'lmasa , u holda yagona " -1 " qiymatini chop eting.

Izoh:

Birinchi misolda quyidagi operatsiyalar ketma-ketligi mumkin:

To'rtinchi o'yinchidan ikkinchi o'yinchiga bitta tanga uzatiladi;
To'rtinchi o'yinchidan beshinchi o'yinchiga bitta tanga uzatiladi;
Birinchi o'yinchidan uchinchi o'yinchiga bitta tanga uzatiladi;
To'rtinchi o'yinchidan ikkinchi o'yinchiga bitta tanga uzatiladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 5 4 0 4	3
2	4 5 9 2 1	-1

E. Futbol

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bir kuni, "Russia Code Cup" tadbirida musobaqadan tashqari musobaqa sifatida futbol o'ynashga qaror qilindi. Barcha ishtirokchilar n ta jamoaga bo'lingan va bir nechta o'yin o'tkazishgan, ikkita jamoa bir-biriga qarshi bir necha marta o'ynay olmaydi.

Tayinlangan sudya eng tajribali a'zo - Pavel edi. Lekin u hammadan dono bo'lgani uchun tez orada o'yindan zerikib uxlab qoldi. Uyg'onib, u turnir tugaganini va jamoalar barcha o'yinlar natijalarini bilishni xohlashlarini aniqladi.

Pavel hech kim uning uxlab yotgani va natijalarga e'tibor bermasligi haqida bilishini istamadi, shuning uchun u barcha o'yinlar natijalarini tiklashga qaror qildi. Buning uchun u barcha jamoalardan so'radi va haqiqiy g'olib do'stlik ekanligini, ya'ni har bir jamoa boshqa jamoalarni to'liq k marta mag'lub etishini bilib oldi. Pavelga barcha shartlarga javob beradigan turnirning xronologiyasini topishga yordam bering yoki aks holda bunday jadval yo'qligini xabar qiling.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son mavjud - n va k\( ( 1 ≤ n , k ≤ 1000 )\).

Chiquvchi ma'lumotlar:

Birinchi qatorda m butun sonini chop eting - o'ynalgan o'yinlar soni. Keyingi m satrda barcha mosliklar haqidagi ma'lumotlar bo'lishi kerak, har bir satrda bittadan mos keladi. i -chi qatorda ikkita butun a[i] va b[i] ( 1 ≤ a[i] , b[i] ≤ n ; a[i] ≠ b[i] ) boʻlishi kerak . a [i] va b i raqamlari shuni anglatadiki, i -o'yinda a[i] raqamiga ega bo'lgan jamoa b[i] raqamli jamoaga qarshi g'alaba qozongan. Siz taxmin qilishingiz mumkin, jamoalar 1 dan n gacha raqamlangan.

Agar muammoning shartlariga javob beradigan turnir mavjud bo'lmasa, u holda -1 ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1	3 1 2 2 3 3 1

F. TL

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Jahonali XContest #5 roundini tayyorlamoqchi edi. Uning allaqachon bitta muammosi bor va u unga vaqt chegarasini (time limit=TL) belgilamoqchi.

Jahonali n ta to'g'ri yechim yozgan . Har bir to'g'ri yechim uchun uning ishlash vaqtini biladi (sekundlarda). Jahonali, shuningdek, m noto'g'ri yechimlar yozgan va har bir noto'g'ri yechim uchun uning ishlash vaqtini biladi (sekundlarda).

Faraz qilaylik, Jahonali muammoda v soniya TL o'rnatadi. Keyin aytishimiz mumkinki, agar uning ishlash vaqti ko'pi v soniya bo'lsa, yechim tizim sinovidan o'tadi . Bundan tashqari, biz shuni aytishimiz mumkinki, agar yechim o'z ish vaqti uchun 2a≤v tengsizlikka ega bo'lsa, "qo'shimcha" vaqt bilan tizim sinovidan o'tadi .

Natijada, Jahonali quyidagi shartlar bajarilishi uchun v soniya TLni o'rnatishga qaror qildi:

v - musbat butun son;
barcha to'g'ri yechimlar tizim sinovidan o'tadi;
kamida bitta to'g'ri yechim tizim sinovidan biroz "qo'shimcha" vaqt bilan o'tadi;
barcha noto'g'ri yechimlar tizim sinovidan o'tmaydi;
v qiymati barcha TL lar orasida minimal bo'lib, ular uchun 1 , 2 , 3 , 4 nuqtalar saqlanadi.

Jahonaliga yordam bering va eng mos TLni toping yoki bunday TL mavjud emasligini ayting.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(n,m (1≤ n, m ≤100)\)mavjud. Ikkinchi qatorda n ta boʻsh joydan ajratilgan musbat sonlar \(a[1], a[2], ..., a[n] ( 1 ≤ a[i] ≤ 100 )\) mavjud — har bir n ta toʻgʻri yechimning ishlash vaqti soniyalarda. Uchinchi qatorda m boʻshliqdan ajratilgan musbat sonlar \(b[1] , b[2], ..., b[m] ( 1 ≤ b[i] ≤ 100 )\) — har bir m notoʻgʻri yechimning ishlash vaqti soniyalarda.

Chiquvchi ma'lumotlar:

Yaroqli TL qiymati bo'lsa, uni chop eting. Aks holda -1 ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 6 4 5 2 8 9 6 10 7 11	5
2	3 1 3 4 5 6	-1

G. Bonus masala

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Disclaimer: Bu masala faqat kayfiyatni yaxshilab olish uchun.

Bu masalada 1 dan 10 gacha bo'lgan son taxmin qiling. Shuni chiqaring, agar Accepted bo'lsa to'g'ri, aks holda boshqa sonni o'ylab ko'ring.

Kiruvchi ma'lumotlar:

Kiruvchi ma'lumotlarda lyuboy narsa kiritilishi mumkin (ignore qiling).

Chiquvchi ma'lumotlar:

Masala javobi. Bu masala 10 ta urinishdan birida Accepted bo'lishi aniq.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	random narsalar	masala javobi

H. Futbolkalar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Magazinga bahor faslining boshlanishidan oldin katta miqdordagi futbolkalar sotuvga qo'yiladi. Umumiy holda sotuvga n turdagi futbolkalar qo'yiladi. i-turdagi futbolkaning ikkita butun son ko'rsatkichi bor — c[i] va q[i], bu yerda c[i] — bu i-turdagi futbolkaning narxi, q[i] esa i-turdagi futbolkaning sifati. Do'konda har bir turdagi futbolkalardan cheksiz miqdorda mavjud deb hisoblash kerak, lekin umumiy holda sifat narx bilan bog'liq emas.

Bashoratlarga ko'ra, keyingi oyda do'konga k nafar xaridor keladi, j-xaridor futbolkalarga b[j] gacha pul sarflashga tayyor.

Barcha xaridorlar bir xil strategiyaga ega. Avval xaridorlar maksimal sifatli futbolkalarni maksimal miqdorda sotib olishni xohlaydilar, keyin qolgan futbolkalar orasidan eng sifatli futbolkalarni maksimal miqdorda sotib olishadi, shuningdek, bir xil sifatli futbolkalar orasida eng arzonini tanlashadi. Xaridorlar bir xil futbolkalarni yoqtirmaydilar, shuning uchun har bir xaridor bir turdagi futbolkadan bitta sotib oladi.

Agar xaridorlar yuqorida ta'riflangan strategiyaga amal qilsalar, har bir xaridor qancha futbolka sotib olishini aniqlang. Barcha xaridorlar bir-biridan mustaqil ravishda harakat qilishadi va birining xaridi boshqasiga ta'sir qilmaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda musbat butun son n (1 ≤ n ≤ 2·10⁵) — futbolkalar turlari soni.

Keyingi n qatorning har birida ikki tadan butun son c[i] va q[i] (1 ≤ ci, qi ≤ 10⁹) — i-turdagi futbolkaning narxi va sifati beriladi.

Keyingi qatorda musbat butun son k (1 ≤ k ≤ 2·10⁵) — xaridorlar soni beriladi.

Keyingi qatorda k ta musbat son b[1], b[2], ..., b[k] (1 ≤ b[j] ≤ 10⁹) keltirilgan bo'lib, har bir j-soni j-xaridor futbolkalarga sarflashga tayyor bo'lgan pul miqdorini bildiradi.

Chiquvchi ma'lumotlar:

Chiqishda har bir xaridor qancha futbolka sotib olishini bildiruvchi k ta butun sondan iborat qator chiqarilishi kerak.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 7 5 3 5 4 3 2 13 14	2 3
2	2 100 500 50 499 4 50 200 150 100	1 2 2 1