SamCoding Round 8 (Div. 3)

A. Shokolad bo'lagi

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 128 mb

Laylo tug'ilgan kuniga katta shokolad plitkasi sovg'a oldi. Plitka \(n\) qator va \(m\) ustundan iborat bo'lib, har bir katakchasi \(1 \times 1\) o'lchamli kichik kvadrat.

Laylo shokoladni darhol yeb qo'ymoqchi emas. U plitkadan faqat bitta kvadrat shaklidagi bo'lak kesib olmoqchi. Kesish faqat katakchalar orasidagi chiziqlar bo'ylab bajariladi. Bo'lak \(1 \times 1\), \(2 \times 2\), \(3 \times 3\) va hokazo o'lchamda bo'lishi mumkin, faqat plitkaga sig'sa bas.

Quyidagi rasmda \(2 \times 3\) o’lchamli plitkadan kvadrat bo’lak kesib olishning ba’zi usullari ko’rsatilgan:

Ikki usul har xil hisoblanadi, agar kesib olingan bo'laklar o'lchami yoki joylashuvi bilan farq qilsa.

Laylo kvadrat bo'lakni necha xil usulda kesib olishi mumkin?

Kirish ma'lumotlari

Yagona qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n, m \le 10^6\)) — plitkaning qatorlari va ustunlari soni.

Chiqish ma'lumotlari

Bitta son — kvadrat bo'lakni kesib olish usullari soni.

Misollar
# Input.txt Output.txt
1 
2 3
 
8
2 
3 4
 
20
Izoh

Birinchi misolda plitka \(2 \times 3\):

  • \(1 \times 1\) o'lchamli bo'lakni \(6\) xil joydan kesib olish mumkin;
  • \(2 \times 2\) o'lchamli bo'lakni \(2\) xil joydan kesib olish mumkin (chapdan yoki o'ngdan);
  • \(3 \times 3\) bo'lak plitkaga sig'maydi.

Jami \(6 + 2 = 8\) usul.

B. Elektron soat

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Bobur xonasiga katta elektron soat osib qo’ydi. Soat vaqtni 24 soatlik formatda \(\text{HH:MM}\) ko’rinishida ko’rsatadi. Bir xonali soat va daqiqalar oldiga nol qo’yiladi, masalan \(\text{07:05}\).

Har bir raqam yetti segmentli indikatorda chiziladi. Har bir raqamni ko’rsatish uchun nechta segment yonishi quyidagi rasmda ko’rsatilgan:

Soat har bir ko’rsatgan vaqti uchun shu vaqtda yonib turgan segmentlar soniga teng energiya birligi sarflaydi. Masalan, \(\text{12:45}\) vaqti \(2+5+4+5=16\) birlik energiya sarflaydi. 

Bobur soatni \(q\) marta sinab ko'rmoqchi. Har safar soat \(A\) vaqtda yoqiladi va \(B\) vaqt ko'rsatilib bo'lgach o'chiriladi. Ya'ni soat \(A\) dan \(B\) gacha bo'lgan barcha vaqtlarni ketma-ket, ikkala chegarasi bilan birga ko'rsatadi. Agar \(B\) vaqt \(A\) dan oldin kelsa, soat yarim tunda \(\text{23:59}\)  dan \(\text{00:00}\)  ga o'tib, keyingi kunda davom etadi.

Har bir sinov uchun soat qancha energiya sarflaganini toping.

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(q\) (\(1 \le q \le 10^5\)) — sinovlar soni.

Keyingi \(q\) ta qatorning har birida ikkita vaqt \(A\) va \(B\) \(\text{HH:MM}\) formatida berilgan (\(00 \le \text{HH} \le 23\), \(00 \le \text{MM} \le 59\)).

Chiqish ma'lumotlari

Har bir sinov uchun alohida qatorda bitta son chiqaring: soat sarflagan energiya.

Misollar
# Input.txt Output.txt
1 
3
12:45 12:45
23:58 00:01
09:59 10:01
 
16
87
59
2 
1
00:00 00:00
 
24
Izoh

Birinchi misolda:

  • 1-sinovda soat faqat \(12:45\) ni ko'rsatadi: \(16\) birlik;
  • 2-sinovda soat \(23:58\), \(23:59\), \(00:00\), \(00:01\) ni ko'rsatadi: \(22 + 21 + 24 + 20 = 87\);
  • 3-sinovda \(09:59\), \(10:00\), \(10:01\): \(23 + 20 + 16 = 59\).

Ikkinchi misolda \(A = B\), shuning uchun soat faqat \(00:00\) ni ko'rsatadi: \(6 + 6 + 6 + 6 = 24\).

C. Don miqdorlarini saralash

Vaqt chegarasi: 2000 ms | Xotira chegarasi: 256 mb

Qadimgi bir rivoyatga ko'ra, shaxmat o'yinini ixtiro qilgan dono odam podshohdan g'ayrioddiy mukofot so'raydi: taxtaning birinchi katagiga bitta bug'doy doni, ikkinchisiga ikkita, uchinchisiga to'rttasi — har keyingi katakka oldingisidan ikki baravar ko'p don qo'yishni so'raydi. Podshoh bunga osongina rozi bo'ladi, biroq keyinroq bu sonning naqadar tez o'sib ketishini tushunib qoladi.

Saroy xazinachilari endi turli o'lchamdagi taxtalar uchun kerak bo'ladigan jami don miqdorini allaqachon hisoblab chiqishgan. Bu sonlar juda katta bo'lib ketgan. Sizning vazifangiz — bu sonlarni eng kichigidan eng kattasigacha saralab berishdan iborat.

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 10^5\)) — hisoblangan don miqdorlari soni beriladi.

