OCPC2021. Задача A. Колёса деда Панаса (код решения)

Условие

Дед Панас, постоялец палаты номер 17 заведения «Покосившийся Скворечник», срочно должен был принять свои таблетки умиротворения. К сожалению, нянечка рассыпала их по столу и теперь дед Панас твёрдо уверен, что он – Генри Форд, а на столе лежат колёса, из которых нужно собирать автомобили и мотоциклы. Сосед деда Панаса, дед Архип, также не дождавшийся своих таблеток, убеждён, что он – Блез Паскаль, и, заметив, что колёс на столе четное количество, донимает нянечку вопросом: «Сколькими способами можно распределить эти колёса между автомобилями и мотоциклами так, чтобы не оставалось лишних?» Поскольку дед Архип не уймётся, пока не получит ответа, и будет мешать нянечке собирать таблетки со стола, на помощь позвали вас и просят подсказать ей правильный ответ.

На ввод поступает единственное целое четное число $n$ $(2 \leqslant n \leqslant 10^9)$ – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно $4$ колеса, для мотоцикла – $2$. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Тесты

Входные данные Выходные данные

6 2
2 1
12 4
1000000000 250000001

Код программы

Решение

Некоторое количество колёс уходит на автомобили, а все остальные — на мотоциклы. Тогда заметим, что каждому способу разделить колёса между автомобилями и мотоциклами соответствует количество автомобилей, которые используются в этом разделении. Всего мы можем взять от $0$ до $\frac{n}{4}$ автомобилей включительно (целочисленное деление).

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC2021. Задача F. Электрик наносит ответный удар (код решения)

Условие

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число $n$ $(2 \leqslant n \leqslant 1000).$ Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от $0$ до $10^5$.

Выведите одно число – суммарную длину проводов, необходимых, чтобы устроить Очень Длинное Замыкание. Гарантируется, что существует хотя бы один способ соединения штепселей с розетками без нарушения правил средневекового этикета.

Тесты

Входные данные Выходные данные

2
1 4
6 8
9
2
1 4
2 5
2
4
2 5 6 9
3 7 12 22
22
3
2 3 4
12 13 17
33

Код программы

Решение

Обратим внимание на то, что оптимальным будет решение подключать $i$-й штепсель к $i$-й розетке. В условии задачи сказано, что существует хотя бы один способ подключить все коннекторы так, чтобы соблюсти средневековое правило этикета. Значит, последовательно подключая самый левый свободный штепсель в самую левую свободную розетку (а поскольку коннекторы изначально упорядочены, это и значит $i$-й штепсель в $i$-й розетку), мы удовлетворим правило этикета. Теперь покажем, что суммарная длина проводов в любом другом подключении не меньше. Предположим, мы подключили $i$-й штепсель в $j$-ю розетку (и это первый случай подключения штепселя не на «свое» место). Поскольку все предыдущие розетки, если они есть, уже заняты, $j \gt i$. Если можно подключить $j$-й штепсель в $i$-ю розетку (т.е. $j$-й штепсель левее $i$-й розетки), то суммарная длина проводов не изменится. Если же $j$-й штепсель правее $i$-й розетки, то чтобы иметь возможность его подключить, надо переподключить штепсели между $i$-м и $j$-м (надо заметить, что такая возможность не гарантирована). В результате этого мы сэкономим провода на не более, чем расстояние между $i$-й розеткой и $j$-м штепселем. Но поскольку $k$-я розетка, в которую мы подключим $j$-й штепсель, обязательно правее самого штепселя, то суммарная длина проводов нового подключения будет больше исходной как минимум на расстояние между $k$-й розеткой и $j$-м штепселем, поскольку этот фрагмент провода «дублируется» подключением $i$-го штепселя в $j$-ю розетку.

Далее остается посчитать сумму разниц координат соответствующих коннекторов любым удобным способом. Например, можно из суммы элементов второй строки вычесть сумму элементов в первой строке.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача B. Палиндромонойя (код решения)

Условие

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Тесты

Входные данные Выходные данные

array yes
iliya no
anna yes
cbaabcb yes
arrya no
anana yes
bcdcbaa yes

Код программы №1

Решение №1

Проверять, является ли входное слово «затаившимся палиндромом» можно непосредственно перенося буквы из начала в конец и каждый раз проверяя, не стало ли слово палиндромом. Для удобства можно написать отдельную функцию, которая будет проверять, является ли слово палиндромом.

