Есеп 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

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

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

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

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

Ответ

2
3
0

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

ab
ac
1
1

Ответ

24

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

(Бөлгіштер)
Сізге бірнеше сан берілген. Әр сан үшін бөлгіштер санын шығару керек. Енгізу файлының бірінші жолында $N$ — бөлгіштер санын табу керек сандардың саны жазылған ($1 \le N \le 50$). Әр келесі жолда $1$-ден $10^{14}$-ға дейін болатын бір бүтін сан жазылған. Шығыс файлына $N$ сан — әр сан үшін бір жолдан шығарылуы тиіс. Әр жол үшін бір сан — сәйкес келетін санның бөлгіштер санын шығару керек. Вход

2
1
6

Ответ

1
4

(Ағаштағы жол)
Әр төбесінің $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$-ден $16$-ға дейін болатын жол — маршруттың шаблоны берілген. Шығыс файлда бір сан — есепке жауап шығарыңыз. Вход

*LS

Ответ

55

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

3 3
1 1 1
1 1 1
10 1 1
1 1
3 3

Ответ

5
1 0 0
1 1 0
0 1 1