Keyingi \(n\) qatorning har birida bitta son \(a_i\) beriladi (\(1 \le |a_i| \le 10^5\)). Bu yerda \(|x|\) — \(x\) ning raqamlari soniga teng.

Barcha sonlarning umumiy uzunligi \(10^6\) dan oshmasligi kafolatlanadi.

Chiqish ma'lumotlari

Don miqdorlarini eng kichigidan eng kattasigacha, har birini alohida qatorda chiqaring

Misollar
# Input.txt Output.txt
1 
3
1
10000000000000000000
3
 
1
3
10000000000000000000
2 
5
9
10
350
120
1000
 
9
10
120
350
1000

D. Qog’oz buklash

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Malika to’garakda uzun qog’oz tasmasi bilan tajriba o’tkazmoqda. Tasma stolda gorizontal yotibdi.

Malika tasmani \(n\) marta bir xil usulda buklaydi: har safar tasmaning o’ng uchini ko’tarib, chap uchining ustiga qo’yadi, shunda tasma teng ikkiga bukiladi. Keyingi buklash shu buklangan tasma bilan xuddi shunday bajariladi.

\(n\) ta buklashdan so’ng Malika tasmani ehtiyotlik bilan to’liq ochadi va avvalgi holatiga qaytaradi. Endi tasmada \(2^n - 1\) ta bukilish chizig’i qoldi. Ular chapdan o’ngga \(1\) dan \(2^n - 1\) gacha raqamlangan. Tepadan qaraganda har bir bukilish chizig’i ikki xil ko’rinishda bo’ladi:

  • \(\text{V}\) — chiziq pastga botgan;
  • \(\text{A}\) — chiziq yuqoriga ko’tarilgan.

Quyidagi rasmda tasma \(1\), \(2\) va \(3\) marta buklangandan keyin ochilgan ko’rinishi tepadan pastga qarab ko’rsatilgan:

Malikaning do’stlari \(q\) ta savol berishdi: “Agar tasmani \(n\) marta buklasak, \(k\)-bukilish chizig’i qanday ko’rinishda bo’ladi?” Har bir savolga javob bering. 

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(q\) (\(1 \le q \le 10^5\)) — savollar soni.

Keyingi \(q\) ta qatorning har birida ikkita butun son \(n\) va \(k\) (\(1 \le n \le 60\), \(1 \le k \le 2^n - 1\)) berilgan.

Chiqish ma'lumotlari

Har bir savol uchun alohida qatorda bitta harf chiqaring: \(\text{V}\) yoki \(\text{A}\).

Misollar
# Input.txt Output.txt
1 
4
1 1
2 3
3 5
3 6
 
V
A
V
A
2 
2
60 576460752303423488
60 1152921504606846975
 
V
A
Izoh

Birinchi misoldagi barcha savollarning javobini rasmdan ko'rish mumkin. Masalan, \(n = 3\) bo'lganda chiziqlar chapdan o'ngga \(\text{V V A V V A A}\) ko'rinishida, shuning uchun 5-chiziq \(\text{V}\), 6-chiziq esa \(\text{A}\).

E. Minimal almashtirishlar soni

Vaqt chegarasi: 2000 ms | Xotira chegarasi: 256 mb

Sizga \(n\) ta sondan iborat \(a_1, a_2, \dots, a_n\) massiv berilgan (barcha elementlar turlicha). Bitta amalda siz massivdagi ixtiyoriy ikkita elementning o'rnini almashtira olasiz. Sizning vazifangiz — massivni o'sish tartibiga keltirish uchun zarur bo'ladigan eng kam almashtirishlar sonini topishdan iborat.

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 10^5\)) — massivdagi elementlar soni beriladi. Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) beriladi, bo'sh joy bilan ajratilgan. Barcha \(a_i\) qiymatlari o'zaro turlicha ekanligi kafolatlanadi.

