Есеп A. Шыбын

Ара қашықтығы $D$ болатын екі қаладан $0$ уақытында бір-біріне қарама-қарсы бағытта сәйкесінше жылдамдықтары $V_1$ және $V_2$ екі велосипедші шықты. Екінші велосипедшіге қарсы бағытта бірінші қаладан бірінші велосипедшімен бірге $W$ ($W \ge max(V_1,V_2)$) жылдамдығымен шыбын шықты. Шыбын екінші велосипедшіге жетсе, ол лезде бұрылып қайта ұшады. Бірінші велосипедшіге жеткенде, ол бұрылып және тағы сол сияқты. Шыбынның $T$ уақыты дейін неше рет бурылыс жасайтының аңыктаңыз. Енгізу файлында $5$ теріс емес сан жазылған: $D$, $V_1$, $V_2$, $W$, $T$ ($T \cdot (V_1 + V_2) < D$). Сандардың ешқайсысы $10^7$-нан аспайды. Шығыс файлына бір жалпы сан — есептің жауабы шығарыңыз. Вход

10 0 0 10 10

Ответ

9

Вход

20 1 2 3 4

Ответ

0

Есеп B. Сиқыр

Баханың шыбындармен ойлап таплап сиқыры есіңізде ме? Жома онымен жарысуды ұйғарып, өз сиқырын ойлап тапты. Жомада жәшік бар. Ол онда шыбынды кіргізе немесе шығара алады. Сонымен қатар, ол жақсы жаттықтырушы ретінде әр шыбынның туғаннан бастап өмір жасын әр минутына дейін біледі. Сиқыр сипаттамасы: уақыттың әр сәтінде ол жәшіктегі жасы $A$-дан $B$-ға (шеткі мәндерді қоса) дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын айтып бере алады. Сіз де осындай сиқыр жасап көріңіз! Енгізу файлының бірінші жолында $N$ — оқиғалардың жалпы саны ($1 \le N \le 2 \cdot 10^5$). Әрі қарай N жол берілген, әрқайсысы оқиғалардың бірін сипаттайды:

• $+ X$ — жәшікке жасы $X$ болатын шыбынды кіргізді;
• $- X$ — жәшіктен жасы $X$ болатын шыбынды шығарды;
• $? K A B$ — сиқыршыдан жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын сұрады ($1 \le K \le 10^5$, $A \le B$).

Шыбынның жасы ($X$, $A$, $B$) — $1$-ден $10^9$-ге дейінгі бүтін сан. Шығыс файлда саны — енгізу файлдағы жас шамасы туралы сұраныстардың санындай болатын жолдар болуы тиіс. Әрбір осындай сұраныс үшін сәйкесінше санды — сұранысқа жауапты құрайтын жолды шығару керек. Егер жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың саны $K$-дан кіші болса, онда $0$-ді шығару керек. Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Ответ

2
3
0

Есеп C. Пароль

Жома ұзын және қүрделі паролдерді қолдануды ұнатады. Ол үй компьютерінің паролін ұмытып қалды және енді жаңа NFS-ті ойнай алмайды. Ол өте көңілсіз және екі рет өзінің паролін еске түсіргісі келді. Өкінішке орай, одан ештеңе шықпады. Ол бірінші әрекетінде $A$ символда, ал екінші әрекетінде $B$ символда қателеспегеніне сенімді, бірақ ол қай символдар дұрыс енгізілгенін нақты білмейді. Ол берілген шарттарға қанағаттандыратын қанша паролдер бар екеніне қызықты. Бірінші жол паролді енгізудің бірінші әрекетін, екіншісі екінші әрекетін құрайды. Екі жолдың ұзындықтары бірдей және $N$-ға тең ($1 \le N \le 10^5$). Әр жол тек қана ағылшын әліппесінің ('$a$', ..., '$z$') кіші әріптерінен құралады. Үшінші жол — $A$, төртінші жол - $B$ сандарынан құралады, $0 \le A, B \le N$. Шығыс файлының бірінші жолына есепке жауап — мүмкін паролдер санын $10^9 + 7$-ге бөлгеннен қалдықты шығар. Вход

ab
ac
1
1

Ответ

24

Мысалдағы мүмкін паролдер: $aa$, $ad$, $ae$, ... $az$.

Есеп D. Ағаштағы жол

Әр төбесінің $3$ ұрпағы бар ағашты шексіз үштік ағаш деп атайық. Ағаштың төбелерінде келесі ережемен сандар жазылған:

• ағаштың түбірінде $1$ жазылған;
• егер белгілі бір төбеде $X$ жазылса, онда оның сол ұрпағында $X \cdot 3$, ортаңғысында $X \cdot 3 + 1$, оңында $X \cdot 3 + 2$ жазылады.

\includegraphics[width=150mm,height=40mm,trim=-130mm 200mm 0 0,clip]{images/ternary.eps} $L$, $C$, $R$, $S$, $*$ символдарынынан тұратын, ұзындығы $N$-ға тең жолды маршруттың шаблоны деп атайық. Маршруттың бірінші төбесі ағаштың түбірі болады. Жолдың әр символы келесі қадамда қайда жүру керек екенін көрсетеді:

• $L$ — сол ұрпағына
• $C$ — ортаңғы ұрпағына
• $R$ — оң ұрпағына
• $S$ — орында тұру
• $*$ — алдыңғы символдардың ($L$, $C$, $R$, $S$) кез-келгені

Жолдың бағасы деп жолдағы төбелердегі сандардың қосындысы (әрбір төбе бір рет саналады). Сізге осы берілген шаблон бойынша өтуге болатын маршруттардың бағаларының қосындысын табу керек. Енгізу файлда ұзындығы $1$-ден $2000$-ға дейін болатын жол — маршруттың шаблоны берілген. Шығыс файлда бір сан — есепке жауап шығарыңыз. Вход

*LS

Ответ

55

$50$ баллды аспайтың тесттердің жиынында $N \le 14$ кепілдік беріледі.

Есеп E. Дене шынықтыру

Оқушылар арасында пәндер бойынша өтетін олимпиадалардың тізіміне дене шынықтыруды қосу шешілді, жекелей айтқанда, спорттық жүру, кедергісіз жүгіру, кедергімен жүгіру, қаптармен жүгіру және тағы басқалар. Оргкомитет спорттың әр түріне бір маршрутты дайындауы тиіс. Жарысты ұйымдастыру үшін шаршыларға бөлінген $N \times M$ болатын тіктөртбұрышты территория бөлінді. Әр шаршы үшін оның жарыстарға дайындау бағасы анықталды. Оған қоса, қатысушылардың маршруты бастала және аяқтала алатын шаршылар белгілі. Маршрут деп әр екі көрші шаршының ортақ қабырғасы бар шаршылар тізбегін атайық. Жарыстардың барлық түрі бір уақытта болатындықтан ешқандай екі маршрут қиылыспауы тиіс, егер олар қиылысса, онда қатысушылар бір-біріне кедергі жасайды. Сіздің мақсатыңыз — оргкомитетке маршруттарды дайындау бағаларының қосындысы минимал болатындай етіп таңдауға көмектесу. Енгізу файлының бірінші жолында үш сан берілген: $N$, $M$ және $K$ ($1 \le N, M, K \le 30$), онда $N$, $M$ — территоряның өлшемі, а $K$ — жарыстар түрлерінің саны. Келесі $N$ жолдың әрқайсысы $1$-ден $100$-ге дейінгі $M$ бүтін саннан — сәйкесінше шаршының жарысқа дайындау бағасы тұрады. Келесі $K$ жолдың әрқайсысы $2$ бүтін саннан — кездейсоқ маршрут бастала алатын шаршының жолы мен қатарының нөмірлері. Соңғы $K$ жолдың әрқайсысы $2$ бүтін саннан — кездейсоқ маршрут аяқтала алатын шаршының жолы мен қатарының нөмірлері. Енгізу файлында ешқандай шаршы екі рет жазылмаған. Жолдағы сандар бос жолмен бөлінген. Егер берілген шартарға қанағаттандыратын маршрут болмаса, шығыс файлда ``$No solution$'' жолын шығару керек. Кері жағдайда бірінші жолда дайындау бағасы ең азын, ал келесі жолдарда маршруттар картасын шығар. Маршурттар картасы — $N \times M$ таблица. $i$-шы жолдың $j$-ші қатарында $0$, егер осы шаршы бойынша маршрут өтпесе немесе $X$ саны ($1 \le X \le K$), егер осы шаршы бойынша $X$-ші маршрут өтсе. Егер оптималды жауаптар саны бірнеше болса, кез-келгенін шығар. Жолдағы сандар бос жолмен бөліну керек. Вход

3 3 2
1 1 1
1 1 1
10 1 1
1 1
1 3
3 2
3 3

Ответ

7
2 0 1
2 2 1
0 2 1

$50$ баллды аспайтың тесттердің жиынында $K = 1$ кепілдік беріледі.

Есеп F. Дүкендер

Қала дөңес көпбұрыш болып келеді. Қалада бірнеше дүкен бар. Қаланың әр тұрғыны тек өзіне жақын тұрған дүкенге барады. Егер жақын дүкендер саны бірнеше болса, онда тұрғын ешқайда бармайды. Әр дүкен үшін осы дүкенге баратын тұрғындар тұратын территорияның ауданын тап. Бірінші жол $N$ — қаланы сипаттайтын көпбұрыш төбелері саны ($3 \le N \le 50$). Келесі $N$ жолдың әрқайсысы $2$ бүтін саннан — төбенің координатасы сағат тілінің бағытына қарсы тәртіппен берілген. Келесі жолда $M$ — қаладағы дүкендер саны жазылған ($1 \le M \le 50$). Келесі $M$ жолдың әрқайсысы $2$ бүтін саннан — дүкендер координатасы ($i$-шы сан — $i$-шы дүкеннің координатасы). Барлық нүктелер әртүрлі. Нүктелердің координаталары — $-10000$-ден $10000$-ға дейінгі интервалдағы сандар. Жолдағы сандар бос орынмен бөлінген. $M$ нақты сандарды шығарыңыз: $i$-шы сан — $i$-шы дүкен қызмет көрсететін, үтірден кейінгі екі цифрға дейін жуықталған аудан. Вход

4
0 0
4 0
4 4
0 4
2
1 2
3 2

Ответ

8.00
8.00

$50$ баллды аспайтың тесттердің жиынында $M \le 2$ кепілдік беріледі.