Код программы №2

Решение №2

Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).

Далее остается проверить, действительно ли подстрока, хеш которой равен хешу «перевернутой» подстроки, является палиндромом, чтобы избежать коллизии, когда двум разным строкам соответствуют равные хеши.
Но решение без этой проверки тоже удовлетворяет тесты на олимпиаде.

Код программы №3

Решение №3

Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).

Решение №1 задачи на ideone.com

Решение №2 задачи на ideone.com

Решение №3 задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача D. Столовая (код решения)

Условие

В столовой заведения «Покосившийся Скворечник» имеется ровно $k$ тарелок, а в самом заведении – $n$ палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

Замечено, что некоторые постояльцы всегда моют за собой посуду, другие же – напротив, никогда не моют. Наутро, перед обходом главврача, вся посуда должна быть вымыта нянечками, поэтому завхоз хочет составить такой план выдачи тарелок, чтобы к концу смены нянечкам пришлось мыть их как можно меньше. Конечно же, в этих целях можно выдавать грязные тарелки, оставшиеся от предыдущих палат, постояльцам текущей. Ваша задача – посчитать, какое количество тарелок останется чистым.

Первая строка ввода содержит два целых числа $n$ и $k$ $(1 \leqslant n \leqslant 10^5, 1 \leq k \leqslant 10^5)$ – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа $a_i$ и $bi$ $(0 \leqslant a_i + b_i \leqslant k)$ – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

Выведите одно число – количество тарелок, оставшихся чистыми к концу смены, при оптимальной раздаче посуды.

Тесты

Входные данные Выходные данные

2 4
1 2
1 1
3
4 10
2 6
4 5
1 1
2 2
8
3 12
2 8
1 4
0 1
5
3 5
2 2
1 3
0 5
0

Код программы

Решение

Для решения задачи можно использовать жадный алгоритм. Для постояльцев каждой палаты нам выгодно сначала выдавать все грязные тарелки. Если они попадают к тем, кто за собой их не моет, то результат не станет хуже. При этом часть тарелок может попасть к тем, кто моет за собой, тогда грязных тарелок станет меньше.

Если грязных тарелок больше, чем не моющих за собой постояльцев, то некоторое количество грязных тарелок достанутся моющим за собой посуду постояльцам заведения.

Если же грязных тарелок меньше, чем «грязнуль»-постояльцев, то после посещения столовой этой палатой грязных тарелок останется столько, сколько там было «грязнуль».
Остается в конце посчитать количество чистых тарелок, зная количество грязных.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача G. Электрик возвращается (код решения)

Условие

Электрик Геннадий, постоялец палаты номер 404 заведения «Покосившийся Скворечник», прокрался ночью к ближайшей ЛЭП, чтобы наконец воплотить в жизнь свой план – отрезать кусок провода, находящийся между двумя соседними опорами, и отомстить лживой розетке из предыдущей задачи.

Он планирует реализовать это следующим образом: сначала просто забраться на вершину одной из опор, отрезать провод, закреплённый там, после чего спуститься на некоторую высоту вниз, возможно до земли. Далее Геннадий рассчитывает воспользоваться способностями человека-паука, которые, по его убеждению, открылись в нём после недавнего удара током: он выстрелит паутиной в некоторую произвольную точку соседнего столба, оттолкнется от первого столба и спустится по дуге окружности либо до второго столба, либо до земли. Разница высот в начале и конце такого спуска не должна превышать некоторую величину $l$, иначе наш новоявленный человек-паук рискует слишком сильно разогнаться и превратиться в человека-лепёшку. Затем электрик поднимется на вершину второго столба, чтобы отрезать закреплённый там провод, и спустится на землю.

Высоты столбов – $h_1$ и $h_2$, расстояние между ними – $d$. Геннадий не очень любит лазать вверх, поэтому он хочет разработать план таким образом, чтобы суммарная дистанция подъёмов была минимально возможной. Раз уж Вы взялись помогать ему, то доведите начатое до конца!

Единственная строка ввода содержит четыре целых числа $d$, $h_1, h_2, l$ $(1 \leqslant d, h_1, h_2, l \leqslant 10^6)$.