Chiqish ma'lumotlari

Yagona qatorda bitta butun son — massivni saralash uchun zarur bo'ladigan eng kam almashtirishlar sonini chiqaring.

Misollar
# Input.txt Output.txt
1 
4
4 3 2 1
 
2
2 
5
2 3 4 5 1
 
4
Izoh

Berilgan \([4, 3, 2, 1]\) massivini saralash uchun \(2\) ta almashtirish yetarli: avval \(4\) va \(1\) ni almashtiramiz — \([1, 3, 2, 4]\), so'ng \(3\) va \(2\) ni almashtiramiz — \([1, 2, 3, 4]\).

F. Tog' sayohati

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Sardor do'stlari bilan Chimyon tog'lariga piyoda sayohatga otlandi. Yo'nalish bo'ylab ketma-ket \(n\) ta to'xtash nuqtasi bor, \(i\)-nuqtaning dengiz sathidan balandligi \(a_i\) metr.

Sayohat bir necha kunga bo'linadi. Har kuni guruh qandaydir \(l\)-nuqtadan yo'lga chiqadi va \(r\)-nuqtada (\(l \le r\)) tunab qoladi; ertasi kuni esa \((r+1)\)-nuqtadan yo'lga chiqadi. Birinchi kun \(1\)-nuqtadan boshlanadi, oxirgi kun esa aynan \(n\)-nuqtada tugashi kerak. Shunday qilib, har bir nuqta roppa-rosa bitta kunga tegishli bo'ladi.

Sardorning qat'iy qoidasi bor: kunlik yo'l "yoqimli" bo'lishi kerak. Ya'ni:

  • kun boshlanadigan \(l\)-nuqta shu kungi yo'ldagi eng past nuqta bo'lishi kerak: \(a_l \le a_i\), barcha \(l \le i \le r\) uchun;
  • kun tugaydigan \(r\)-nuqta shu kungi yo'ldagi eng baland nuqta bo'lishi kerak: \(a_r \ge a_i\), barcha \(l \le i \le r\) uchun.

Masalan, balandliklari \([1, 3, 2, 4]\) va \([1, 2, 1, 2]\) bo'lgan kunlik yo'llar yoqimli, \([1, 3, 2]\) esa yoqimli emas, chunki kun eng baland nuqtada tugamayapti. Bitta nuqtadan iborat kunlik yo'l har doim yoqimli.

Do'stlar tezroq uyga qaytmoqchi. Butun yo'nalishni eng kamida nechta yoqimli kunga bo'lish mumkinligini toping.

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 300\,000\)) — to'xtash nuqtalari soni.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — nuqtalarning balandliklari.

Chiqish ma'lumotlari

Bitta son — sayohat uchun kerak bo'ladigan eng kam kunlar soni.

Misollar
# Input.txt Output.txt
1 
6
2 3 1 1 5 1
 
3
2 
5
5 4 3 2 1
 
5

G. Bayram chiroqlari

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 256 mb

Samarqandda bayram arafasi! Shahar hokimligi Registon maydonidan boshlanuvchi uzun xiyobonga \(n\) ta chiroq o'rnatdi. Chiroqlar chapdan o'ngga \(1\) dan \(n\) gacha raqamlangan va dastlab hammasi yonib turibdi.

Shahar elektrigi Jasur aka bayram kechasi davomida markazdan ketma-ket \(q\) ta buyruq oladi. Har bir buyruq uchta son bilan beriladi: \(l\), \(r\) va \(k\).

  • Agar \(k = 1\) bo'lsa — tejamkorlik buyrug'i: \(l\) dan \(r\) gacha (ikkala chegara ham kiradi) bo'lgan barcha chiroqlar o'chiriladi. Ulardan ba'zilari avval o'chiq bo'lgan bo'lsa ham, o'chiqligicha qoladi.
  • Agar \(k = 2\) bo'lsa — tantana buyrug'i: \(l\) dan \(r\) gacha bo'lgan barcha chiroqlar yoqiladi. Ulardan ba'zilari avval yonib turgan bo'lsa ham, yonib turaveradi.

Hokim har bir buyruqdan keyin xiyobonda nechta chiroq yonib turganini bilmoqchi. Jasur akaga yordam bering!

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(n\) — chiroqlar soni, ikkinchi qatorda bitta butun son \(q\) — buyruqlar soni (\(1 \le n \le 10^9\), \(1 \le q \le 3 \cdot 10^5\)).

Keyingi \(q\) ta qatorning \(i\)-sida uchta butun son \(l_i\), \(r_i\) va \(k_i\) berilgan — \(i\)-buyruq (\(1 \le l_i \le r_i \le n\), \(1 \le k_i \le 2\)).

