Yuqori standart, informatika Yakuniy bosqich, 2019 yil 4 fevral


Download 26.24 Kb.
Sana10.10.2019
Hajmi26.24 Kb.

Yuqori standart, informatika

Yakuniy bosqich, 2019 yil 4 fevral

Vazifa A. Olamlar orqali

Fayl nomi

standart kirish

Chiquvchi fayl nomi:

standart chiqish

Vaqt chegarasi:

1 soniya

Xotira chegarasi:

256 megabayt

Rik va Morti sayohatni boshdan kechirishmoqda. Rik va Mortining dunyosida n koinot mavjud .

Yaqinda Morti Rik bilan sayohat qilish uchun qancha imkoniyatlar borligini bilmoqchi edi.

ko'p sayohat (sayohat bu qandaydir tartibda barcha olamlarni aylanib o'tish). Morty unchalik emas

aqlli va olamlarning soni katta bo'lsa, modulo m sayohatlari soni bilan cheklanadi . Ko'proq

Mortining klonlari borligini qaerdan bilasiz. Shuning uchun, sizga biron bir Eortiya yordam so'rab kelmadi.

va uchta. Ularga og'ir ishlarida yordam bering.

Kirish formati

Kirish uchta qatorni oladi, ularning har birida n , m (1 ≤ n ≤ 10 18 ,

1 ≤ m ≤ 10 6 ).

Chiqish formati

3 ta raqamni chop eting - har bir Mortining javobi.

Reyting tizimi

N ≤ 10 6 da ishlaydigan echimlar kamida 40 foiz ball oladi.

Misol


standart kirish

standart chiqish

1 2

3 7


3 6

1

6



0

Eslatma


Sinov holatini tushuntirish. Uchun n = 1, faqat bir tur bor - birinchi tashrifi

koinot, n = 3 uchun 6 xil tur mavjud (123, 132, 213, 231, 321, 312), shuning uchun

modulo 6 - 0, va modulo 7 - 6.

1 - 5 sahifa





2-sahifa

Yuqori standart, informatika

Yakuniy bosqich, 2019 yil 4 fevral

Muammo B. Leprexaun

Fayl nomi

standart kirish

Chiquvchi fayl nomi:

standart chiqish

Vaqt chegarasi:

2 soniya

Xotira chegarasi:

256 megabayt

"Amerikalik xudolar" teleserialida to'satdan xudolar va ularning ijodlari mavjud. Suma

pastga tushgan Svini - moxov va har bir o'zini hurmat qiladigan leprexaun kabi, uning kostryulkasi ham bor

oltin tangalar, garchi ba'zi oltin tangalar omadli. Uning n tangasi bor

va har bir baxtli odam uchun uning nominal qiymati ekanligi ma'lum

(eksklyuziv operatsiya



yoki - "XOR") bundan tashqari barcha tangalarning nominatsiyalari. Svini sizga o'zining qozonini ishonib topshirdi, ammo

Endi u q sizga so'rovlarini. Uch xil so'rov mavjud:

1. Ushbu og'irlikdagi tanga olinishini ta'minlash bilan qozondan tanga x qiymatidagi tanga chiqarib oling

hozirda mavjud.

2. qozonga tanga x tanga qo'shing .

3. Omadli tangalar sonini toping.

Kirish formati

Birinchi satrda n va q ikkita (1 ≤ n ≤ 5 · 10 5 , 1 ≤ q ≤ 5 · 10 5 ) butun sonlar mavjud.

tanga va so'rovlar soni.

Ikkinchi yo'l o'z ichiga olgan n butun sonlari bir i (≤ 1 i ≤ 2 · 10 9 ,) bir i din - i tangani th.

Keyingi q satrlarda t so'rov turi avval o'rnatiladi (1 ≤ t ≤ 3) va agar so'rov birinchi bo'lsa yoki

ikkinchi turda bo'lsa, keyin tanga x ning nominal qiymati berilgan (1 ≤ x ≤ 2 · 10 9 ). Tangalarning so'rovlari va nominatsiyalari turlari -

butun sonlar.

Chiqish formati

Uchinchi turdagi har bir so'rov uchun baxtli tangalar sonini chop eting.

Reyting tizimi



N ≤ 100 da ishlaydigan echimlar kamida 20 foiz ballga ega bo'ladi.

N ≤ 10000 da ishlaydigan echimlar kamida 50 foiz ballga ega bo'ladi.

Misol


