A. Tug'ilgan kun
Xotira: 32 MB, Vaqt: 1000 msBugun Abdulazizning tug'ilgan kuni va u sinfdoshlarini shirinliklar bilan siylamoqchi. U maktabga borishda yo‘ldagi do‘kondan shirinlik sotib olmoqchi. Do‘konda faqat ikki xil shirinlik bor: shokolad va karamel. Ular 3 donadan qilib o‘ralgan to'plamlarda sotiladi va o'ramda har ikki turdagi konfetlar mavjud (ya'ni, bitta paketda bitta turdagi ikkita konfet va boshqa turdagi bitta konfet mavjud). Ichida qanday konfet borligini paketning tashqi ko‘rinishidan bilib bo‘lmaydi. Hech kimni xafa qilmaslik uchun sinfdagi barchaga bitta turdagi konfet berish kerak, qolganini esa uyiga olib ketadi. Abdulaziz maktabga borish uchun tayyorgarlik ko'rishi kerak, shuning uchun u sizdan hammaga etarli miqdorda konfet bo'lishi uchun sotib olinishi kerak bo'lgan minimal paketlar sonini hisoblab berishingizni so'ramoqda.
Kiruvchi ma'lumot sifatida \(n\)\((\le n \le 10^9)\) - sinfdagi o'quvchilar soni kiritiladi.
Chiquvchi ma'lumot sifatida yagona qiymat , Abdulaziz sotib olishi kerak bo'lgan paketlar soni chiqarilsin.
Birinchi misolda Abdulaziz ikki paket shirinlik sotib oladi. Birinchi paketda bitta turdagi 2 ta konfet va boshqa turdagi 1 ta konfet mavjud. Agar ikkinchi paket birinchisi bilan bir xil bo'lsa, Abdulazizda bitta turdagi 4 ta konfet va boshqa turdagi 2 ta konfet bo'ladi. Agar ikkinchi paket birinchisidan farq qilsa, Abdulaziz har bir turdagi 3 ta konfetga ega bo'ladi. Har holda, Abdulazizda bir xil turdagi 3 ta konfet bo'ladi. Birinchi misoldan ko'rinib turibdiki, bir xil turdagi 4 ta konfetni olish kafolati bo'lishi uchun ikkita paketni sotib olishning o'zi etarli emas.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
2 |
| 2 |
4 |
3 |
| 3 |
49182 |
32788 |
B. Belanchak
Xotira: 32 MB, Vaqt: 1000 msAziza, Bahodir va Samandar bolalar maydonchasiga kelib, tebranma belanchakda o’ynashni xohladilar. Belanchak — bu markazi mahkamlangan uzun tayoq bo'lib, bolalar uning ikki uchiga o'tirib tebranadilar.
Bolalarning og’irligi A, B va S kilogram. Tebranganda muvozanatni saqlash uchun, uning ikkala uchidagi og’irliklar farqi F kilogramdan oshmasligi kerak. Do'stlarga omad kulib boqdi: maydoncha yaqinida og'ir toshlar yotibdi. Bolalardan biri o'z bilan istalgan toshni olib, belanchakni uchlaridagi og’irlik farqini ruxsat etilgan chegaraga yetkazishi mumkin. Do'stlarga, ular belanchakda tebranishlari uchun, minimal og'irlikdagi toshni aniqlashda yordam bering.
Dastur kirish sifatida alohida satrlarda yozilgan bolalar og’irligi bo’lgan uchta A, B, S qiymatlarni oladi. To'rtinchi qatorda esa belanchak uchlaridagi eng katta ruxsat etilgan og’rlik farqi F kiritiladi. Barcha sonlar butun va musbat sonlar bo’lib, qiymati \(10^9\)dan oshmaydi.
Dastur do'stlar optimal tarzda o'tirishlari uchun belanchakning bir tomoniga qo'shilishi kerak bo'lgan minimal tosh o’g’irligini butun son ko’rinishida chop etishi kerak. Agar ular toshga muhtoj bo'lmasa, dastur 0 raqamini chop etishi kerak.
Birinchi misolda Aziza va Samandar bir tomonda o'tirishadi, ularning umumiy massasi 65 kg ni tashkil qiladi. Bahodir 15 kilogramlik toshni olib, boshqa tomonga o'tiradi, shunda Bahodirning tosh bilan massasi 55 kg bo'ladi. Belanchakning uchlaridagi og'irliklar farqi 10 kg bo'ladi. Ikkinchi misolda Aziza va Bahodir bir tomonda (50 kg), Samandar boshqa tomonda (45 kg) o'tirishadi. Og'irlikdagi farq 5 kg bo'ladi, shuning uchun tosh kerak bo'lmaydi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
30 40 35 10 |
15 |
| 2 |
30 20 45 10 |
0 |
C. Kinoteatr
Xotira: 512 MB, Vaqt: 1000 msKinoteatrda o’rindiqlar ko’pincha tomoshabinlarga qulaylik yaratish uchun qo’shni qatorlar bilan tartibga solinadi. Bunday kinoteatrda 1, 3, 5 . . . kabi barcha toq qatorlarda N ta o’rindiq va 2, 4, 6 . . . kabi barcha juft qatorlarda N + 1 o’rin bo’lsin. Qatorlardagi o’rindiqlar toq qatorlarda 1 dan N gacha va juft qatorlarda 1 dan N + 1 gacha raqamlangan. Kassa chiptalarni ketma-ket sotadi: birinchi navbatda 1-qatordagi 1-dan N-chi oʻrinlar uchun, soʻngra 2-qatordagi 1-dan N+1-chi oʻrinlar uchun, soʻngra 3-qatordagi 1-dan . . . va hokazo oʻrinlar uchun. Sotilgan K-chi chipta uchun qator va o’rindiq raqamini aniqlang.
Dastur kirish sifatida ikkita butun sonni oladi. Birinchi qatorda N \((1 \le N \le 10^9)\)- kinoteatrning 1-qatoridagi o'rindiqlar soni . Ikkinchi qatorda K \((1 \le K \le 2*10^9)\)- sotilgan chiptaning seriya raqami.
Dastur ikkita qiymat chiqarishi kerak: sotilgan K-chi chiptaning qator raqami va o'rindiq raqami.
Namunaviy testdagi misolni tushuntirish. 1 dan 10 gacha chiptalar birinchi qatorda sotiladi. 11 dan 21 gacha bo'lgan chiptalar ikkinchi qatorda sotiladi. Uchinchi qator uchun chiptalar 22-dan boshlab sotiladi, 25-chipta 3-qatorning 4-o'rnida bo'ladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
10 25 |
3 4 |
| 2 |
5 58 |
11 3 |
D. Lazerli qurol
Xotira: 512 MB, Vaqt: 1000 msKosmik otishma o'yinidagi o'yinchi juda kuchli lazer quroliga ega. Ammo u harakatsiz va faqat bitta yo'nalishda otishi mumkin. O'yinchi o'yin maydoniga ikki tomonlama ko’zgularni qo'yishi mumkin, bu esa dushmanlarni urish uchun nurning yo'lini o'zgartiradi. Qurol joylashgan markaz bilan dekart koordinatalar tizimini joriy qilaylik, ya'ni qurol (0;0) koordinatalariga ega. U (1;1) nuqta yo'nalishi bo'yicha o'q uzadi. O'yinchi ko'zgularni butun koordinatali nuqtalarga qo'yishi mumkin. Ko'zgular gorizontal yoki vertikal bo'lishi mumkin, agar nur ko’zgaga tegsa, u nurni aks ettirish qonunlariga muvofiq nurning traektoriyasini o'zgartiradi. Ko’zgudan nurni aks ettirishning ba'zi mumkin bo'lgan variantlari rasmda ko'rsatilgan.
Lazer nurlari nishonga tegishi uchun siz eng kam miqdorda kerak bo'ladigan ko'zgular sonini aniqlashingiz kerak.
Dastur kiruvchi ma’lumot sifatida alohida qatorlarda yozilgan nishonning \(x\) va \(y\) (10000 dan oshmaydigan butun sonlar) koordinatlarini qabul qiladi. Bunda \((x;y)\) nuqta koordinata boshi bilan mos kelmasin.
Dastur dastlab \(N\) ta zarur bo'lgan ko'zgular sonini chiqarishi kerak. Keyingi \(N\)ta qatorda har bir ko'zgu haqida ma'lumot bo'lishi kerak. Yani \(i\)-chi o'rinlarda ikkita butun son \(x_i\) va \(y_i\) nuqtaning koordinata qiymati va biror belgi \(t_i\) bo'lishi kerak, bu ko'zguning o'rnatilgan nuqtasi \((x_i;y_i)\) va ko'zgu turi \(t_i\) ni anglatadi. Agar \(t_i\) belgisi "V" bo'lsa, demak, \(i\)-chi ko'zgu vertikal tarzda o'rnatilgan, agar \(t_i\) belgisi "H" bo'lsa, demak, ko'zgu gorizontal tarzda o'rnatilgan. Masalan, “-2 5 H” yozuv gorizontal ko'zguni (−2;5) nuqtada ekanligini anglatadi. Ko'zguni har qanday tartibda chiqarish mumkin. Ko'zgu (0;0) nuqtada o'rnatilishi mumkin emas, shuningdek, ikkita ko'zgu bir xil nuqtada o'rnatilishi ham mumkin emas. \(x_i\)va \(y_i\) ning qiymatlari 100000 dan oshmasligi kerak.
Shuningdek, aks ettirilgan nurning qurolga tegishi mumkin emas. Agar javobning bir nechta variantlari bo'lsa, ulardan birini chiqarish mumkin. Agar topshiriq shartlariga muvofiq nishonni urishning iloji bo'lmasa, dastur -1 sonini chiqarishi kerak. Agar maqsadga erishish uchun ko'zgu kerak bo'lmasa, dastur bitta 0 raqamini chiqarishi kerak.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 7 |
-1 |
| 2 |
5 5 |
0 |
| 3 |
2 4 |
1 3 3 V |
| 4 |
9 7 |
1 8 8 H |
E. Ko'cha chiroqlari
Xotira: 32 MB, Vaqt: 1000 msTo'g'ri ko'cha bo'ylab bir xil masofada \(N\) ta uy joylashgan. Uylar orasidagi masofani bir birlik uzunlik sifatida qabul qilamiz. Har bir uy yoniga birta chiroq o'rnatish mumkin. Jami \(A\) ta chiroq bor, ular \(X\) masofagacha yorita oladi, va \(B\) ta chiroq bor, ular \(Y\) masofagacha yorita oladi. Agar \(X=0\) yoki \(Y=0\) bo'lsa, bunday chiroq faqat o'z o'rnatilgan uyni yoritadi. Siz barcha uylar yoritilgan bo'lishi uchun chiroqlarning minimal sonini aniqlashingiz kerak. Bir uy bir nechta chiroq bilan yoritilishi mumkin. Ko'chaning uylar orasidagi hududlarni yoritish majburiy emas.
Dastur kiruvchi ma’lumot sifatida bitta \(N\) butun sonini oladi \((1 \leq N \leq 10^5)\). Keyingi satrda yana \(A, X, B\)va \(Y\) butun musbat sonlar kiritiladi, ularning qiymatlari \(10^5\) dan oshmasligi kerak.
Dastur qancha chiroq o'rnatish kerakligini aniqlashi kerak va har bir chiroq uchun ikki butun sonni chiqarishi kerak - chiroqning koordinatasi va u yoritadigan masofa (ya'ni, \(X\) yoki \(Y\) soni).
Koordinatalar \(1\) dan \(N\) gacha bo'lgan butun sonlar bo'lishi kerak, har bir uy yonida faqat bitta chiroq o'rnatish mumkin.
Agar bir nechta to'g'ri javoblar bo'lsa, dastur har qanday to'g'ri javobni chiqarishi mumkin.
Agar javob mavjud bo'lmasa, dastur -1 ni qaytarishi kerak.
Birinchi misolda javobda 2-uydagi chiroq 1 va 3-uylarni ham yoritadi, 5-uydagi chiroq esa 3, 4, 6 va 7-uylarni ham yoritadi, 9-uydagi chiroq esa 8 va 10-uylarni ham yoritadi. Natijada barcha uylar yoritiladi. Ikkinchi misolda esa chiroqlar yetarli emas.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
10 3 1 1 2 |
3 2 7 1 10 1 |
| 2 |
10 1 1 1 2 |
-1 |
| 3 |
5 8 1 4 8 |
5 8 |