Выведите одно число – минимальную суммарную дистанцию подъёма Геннадия с точностью не хуже $10^-5$.

Тесты

Входные данные Выходные данные

5 5 5 5 10.00000
4 5 8 5 10.00000
4 8 5 1 13.00000
3 4 6 1 9.00000
15 2 7 8 9.00000
2 5 7 11 7.82843
1 35 38 2 38.16228

Код программы

Решение

Во-первых, поймем, что выгоднее сначала забраться на более низкий столб. Действительно, предположим, $h_1 \gt h_2$ и начинать электрик Геннадий будет с первого столба.

Заметим, что если Геннадий применит навыки человека-паука, то не сможет оказаться на втором столбе выше, чем $h_2-d$ (т.е. не выше точки $E_1$), поскольку перелетать он будет по дуге окружности, радиус которой не меньше $d$. С другой стороны, начиная с более низкого столба, он сможет перелететь в точку $E_3$ (предполагаем, что возможность воспользоваться способностью есть). При этом $H_1E_3=H_1H_2$.
Теперь сравним суммарное расстояние подъемов вверх по столбам. Если начинать с более высокого, то: $AH_1+H_2E_1=AE+H_1E+EH_2$.

С другой стороны, начиная с более низкого, получим:
$BH_2+E_3H_1=BH_2+H_1H_2$.
Заметим, что $BH_2=AE$, а по неравенству треугольника $H_1E+EH_2 \gt H_1H_2$. Отсюда и получаем, что начинать с более низкого столба экономнее.
В случае же, когда способность человека-паука применить нельзя или с её помощью Геннадий спускается до земли, не имеет значения, с какого столба начинать. Поэтому будем считать, что $h_1 \leqslant h_2$.

Забраться на более низкий столб обязательно входит в итоговую сумму. Кроме того, Геннадию либо надо будет подниматься на высоту, равную длине паутины (т.е. радиусу окружности), либо просто подняться на второй столб.

Для удобства обозначим $h_2-h_1$ через $\Delta h$, а отрезок $H_1H_2$ через $r$.
Чтобы была возможность использовать способность человека-паука, мы хотим добиться того, чтобы выполнялось следующее неравенство:
$$r — \Delta h \leqslant l $$.
Будем считать, что $h_1$ — это не высота первого столба, а высота, с которой Геннадий перелетать на второй столб (понятно, что ради удовлетворения ограничения $l$ Геннадий может только начать спускаться вниз).

Из треугольника $\Delta EH_1H_2$ выражаем $r$ :
$$r = \sqrt{d^2+\Delta h^2}.$$

Тогда неравенство принимает вид:
$$\sqrt{d^2+\Delta h^2)-\Delta h} \leqslant l,$$
$$d^2+\Delta h^2 \leqslant \frac{d^2 — l^2}{2l},$$
$$h_1 \leqslant h_2 — \frac{d^2 — l^2}{2l}.$$

Теперь понятно, что высота, с которой Геннадию надо стрелять паутиной, будет меньшим значением между выражением в правой части неравенства и высотой первого столба (в случае, если полученное нами выражение больше высоты столба, мы понимаем, что «стрелять» надо с только вершины столба).

Далее остается исключить случай, когда наше выражение отрицательное (что соответствует случаю, в котором Геннадию надо спуститься на землю и пешком перейти ко второму столбу или же на паутине перелететь только до земли, т.к. для того, чтобы совершить прыжок, удовлетворяющий ограничение $l$, герою необходимо спуститься на высоту ниже уровня земли, что невозможно).

Далее остается вычислить длину паутины по формуле $ r = \sqrt{d^2+\Delta h^2},$ принимая в качестве $h_1$ высоту, с которой надо стрелять паутиной, и прибавить полученную величину к высоте первого столба.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 396. Дождь

Условие

Дождь Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y  =  0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Входные данные

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0  \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

Выходные данные

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

Входные данные Выходные данные

30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
18
7 5
1 6 10 8
5 3 8 2
6 10 11 9
9 10 14 12
6 6 12 7
8
4 4
1 1 3 3
2 3 0 6
7 3 5 2
6 5 9 6
4
8 3
8 6 2 4
7 4 9 3
6 1 10 2
2
2 3
5 9998 0 10000
7 9996 11 9994
4 9996 9 9993
9

Код программы

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

Related Images: