A. Robot
Xotira: 64 MB, Vaqt: 1000 mso'qida 0 - nuqtada robot turibdi. Uning keyingi sekunddagi harakati massiv orqali berilgan. Ya'ni:
- bo'lsa, - sekundda robot qadam o'ngga yuradi
- bo'lsa, - sekundda robot qadam chapga yuradi
- bo'lsa, - sekundda robot o'z joyida turadi.
sekunddan keyin robot 0 - nuqtadan qancha uzoqlikda joylashishini toping.
Birinchi qatorda massiv uzunligini ifodalovchi soni beriladi . Keyingi qatorda esa ta butun son - massiv elementlari beriladi .
Bitta butun son - masalaning javobini chiqaring.
# | 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 msGolomb ketma-ketligi – - elementi i soni ketma-ketlikda necha marta uchragani soniga teng bo’lgan o'suvchi ketma-ketlikdir. Ketma-ketlikning bir nechta dastlabki qiymatlari:
.
Misol uchun, , sababi 1 soni ketma-ketlikda bir marta uchragan. Xuddi shu kabi , chunki 4 soni ketma-ketlikda 3 marta uchragan.
Golomb ketma-ketligini quyidagi formula orqali topish mumkin:
Sizning vazifangiz Golomb ketma-ketligini dastlabki ta hadi yig’indisini topishdan iborat.
Bitta butun soni .
Bitta butun son – masalaning javobi.
Ketma-ketlikning dastlabki 5 ta hadi: . Ularning yig'indisi esa 11.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
5 |
11 |
2 |
12 |
44 |
C. Daraxtlarni ulash
Xotira: 64 MB, Vaqt: 1000 msDaraxt deb bog’langan, ta tugun va ta shoxdan iborat grafga aytiladi.
Sizga mos ravishda ta va 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.
Birinchi qatorda bitta butun soni - birinchi daraxt tugunlari soni . Ikkinchi qatorda esa ta va ko’rinishidagi juftliklar, ya’ni birinchi daraxt bog’lanishlari beriladi . Keyingi qatorda esa xuddi shu tartibda ikkinchi daraxt beriladi, dastlab butun soni, so’ngra ta va juftliklar .
Bitta butun son – masalaning javobi.
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.
# | 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 msta elementdan iborat massiv va ko'rinishidagi ta juftliklar berilgan. Har bir uchun massivni - va -elementlarini o'rnini almashtirish mumkin, bunda almashtirishlar soni cheklanmagan.
Sizning vazifangiz, yuqoridagi shartlarni qanoatlantirgan holda, massivni leksikografik eng kichik holatga keltirishdan iborat.
Birinchi qatorda ikkita butun son va beriladi . Ikkinchi qatorda ta butun son - massiv elementlari beriladi . Keyingi ta qatorda esa juftliklar beriladi .
Mumkin bo'lgan leksikografik eng kichik massivni chiqaring.
# | 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 msShermat robotni 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 ta nuqtaga borgani va robot borgan ixtiyoriy ikkita qo'shni nuqtalar orasidagi masofa oraliqda bo’lishini (har bir uchun ) 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).
Birinchi qatorda bitta butun soni - testlar soni beriladi . Keyingi ta qatorda Shermat ekranga chiqargan nuqtalarni bildiruvchi soni, shuningdek, , , va sonlari beriladi. .
Har bir test uchun javobni alohida qatorda chiqaring.
# | 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 msShaharda 1 dan gacha raqamlangan ta bino bor, -bino balandligi . Uchuvchini ta samolyoti bor, - samolyot balandlikkacha ko’tarila oladi.
Uchuvchi parvozini qaysidir shaharda boshlab, shaharda tugatadi, bunda bo’lishi lozim. Ya’ni u faqat o’ng tomonga ucha oladi. Uchuvchi samolyot ko’tarila oladigan balandlikdan baland binoga bora olmaydi.
Sizning vazifangiz har bir samolyot uchun, necha xil parvoz uyushtirish mumkinligini topishdan iborat
Birinchi qatorda mos ravishda binolar soni va samolyotlar sonini bildiruvchi va sonlari beriladi . Ikkinchi qatorda ta butun son beriladi. Uchinchi qatorda esa ta butun son, beriladi .
Har bir samolyot uchun turli xil parvozlar sonini toping.
Birinchi samolyot bilan uchuvchi quyidagicha parvozlarni amalga oshirishi mumkin: (1, 1), (3, 3), (5, 5), (5, 6), (6, 6).
# | 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 msShermatning 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 ta chipta bor va chiptalar 3 xil turga bo’linadi:
1. Bu chipta orqali bekatdan bekatgacha borsa bo’ladi.
2. Bu chipta orqali bekatdan oraliqdagi ixtiyoriy bekatga borsa bo’ladi.
3. Bu chipta orqali esa oraliqdagi ixtiyoriy bekatdan bekatga borsa bo’ladi.
Har bir chipta uchun avtobus qancha vaqt harakatlanishi ko’rsatilgan. Bekatlar soni jami ta bo’lib, dastlab Shermat - bekatda turibdi. Shermat - 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.
Birinchi qatorda 3 ta butun son - , , va – bekatlar soni, chiptalar soni va Shermat turgan bekat beriladi . Keyingi ta qatorda chiptalar tavsifi kiritiladi va ular quyidagicha ifodalanadi:
- - bu birinchi turli chipta bo'lib, bu chipta orqali bekatdan bekatga vaqtda borish mumkin.
- - bu ikkinchi turli chipta bo'lib, bu chipta orqali bekatdan oraliqdagi ixtiyoriy bekatga vaqtda borish mumkin.
- - bu uchinchi turli chipta bo'lib, bu chipta orqali oraliqdagi ixtiyoriy bekatdan bekatga vaqtda borish mumkin.
Yagona qatorda probel bilan ajratilgan ta sonni chiqaring, - son bekatdan - bekatgacha borish mumkin bo'lgan eng qisqa vaqtga teng bo'lsin, agar borishni iloji yo'q bo'lsa chiqaring.
# | 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 |