A. Komiljon va shokolad
Xotira: 32 MB, Vaqt: 1000 msKomiljon bugun xolasinikiga bormoqchi. Komiljonni xolasining uyida shirin taomlar va xolasidan tashqari jiyanlari bo‘lmish Asror, Abror va Ahror kutishmoqda. Komiljon jiyanlarini juda yaxshi ko‘radi, shuning uchun ularga o‘zining shokoladlarini olib bormoqchi.
Unda hozir \(N\) dona shokolad bor. Ammo u xolasinikiga borganda hamma jiyanlarini birdek xursand qilish uchun ularga bir xil sondagi shokoladlar berishi shart. U uyidan ko‘pi bilan nechta shokoladni o‘zi bilan olib ketsinki, jiyanlariga shokoladlarni tarqatib bo‘lgach, uning o‘zida ortiqcha shokolad qolmasin?
Kirish oqimining birinchi qatorida bitta butun son - \(N\) - hozirgi vaqtda Komiljondagi shokoladlar soni. \(3 \leq N \leq 30\)
Masala javobini chop eting.
.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
8 |
6 |
B. Komiljon va uning do'stlari
Xotira: 32 MB, Vaqt: 1000 msKomiljon va uning do‘stlari dekart koordinatalar sistemasida yashashadi. Afsuski, Komiljonning uyi ba’zi sabalarga ko‘ra buzilmoqda. Shuning uchun ham Komiljon yangi uy xarid qilmaguncha bir do‘stining uyida yashab turmoqchi. Komiljon o‘z buyumlarini do‘stining uyiga ko‘chirishi uchun Manhattan masofasini bosib o‘tishi lozim. Ya’ni agar Komiljonning uyi \((a, b)\) koordinatada, do'stining uyi \((c, d)\) koordinatada bo'lsa, Komiljon \(|a-c|+|b-d|\) masofani bosib o'tishi kerak.
Sizga xaritadagi barcha uylarning koordinatalari beriladi, bunda \(i\)-uy \((X_i, Y_i)\) koordinatalarda joylashgandir. Ammo siz na Komiljonning va na uning do‘sting uyi bilasiz. Sizning vazifangiz Komiljon va uning do‘stining uylari joylashgan barcha holatlardan Komiljon eng kam harakat qiladigan va eng ko‘p harakat qiladigan masofalarni topishdir. E’tibor bering, Komiljon va uning do‘sti har xil raqamli uylarda yashashadi, ammo ularning koordinatalari ustma-ust tushib qolishi mumkin.
Kirish oqimining birinchi qatorida bitta butun son - \(N\) soni kiritiladi. \((2 \le N \le 500)\)
Kirish oqimining keyingi \(N\)ta qatorida ikkitadan butun son - \(X_i\) va \(Y_i\) kiritiladi. \((0 \le X_i, Y_i \le 1000)\)
Bitta qatorda ikkita son, minimal va maksimal masofalarni chiqaring.
Agar 2-uy Komiljonning uyi va 4-uy do‘stining uyi bo‘lganida, Komiljon eng minimal 2 masofani bosib o‘tgan bo‘lardi.
Agar 3-uy Komiljonning uyi va 2-uy do‘stining uyi bo‘lganida, Komiljon eng maksimal 9 masofani bosib o‘tgan bo‘lardi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 2 3 0 0 4 5 1 1 |
2 9 |
C. Banknotalar
Xotira: 256 MB, Vaqt: 1000 msRobolandiya Markaziy bankida \(N\)ta banknota qolgan, va ularning qiymati \(A_1, A_2, ..., A_N\) robodollarga teng. Robolandiya banknotalarining bir ajoyib xususiyati bor: ixtiyoriy \(A_i\) va \(A_j\) banknotalar uchun \((1 \le i, j \le N)\) ulardan biri boshqasiga qoldiqsiz bo‘linadi.
Bankning \(Q\)ta potensial mijozi bor va har bir mijoz ma’lum bir miqdorda pul qarzga olmoqchi. Agar mijoz bankdan \(X_i\) robodollar qarz olmoqchi bo‘lsa, bank bu pullarni qaytimsiz bera oladigan bo‘lsa, buning uchun eng minimal nechta banknotalar ishlatish mumkin? Sizning vazifangiz shu savolga javob berish. Agar qaytimsiz qarz berishning iloji bo‘lmasa \(-1\) deb chiqaring.
E’tibor bering, sizning dasturingiz mijozlarga pullarni bermaydi, ya’ni so‘rovlar bir biriga ta’sir etmaydi.
Kirish oqimining birinchi qatorida bitta butun son - \(N\) - jami banknotalar soni beriladi. \((1 \le N \le 2 \cdot 10^5)\)
Kirish oqimining ikkinchi qatorida probel bilan ajratilgan \(N\)ta butun son - \(A_1, A_2, ..., A_N\) - banknotalar qiymati kiritiladi. Istalgan ikki sondan biri boshqasiga bo‘linishi kafolatlanadi. \((1 \le A_i \le 10^{18})\)
Kirish oqimining uchinchi qatorida butun son - \(Q\) - mijozlar soni kiritiladi. \((1 \le Q \le 2 \cdot 10^5)\)
Kirish oqimining to‘rtinchi qatorida probel bilan ajratilgan \(Q\)ta butun son - \(X_1, X_2, ..., X_Q\) - mijoz so‘rab kelgan qarz miqdori kiritiladi. \((1 \le X_i \le 10^{18})\)
Har bir mijoz uchun qarz berish mumkin bo‘lgan minimal banknotalar sonini chiqaring, buning iloji bo‘lmasa \(-1\) chiqaring.
1-test 1-so‘rovda 3=2+1; 1=1; 11=2+1+8. Qolganlarini esa qaytimsiz yasab bo‘lmaydi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2 1 8 5 3 1 5 11 12 |
2 1 -1 3 -1 |
| 2 |
4 1 1 1 100 4 4 3 101 104 |
-1 3 2 -1 |
D. Shifuning topshirig'i
Xotira: 256 MB, Vaqt: 2000 msKung-fu Panda ustoz Shifuning topshirig‘iga binoan, uzunligi \(N\)ga teng ketma-ketlik yasadi. Ammo ustoz Shifu bu ketma-ketlik Nefrit saroyi qoidalariga zidligini aytib, unga \(M\)ta cheklov qo‘ydi: har bir \(X_i, Y_i\) indekslar uchun, ushbu indeksdagi elementlar farqi 1ga teng bo'lishi kerak.
Boshqa so‘zlar bilan aytganda \(|A_{X_i} - A_{Y_i}| = 1\) shart bajarilishi lozim.
Endi Kung-fu Panda ketma-ketlik boshidan yasamoqchi. Siz unga yordam bering va ustoz Shifuning cheklovlariga mos keluvchi istalgan massivni topib bering. Agar bunday ketma-ketlikni topishning iloji yo‘q bo'lsa, \(-1\) chiqaring
Kirish oqimida birinchi qatorda ikkita butun son - \(N, M\) kiritiladi. \((1 \le N \le 10^5; 0 \le M \le 10^5)\)
Keyingi \(M\)ta qatorning har birida cheklovni ifodalovchi ikkita butun son - \(X_i\) va \(Y_i\) kiritiladi. \((1 \le X_i, Y_i \le N)\)
Agar javob bor bo'lsa, bir qatorda massiv elementlarini chiqaring, bunda \(1 \leq A[i] \leq 10^9\) shart bajarilishi kerak. Javoblar bir nechta bo'lsa, ixtiyoriysini chiqarishingiz mumkin. Javob yo'q bo'lsa \(-1\) chiqaring.
1-testda: \([2, 1, 5, 2, 6, 3]\) massivi barcha shartlarni qanoatlantiradi.
\(|A_3 - A_5| = |5 - 6| = 1\)
\(|A_1 - A_2| = |2 - 1| = 1\)
\(|A_4 - A_2| = |2 - 1| = 1\)
\(|A_4 - A_6| = |2 - 3| = 1\)
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
6 4 3 5 1 2 4 2 4 6 |
2 1 5 2 6 3 |
| 2 |
3 1 2 2 |
-1 |
E. Asilbek va g'aroyib oraliqlar
Xotira: 256 MB, Vaqt: 2000 msAsilbekda uzunligi \(N\)ga teng \(A\) massiv hamda \(T\) soni bor. Asilbek barcha \(1 \le l \le r \le N\) bo‘lgan oraliqlar ichidan \(F(l, r) \le T\) bo‘lgan oraliqlar sonini topmoqchi. Siz unga yordam bering.
\(F(l, r)\) quyidagicha hisoblanadi:
- \(B_1=A_l; B_2=A_{l+1}; ...; B_{r-l+1}=A_r\) massiv bo'lsin
- Bitta amalda \(B\)ning ixtiyoriy elementini 1ga oshirish, yoki 1ga kamaytirish mumkin.
- \(B\) massiv barcha elementlarini teng qilish uchun kerak bo'ladigan minimal amallar soni \(F(l, r)\) ga teng bo'ladi.
Masalan, \(A=[4,2,8,5]\). Bunda \(F(1, 2)=2\); \(F(3,3)=0\) hamda \(F(1, 4) = 7\).
Birinchi qatorda ikkita butun son - \(N\) va \(T\) sonlari kiritiladi. \(1 \le N \le 5 \cdot 10^5\); \(0 \le T \le 5 \cdot 10^{14}\)
Ikkinchi qatorda \(N\)ta butun son, \(A\) massiv elementlari kiritiladi. \(0 \le A_i \le 10^9)\)
Berilgan \(A\) massiv uchun \(F(l, r) \le T\) shartni bajaradigan \(1 \le l \le r \le N\) juftliklar sonini chop eting.
1-testda quyidagi oraliqlar shartni qanoatlantiradi: [1, 1]; [2, 2]; [3, 3]; [4, 4]; [1, 2] va [3, 4].
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 3 4 2 8 5 |
6 |
| 2 |
4 0 1 1 1 1 |
10 |