Chiqish ma'lumotlari

\(q\) ta butun son chiqaring. \(i\)-son birinchi \(i\) ta buyruq bajarilgandan keyin yonib turgan chiroqlar soniga teng bo'lishi kerak. Har bir sonni alohida qatorga chiqaring.

Misollar
# Input.txt Output.txt
1 
10
5
3 5 1
1 2 1
4 8 2
9 9 1
1 9 2
 
7
5
7
6
10
2 
7
4
2 6 1
3 4 2
1 7 1
5 5 2
 
2
4
0
1

H. Sehrli gulzor

Vaqt chegarasi: 1000 ms | Xotira chegarasi: 512 mb

Sehrgar shogirdi Nodira ustozining gulzoriga qarashi kerak. Gulzorda bir qatorga \(n\) ta gul ekilgan, \(i\)-gulning sehr kuchi \(a_i\) ga teng. Sehr kuchi musbat ham, manfiy ham, nol ham bo'lishi mumkin.

Ustoz ketishdan oldin shunday tayinladi: "Men qaytgunimcha barcha gullar tinchlansin, ya'ni har bir gulning sehr kuchi qat'iy manfiy bo'lsin."

Nodira faqat bitta afsunni biladi, va uning g'alati xususiyati bor. Afsun har doim gulzordagi eng kuchli bo'lakka tushadi:

  1. Avval ketma-ket turgan gullardan iborat shunday \([l, r]\) bo'lak (\(1 \le l \le r \le n\)) tanlanadi, uning yig'indisi \(a_l + a_{l+1} + \ldots + a_r\) gulzordagi barcha bo'laklar yig'indilari ichida eng kattasi bo'lsin. Bunday bo'laklar bir nechta bo'lsa, Nodira ulardan istalganini tanlashi mumkin;
  2. So'ng shu bo'lakdagi har bir gulning sehr kuchi \(1\) ga kamayadi.

Nodira barcha gullarni tinchlantirish uchun eng kamida necha marta afsun o'qishi kerak?

Kirish ma'lumotlari

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 5 \cdot 10^5\)) — gullar soni.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(-10^6 \le a_i \le 10^6\)) — gullarning sehr kuchlari.

Chiqish ma'lumotlari

Bitta butun son — afsunlarning eng kam soni.

Misollar
# Input.txt Output.txt
1 
4
3 -1 2 1
 
6
2 
4
-3 -1 -4 -2
 
0
3 
7
5 1000000 -300000 999999 -7 450000 0
 
1875005
Izoh

Birinchi misolda afsunlarni bunday o'qish mumkin:

  1. \([3, -1, 2, 1]\): eng katta yig'indi \(5\), u \([1, 4]\) bo'lakda → \([2, -2, 1, 0]\);
  2. eng katta yig'indi \(2\), bo'lak \([1, 1]\) → \([1, -2, 1, 0]\);
  3. eng katta yig'indi \(1\), bo'lak \([1, 1]\) → \([0, -2, 1, 0]\);
  4. eng katta yig'indi \(1\), bo'lak \([3, 3]\) → \([0, -2, 0, 0]\);
  5. eng katta yig'indi \(0\), bo'lak \([1, 1]\) → \([-1, -2, 0, 0]\);
  6. eng katta yig'indi \(0\), bo'lak \([3, 4]\) → \([-1, -2, -1, -1]\).

Endi barcha gullar tinchlandi. \(6\) tadan kam afsun bilan bunga erishib bo'lmaydi.

Ikkinchi misolda barcha gullar allaqachon tinch, shuning uchun bitta ham afsun kerak emas.

I. Sonni teskari qilish

Vaqt chegarasi: 2000 ms | Xotira chegarasi: 256 mb

Manfiy bo'lmagan butun son \(n\) berilgan. Uning raqamlarini teskari tartibda joylashtirib hosil bo'lgan sonni toping.

Masalan, \(n = 1234\) uchun javob \(4321\) bo'ladi.

Kirish ma'lumotlari

Yagona qatorda butun son \(n\) beriladi (\(0 \le n \le 10^9\)).

Chiqish ma'lumotlari

\(n\) sonining raqamlari teskari tartibda joylashtirilgandan hosil bo'lgan sonni chiqaring.

Misollar
# Input.txt Output.txt
1 
1234
 
4321
2 
1200
 
21
Izoh

Diqqat, muhim nozik jihat: agar asl sonning oxirida nol(lar) bo'lsa (masalan, \(1200\)), teskari son boshida emas, sondan tashqarida joylashadigan nol bo'lib qoladi va u avtomatik ravishda yo'qoladi — natijada \(1200\) ning teskarisi \(0021\) emas, \(21\) bo'ladi.