standart kirish

standart chiqish

1 3

1

3



2 1

3

0



2

Eslatma


i mutlaq yoki raqamlari bit bitwise th A va B 1, agar faqat agar i bir qator bit th

va b har xil.

4 va 5, 4 = 100 2 va 5 = 101 2 raqamlarining "XOR" raqamini ko'rib chiqing , shunda ularning egri yoki eksklyuziv yoki teng

001 2 , ya'ni kasr sonlar tizimida 1.

Keling, vaziyatdan bir misolni tahlil qilaylik. Dastlab bitta tanga bor, shuning uchun hammasi "XOR"

bundan mustasno, tangalar 0 ga teng, shuning uchun omadli tangalar yo'q. Keyin yana bir tanga qo'shiladi

vazn 1. Bitta tanga "XOR" ning og'irligi uning vazniga teng, shuning uchun ikkala tanga ham omadlidir.

2 - 5 sahifa





3-sahifa

Yuqori standart, informatika

Yakuniy bosqich, 2019 yil 4 fevral

Muammo C. Dasha va teleseriallar

Fayl nomi

standart kirish

Chiquvchi fayl nomi:

standart chiqish

Vaqt chegarasi:

1 soniya

Xotira chegarasi:

256 megabayt

Dasha teleko'rsatuvlarni juda yaxshi ko'radi. Yaqinda Netflix "Black Mirror" ning yangi epizodini chiqardi. Ammo bu

oddiy epizod emas, balki interfaol voqea. Hammasi bo'lib unda n lahzalar bor , ba'zi lahzalar - vilkalar

fitna: ular uchun keyingi qaysi nuqtada tanlov bor. Bizning versiyamizda, kafolat

Ma'lum bo'lishicha, bitta finalga faqat bitta yo'l bilan erishish mumkin. Dashaning do'stlari

unga k salqin lahzalar haqida gapirib berdi . Dasha kompyuter fanlari tanloviga tayyorgarlik ko'rayotganligi sababli u

U teleshoularga ko'p vaqt sarflashni xohlamaydi, shuning uchun u lahzalar tartibini ham bilar edi

allaqachon ko'rgan daqiqalarni orqaga qaytaradi.

Dashaga ko'rishi kerak bo'lgan daqiqalarning minimal sonini topishga yordam bering,

barcha qiziqarli fikrlarni olish.

Kirish formati

Birinchi satrda n va k ikkita butun sonlar mavjud (2 ≤ n ≤ 5 · 10 5 , 1 ≤ k ≤ n ) - son

mumkin bo'lgan daqiqalar va Dasha uchun qiziqarli daqiqalar soni.

Ikkinchi yo'l o'z ichiga oladi - n 1 natural son i (≤ 1 i ≤ i ), i - on bo'lgan zarur

i + 1) daqiqaga yetib borishni tanlang .

Oxirgi satrda k butun sonlar mavjud - Dashaga kerak bo'lgan daqiqalarning ko'rsatkichlari. Ko'rsatkichlar

Haqiqiy lahzalar boshqacha.

Chiqish formati

Bitta raqamni chop eting - Dasha ko'rgan daqiqalarning minimal soni.

Reyting tizimi



N ≤ 20 uchun ishlaydigan dasturlar kamida 40 foizni oladi

nuqta.


i = i holatida ishlaydigan dasturlar i uchun i kamida 10 foiz to'laydi

nuqta.


Misollar

standart kirish

standart chiqish

3 2


1 2

2 3


3

5 2


1 1 1 4

1 2


2

Eslatma


Birinchi sinovda Dasha barcha fikrlarni ko'rib chiqishi kerak, chunki ularning barchasi Dasha uchun qiziqarli.

Ikkinchi misolda, Dasha 4 va 5-daqiqalarda qatnashmasligi mumkin, chunki Dasha u bilan uchrashishi mumkin

2 ball, faqat 1 va 2 ni chetlab o'tib, 3 gacha - faqat 1 va 3.

3 - 5 sahifa





4-sahifa

Yuqori standart, informatika

Yakuniy bosqich, 2019 yil 4 fevral

Vazifa D. Tun qiroli

Fayl nomi

standart kirish

Chiquvchi fayl nomi:

standart chiqish

Vaqt chegarasi:

1 soniya

Xotira chegarasi:

256 megabayt

"Taxtlar o'yini" ning 8-mavsumi chiqishini kutar ekan, Gleb avvalgi barcha mavsumlarni ko'rib chiqdi va

Shu sababli u Kecha Podshohiga qarshi o'z qo'shinini tuzishga qaror qildi. Taxtlar o'yinida

7ta shohlik, ammo vazifani murakkablashtirish uchun u o'z olamini n shohliklari bilan bunyod etgan

har bir qirollikda m odamlar bor. Go'zallik va xilma-xillik uchun u uni olishga qaror qildi

har bir qirollikdan bir kishi va ularni ketma-ket joylashtiring, shunda o'sish modullarining yig'indisi farqlanadi

qo'shni odamlar qatori minimal edi (

∑ n- 1



i = 1 | a i - a i +1 ) Gleb bu muammoni hal qila olmadi,

shuning uchun siz undan unga yordam berishingizni so'raydi.

Kirish formati

Birinchi qatorda ikkita n va m natural sonlar mavjud (1 ≤ n · m ≤ 10 5 ) - qirollar soni

va har bir qirollikda yashovchilar soni.

Keyingi n satrda qirollar tasvirlangan. Ushbu satrlarning har birida m tabiiy mavjud

raqamlari bir i (≤ 1 i 10 ≤ 9 qaerda,) bir i o'sishi - i , bu holatda odamni -th.

Chiqish formati



N uzunlikdagi raqamlar ketma-ketligini chop eting - har bir tanlangan kishining o'sishi. Agar javoblar bo'lsa

bir nechta, barcha raqamlarning minimal yig'indisi bilan javobni chop eting.

Reyting tizimi

N m 10 3 uchun to'g'ri ishlaydigan echimlar kamida 40% ballga ega bo'ladi.

Misollar


standart kirish

standart chiqish

3 2

2 2


6 7

99 1


1 2 6

2 2


9 9

6 3


9 6

Eslatma


1-testga sharh: 3 shohlikdan bittasining balandligi, balandligi 2 dan 1 gacha, balandligi 6 dan 2 gacha bo'lgan odam.

2-chi sinov haqida sharh: 2 shohlikning 6 tadan balandligi, 1 tadan 9 tasida balandligi bo'lgan odam.

4 - 5 sahifa



5-sahifa

Yuqori standart, informatika

Yakuniy bosqich, 2019 yil 4 fevral

Vazifa E. bosing

Fayl nomi

standart kirish

Chiquvchi fayl nomi:

standart chiqish

Vaqt chegarasi:

2 soniya

Xotira chegarasi:

256 megabayt

Ma'lumki, Thanos cheksizlikdagi barcha toshlarni egallab olgan. Endi u o'ziga keldi

makkor reja. Dastlab, koinotdagi edi n 1 raqamlangan belgilar, n ba'zi

Ular tirik edilar va ba'zilari allaqachon o'lgan edi. Barmoq bilan bosish hatto barcha belgilarni oladi

o'liklarni tiriltiradi yoki tiriklarni o'ldiradi. Stan Li ni qancha muxlis biladi

Bu koinotning xudolar biri bo'lib, u Thanos bilan o'ynashga qaror qildi va unga berdi Q ikki so'rovlarni

turlari.

1. segmentida bosh barmoq bilan bosing l ustida r . Ushbu so'rov davomida barcha ko'rsatkichlar ko'rsatilgan qahramonlar uchun



l + 2 k ≤ r , quyidagi operatsiya amalga oshiriladi: o'liklar tiriladi, tiriklar o'ladi.

2. l dan r gacha bo'lgan vaqt oralig'ida tirik belgilar sonini toping .

Kirish formati

Birinchi qatorda n va m ikkita butun sonlar mavjud (1 ≤ n, m ≤ 300000) - qahramonlar soni va

Stan Li so'rovlarining soni.

Keyingi liniyasi mavjud n ta butun sondan bir i , bir i o'lik bo'lsa belgilar tirik va 0 bo'lsa, = 1.

Keyingi m satrlarda t , l va r uchta butun sonlar berilgan (1 ≤ t ≤ 2, 1 ≤ l ≤ r ≤ n ) - so'rov turi

va chap va o'ng chegaralari.

Chiqish formati

Ikkinchi turdagi har bir so'rov uchun bitta raqamni bosib chiqaring - l dan intervalgacha yashovchilar soni



r .

Misol


standart kirish

standart chiqish

3 4

1 0 1


1 1 3

2 1 3


1 1 3

2 1 3
Download 26.24 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling