A. Vertolyot

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Vertolyotning yoqilg'isi tugamoqda va zudlik bilan yerga qo'nishi zarur. Vertolyot faqat va faqat H ko'rinishidagi \(H \times H\) maydonga qo'na oladi. Vertolyotning qo'na olishi uchun unga maydonni chizib bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda H toq soni kiritiladi.

\(3 \le H \le 79\)

Chiquvchi ma'lumotlar:

Ko'rsatilgan shaklni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
 
H H
HHH
H H
2 
5
 
H   H
H   H
HHHHH
H   H
H   H
3 
9
 
H       H
H       H
H       H
H       H
HHHHHHHHH
H       H
H       H
H       H
H       H

B. Tort

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Shahzoda Shohruhni hayratda qoldirmoqchi va u uchun tort pishirmoqchi. U to'g'ri retseptni topdi, lekin uyda barcha kerakli masalliqlar bor-yo'qligiga ishonchi komil emas. Tortni tayyorlash uchun har bir masalliqdan qancha miqdorda kerakligini va  uydagi miqdorni bilib, Shahzoda do'konga yo'l oldi. U nechta masalliq sotib olishi kerakligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) - kerakli masalliqlar soni kiritiladi.

Keyingi qatorda \(N\) ta butun son \(A_i\) - har bir masalliqdan qanchadan kerakligi kiritiladi.

Keyingi qatorda \(N\) ta butun son \(B_i\) - har bir masalliqdan uyda qancha borligi kiritiladi.

\(1 \le N \le 10^5\)

\(1 \le A_i, B_i \le 10^9\)

Chiquvchi ma'lumotlar:

Do'kondan necha xil turdagi masalliq sotib olish kerakligini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
3 0 2 3
4 0 2 3
 
0
2 
8
1 6 7 7 5 7 7 4 
6 5 3 8 10 3 7 4
 
3
3 
6
10 3 6 4 8 19
20 10 3 4 9 18
 
2

C. Tozalash

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Sardor xonasini tozalamoqchi. U bo‘sh joyning katta qismini o‘yinchoqlar, poyabzallar, gugurtlarning bo‘sh qutilari egallaganini payqab qoldi... Bola bir nechta qutilarni boshqalarning ichiga qo‘yishga qaror qildi va shu tariqa ko‘p joyni tejashga qaror qildi. Qutilar juda o'ziga xos shaklga ega - har bir qutiga faqat bitta kichikroq quti qo'yilishi mumkin.
Albatta, bu kichikroq quti ichida boshqa, hatto undan ham kichikroq quti bo'lishi mumkin. Sardor xonani tozalagandan keyin u yerda qancha quti ko'rinishini ayting.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) - qutilar soni kiritiladi.

Keyingi qatorda N ta butun son \(A_i\) - har bir quti o'lchami kiritiladi.
\(1 \le N \le 10^6\)

\(1 \le A_i \le 10^9\)

Chiquvchi ma'lumotlar:

Tozalash ishlaridan so'ng xonada ko'rinadigan nechta quti qolishini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
14
7 2 3 2 9 4 6 2 10 4 9 3 8 8
 
3
2 
10
9 10 3 2 4 10 7 7 5 6
 
2

D. Yomon tugunlar

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Temur balandligi N bo'lgan to'liq ikkilik daraxt rasmini chizdi, unda tugunlar ketma-ket natural sonlar bilan raqamlanadi, shunda har bir cho'qqining chap o'g'li otasining qiymatidan ikki baravar katta, o'ng o'g'li esa o'z ukasidan bir raqam kattaroq. 

Temurning ukasi Muhriddin daraxtdagi bir nechta tugunni yomon deb hisobladi va ularni daraxtdan kesib tashladi. Bunda agar shu tugunning bolalari bo'lsa, ular ham daraxtdan ajralib tushdi. Daraxtda nechta tugun qolganligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(G\) va \(N\) - daraxtning balandligi va Muhriddin yomon deb hisoblagan tugunlar soni kiritiladi.

Keyingi qatorda \(N\) ta butun son \(A_i\) - har bir yomon tugun qiymati kiritiladi.

\(1 \le G \le 60\)

\(1 \le N \le 10^5\)

\(1 \le A_i \le 2^G-1\)

\(A_i \neq A_j\) barcha \(1 \le i < j \le N\) uchun.

Chiquvchi ma'lumotlar:

Barcha yomon tugunlar kesib tashlangandan so'ng daraxtda qolgan tugunlar sonini chop eting. 

Eslatma!!! Python uchun pypy kompilyatoridan foydalaning.

Izoh:

5 balandlikdagi to'liq ikkilik daraxt.

Find LCA for K queries in Complete Binary Tree - GeeksforGeeks
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 5
6 8 10 9 2
 
5
2 
3 3
7 3 4
 
3
3 
5 5
2 17 25 20 22
 
15

E. Logistika

Xotira: 256 MB, Vaqt: 3000 ms
Masala

Robotics Lab kompaniyasi yangi loyiha - logistika tizimini yo'lga qo'ydi. Logistika kompaniyasida N ta haydovchi bor. Bundan tashqari test tizimi ishlab chiqilgan - testda haydovchining psixologik holati va haydovchilik qobiliyatidan kelib chiqib bir martalik safar uchun rulda o'tirishi mumkin bo'lgan maksimum masofa belgilanadi. Bitta yuk mashinasida istalgan miqdordagi haydovchi yo'lovchi sifatida harakatlanishi mumkin.

Ikki turdagi so'rovlar mavjud:

  • U k a → k-haydovchiga a masofa yurishiga ruxsat beruvchi litsenziya beriladi.
  • Z c s → s masofaga borish kerak bo'lgan c ta yuk mashinasi yo'lga chiqadi.

Dastlab barcha haydovchilarning litsenziyasi 0 ga teng.

Har bir ikkinchi turdagi so'rov uchun safar oxirigacha yeta olish yoki yeta olmasligini aniqlang. 

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n \) va \(q\) - haydovchilar va so'rovlar soni kiritiladi.

Keyingi \(q\) ta qatorda yuqoridagi so'rovlardan biri kiritiladi.

\(1 \le n, m \le 10^6\)

\(1 \le k, c \le n\)

\(0 \le a \le 10^9\)

\(1 \le s \le 10^9\)

 

Chiquvchi ma'lumotlar:

Har bir ikkinchi turdagi so'rov uchun alohida qatorda, agar safarni oxirigacha yetkazishning iloji bo'lsa “Yes”, aks holda “No” ni chop eting.

Izoh:

Yuk mashinalari hech qachon ortga yurmaydi, barcha yuk mashinalari bir vaqtda bir masofaga yuradi va istalgan vaqtda haydovchilar rul almashishi va boshqa yuk mashinasiga o'tishi mumkin!!!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1
 
No
Yes
No
Yes
2 
13 17
U 1 12
Z 1 9
Z 1 5
Z 4 7
U 7 18
Z 1 1
Z 1 8
U 6 4
U 1 9
U 3 13
Z 5 2
U 7 8
U 4 20
U 7 14
Z 6 1
Z 3 2
Z 8 7
 
Yes
Yes
No
Yes
Yes
No
No
Yes
No
Kitob yaratilingan sana: 18-Oct-24 10:23