A. Robot

Xotira: 64 MB, Vaqt: 1000 ms
Masala

OXOX o'qida 0 - nuqtada robot turibdi. Uning keyingi nn sekunddagi harakati aa massiv orqali berilgan. Ya'ni:

  • ai>0a_i > 0 bo'lsa, ii - sekundda robot aia_i qadam o'ngga yuradi
  • ai<0a_i < 0 bo'lsa, ii - sekundda robot aia_i qadam chapga yuradi
  • ai=0a_i = 0 bo'lsa, ii - sekundda robot o'z joyida turadi.

nn sekunddan keyin robot 0 - nuqtadan qancha uzoqlikda joylashishini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda aa massiv uzunligini ifodalovchi nn soni beriladi (1n105)(1 ≤ n ≤ 10^5). Keyingi qatorda esa nn ta butun son - aa massiv elementlari beriladi (109ai109)(-10^9 ≤ a_i ≤ 10^9).

Chiquvchi ma'lumotlar:

Bitta butun son - masalaning javobini chiqaring.

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

B. Golomb ketma-ketligi

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Golomb ketma-ketligi G1,G2,  ,GnG_1, G_2, \space \dots \space, G_nii - elementi i soni ketma-ketlikda necha marta uchragani soniga teng bo’lgan o'suvchi ketma-ketlikdir. Ketma-ketlikning bir nechta dastlabki qiymatlari:
[1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7, ][1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, \space \dots].

Misol uchun, G1=1G_1 = 1, sababi 1 soni ketma-ketlikda bir marta uchragan. Xuddi shu kabi G4=3G_4 = 3, chunki 4 soni ketma-ketlikda 3 marta uchragan.

Golomb ketma-ketligini quyidagi formula orqali topish mumkin:

G1=1G_1 = 1
Gi+1=1+Gi+1GGi  i1G_{i+1} = 1 +G_{i+1-G_{G_i}} \space\space i \ge1

Sizning vazifangiz Golomb ketma-ketligini dastlabki nn ta hadi yig’indisini (G1+G2++Gn)(G_1 + G_2 + \dots + G_n) topishdan iborat.

Kiruvchi ma'lumotlar:

Bitta butun nn soni (1n109)( 1 \le n \le 10^9).

Chiquvchi ma'lumotlar:

Bitta butun son – masalaning javobi.

Izoh:

Ketma-ketlikning dastlabki 5 ta hadi: {1,2,2,3,3}{\{ 1, 2, 2, 3, 3}\}. Ularning yig'indisi esa 11.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
5
11
2
12
44

C. Daraxtlarni ulash

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Daraxt deb bog’langan, nn ta tugun va n1n-1 ta shoxdan iborat grafga aytiladi.

Sizga mos ravishda nn ta va mm ta tugundan iborat bo’lgan ikkita daraxt berilgan. Birinchi daraxtning biror tugunini ikkinchi daraxtning biror tuguniga ulash orqali bitta yangi daraxt hosil qilindi. Sizning vazifangiz esa hosil bo’lgan daraxtda ixtiyoriy ikkita tugun orasidagi maksimal masofa eng kamida qancha bo’lishi mumkinligini topishdan iborat.

Ikki tugun orasidagi masofa deb, bu tugunlar orasidagi shoxlar soniga aytiladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun nn soni - birinchi daraxt tugunlari soni (1n105)(1 ≤ n ≤ 10^5). Ikkinchi qatorda esa n1n-1 ta uu va vv ko’rinishidagi juftliklar, ya’ni birinchi daraxt bog’lanishlari beriladi (1u,vn,uv)(1 ≤ u, v ≤ n, u \ne v). Keyingi qatorda esa xuddi shu tartibda ikkinchi daraxt beriladi, dastlab mm butun soni, so’ngra m1m - 1 ta uu va vv juftliklar (1m105,1u,vm,uv)(1 ≤ m ≤ 10^5, 1 ≤ u, v ≤ m, u \ne v).

Chiquvchi ma'lumotlar:

Bitta butun son – masalaning javobi.

Izoh:

Quyidagi rasmda birinchi daraxt sariq rangda, ikkinchi daraxt ko’k rangda berilgan, ularni bog’lovchi shox esa qizilda berilgan, yangi daraxtdagi eng uzun masofa 3.

https://robocontest.uz/storage/images/m173.1.png

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

D. Massiv

Xotira: 64 MB, Vaqt: 2000 ms
Masala

nn ta elementdan iborat aa massiv va (x,y)(x, y) ko'rinishidagi mm ta juftliklar berilgan. Har bir i  (1im)i \space\space (1 ≤ i ≤ m) uchun massivni xix_i- va yiy_i-elementlarini o'rnini almashtirish mumkin, bunda almashtirishlar soni cheklanmagan.

Sizning vazifangiz, yuqoridagi shartlarni qanoatlantirgan holda, aa massivni leksikografik eng kichik holatga keltirishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son nn va mm beriladi (1n,m105)(1 ≤ n, m ≤ 10^5). Ikkinchi qatorda nn ta butun son - aa massiv elementlari beriladi (1ai109)(1 ≤ a_i ≤ 10^9). Keyingi mm ta qatorda esa (xi,yi)(x_i, y_i) juftliklar beriladi (1xi<yin)(1 ≤ x_i < y_i ≤ n).

 

Chiquvchi ma'lumotlar:

Mumkin bo'lgan leksikografik eng kichik massivni chiqaring.

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

E. Dasturchi Shermat

Xotira: 64 MB, Vaqt: 2000 ms
Masala

Shermat robotni OXOX o'qi bo'yicha harakatlantiradigan dastur tuzdi va qanchadir vaqt o’tgach robot harakatlangan nuqtalarning koordinatalarini ekranga chiqardi. Lekin Shermat har doimgidek nimanidir esdan chiqargandi. Bu safar u probellarni esdan chiqaribdi. Endi robot jami kk ta nuqtaga borgani va robot borgan ixtiyoriy ikkita qo'shni nuqtalar orasidagi masofa [l,r][l,r] oraliqda bo’lishini (har bir i (1i<k)i \space (1 ≤ i < k) uchun lxixi+1rl ≤ |x_i - x_i+1| ≤ r) hisobga olib, sizdan hozirgi ma’lumotlarni necha xil usulda tiklash mumkinligini so'ramoqda.

Yodda tuting. Nuqtani koordinatasi nomanfiy butun son bo'lib, oldida nollar bo'lmasligi lozim (0 sonini o'zidan tashqari).

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun tt soni - testlar soni beriladi (1t100)(1 ≤ t ≤ 100). Keyingi tt ta qatorda Shermat ekranga chiqargan nuqtalarni bildiruvchi xx soni, shuningdek, ll, rr, va kk sonlari beriladi. (1x1018,0l,r1018,1k18)(1 ≤ x ≤ 10^{18}, 0 ≤ l, r ≤ 10^{18}, 1 ≤ k ≤ 18).

 

Chiquvchi ma'lumotlar:

Har bir test uchun javobni alohida qatorda chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4
248 16 45 2
248 16 46 2
4444 1 5 2
10010 0 100000 2
1
2
0
2

F. Uchuvchi

Xotira: 64 MB, Vaqt: 2000 ms
Masala

Shaharda 1 dan nn gacha raqamlangan nn ta bino bor, ii-bino balandligi hih_i. Uchuvchini mm ta samolyoti bor, ii- samolyot aia_i balandlikkacha ko’tarila oladi.

Uchuvchi parvozini qaysidir ss shaharda boshlab, tt shaharda tugatadi, bunda sts ≤ t bo’lishi lozim. Ya’ni u faqat o’ng tomonga ucha oladi. Uchuvchi samolyot ko’tarila oladigan balandlikdan baland binoga bora olmaydi.

https://robocontest.uz/storage/images/m176.1.png

Sizning vazifangiz har bir samolyot uchun, necha xil parvoz uyushtirish mumkinligini topishdan iborat

Kiruvchi ma'lumotlar:

Birinchi qatorda mos ravishda binolar soni va samolyotlar sonini bildiruvchi nn va mm sonlari beriladi (1n,m105)(1 ≤ n, m ≤ 10^5). Ikkinchi qatorda nn ta butun son h1,h2,  ,hnh_1, h_2, \space\dots\space, h_n beriladi. Uchinchi qatorda esa mm ta butun son, a1,a2,  ,ama_1, a_2, \space\dots\space, a_m beriladi (1hi,ai106)(1 ≤ h_i, a_i ≤ 10^6).

Chiquvchi ma'lumotlar:

Har bir samolyot uchun turli xil parvozlar sonini toping.

Izoh:

Birinchi samolyot bilan uchuvchi quyidagicha parvozlarni amalga oshirishi mumkin: (1, 1), (3, 3), (5, 5), (5, 6), (6, 6).

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

G. Super chiptalar

Xotira: 128 MB, Vaqt: 2500 ms
Masala

Shermatning tug’ilgan kunida unga avtobus uchun chiptalar sovg’a qilishdi. Shermat boshida ozroq xafa bo’lgandi, lekin chiptalar oddiy emas balki super chiptalar ekanligini ko’rganidan keyin ancha taskin topdi.

Hozirda uning qo’lida mm ta chipta bor va chiptalar 3 xil turga bo’linadi:
1. Bu chipta orqali aa bekatdan bb bekatgacha borsa bo’ladi.
2. Bu chipta orqali aa bekatdan [l,r][l,r] oraliqdagi ixtiyoriy bekatga borsa bo’ladi.
3. Bu chipta orqali esa [l,r][l,r] oraliqdagi ixtiyoriy bekatdan aa bekatga borsa bo’ladi.

Har bir chipta uchun avtobus qancha vaqt harakatlanishi ko’rsatilgan. Bekatlar soni jami nn ta bo’lib, dastlab Shermat ss - bekatda turibdi. Shermat ss - bekatdan qolgan bekatlarga eng kamida qancha vaqt sarflab yetib olish mumkinligiga qiziqmoqda. Shaharda avtobus reyslari shunchalik ko’pki bekatdan bir avtobusdan tushib boshqasiga o’tirishga ketgan vaqtni 0 deb hisoblash mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda 3 ta butun son - nn, mm, va ss – bekatlar soni, chiptalar soni va Shermat turgan bekat beriladi (1n,m105,1sn)(1 ≤ n, m ≤ 10^5, 1 ≤ s ≤ n). Keyingi mm ta qatorda chiptalar tavsifi kiritiladi va ular quyidagicha ifodalanadi:

  • 1 a b t1 \space a \space b \space t - bu birinchi turli chipta bo'lib, bu chipta orqali aa bekatdan bb bekatga tt vaqtda borish mumkin.
  • 2 a l r t2 \space a \space l \space r \space t - bu ikkinchi turli chipta bo'lib, bu chipta orqali aa bekatdan [l,r][l, r] oraliqdagi ixtiyoriy bekatga tt vaqtda borish mumkin.
  • 3 a l r t3 \space a \space l \space r \space t - bu uchinchi turli chipta bo'lib, bu chipta orqali [l,r][l, r] oraliqdagi ixtiyoriy bekatdan aa bekatga tt vaqtda borish mumkin.
Chiquvchi ma'lumotlar:

Yagona qatorda probel bilan ajratilgan nn ta sonni chiqaring, ii - son ss bekatdan ii - bekatgacha borish mumkin bo'lgan eng qisqa vaqtga teng bo'lsin, agar borishni iloji yo'q bo'lsa 1-1 chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
0 28 12 
Kitob yaratilingan sana: 17-May-25 07:30