#2532

Ханты-Мансийск — Париж

Темы: [Динамическое программирование] [Дерево отрезков, RSQ, RMQ] [Бинарный поиск в массиве]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2010, Задача D ]

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

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

В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.

Система оценивания

Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.

Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

Примеры

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

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

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

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

#2969

Дракон

Темы: [Бинарный поиск по ответу] [Задачи на моделирование]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2010, Задача C ]

В королевстве Флатландия наступили тяжелые времена. В пещерах неподалеку от столицы поселился ужасный Черный Дракон. Каждую ночь он выползал на охоту. Много людей погубил он, много построек уничтожил.

Король Флатландии понял, что дальше так продолжаться не может, и нанял отважного Рыцаря, чтобы тот победил рептилию.

Рыцарь принял предложение Короля и начал готовиться к битве. Сам он участия в битве принимать не желал (не рыцарское это дело –– мечом махать), поэтому решил собрать войско из копейщиков. Но копейщикам надо платить, а у Рыцаря из-за кризиса осталось совсем немного сбережений. Помогите ему определить минимальное число копейщиков, необходимое для победы над Черным Драконом.

У копейщика и у дракона есть два параметра: количество очков здоровья и наносимый противнику урон.

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

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

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

Вводятся четыре натуральных числа через пробел: H_d, D_d, h_p, d_p –– количество очков здоровья дракона, урон, наносимый драконом, количество очков здоровья одного копейщика и урон, наносимый одним копейщиком. Все числа положительные и не превосходят 10⁹.

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

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

Примеры

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

500 50 10 10

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

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

500 28 10 10

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

#3182

Колесо Фортуны

Темы: [Линейный поиск] [Остатки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 1 день, Задача B ]

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью \(v\) градусов в секунду, и стрелка, переходя из сектора \(X\) к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на \(k\) градусов в секунду. При этом если \(v \le k\), то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор \(X\).

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от \(a\) до \(b\) градусов в секунду.

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

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

Первая строка входного файла содержит целое число \(n\) — количество секторов колеса (\(3 \le n \le 100\)).

Вторая строка входного файла содержит \(n\) положительных целых чисел, каждое из которых не превышает \(1000\) — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.

Третья строка содержит три целых числа: \(a\), \(b\) и \(k\) (\(1 \le a \le b \le 10^9\), \(1 \le k \le 10^9\)).

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

В выходном файле должно содержаться одно целое число — максимальный выигрыш.

Примечание

В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то — 5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то — 4.

Во втором примере возможна только одна начальная скорость вращения колеса — 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то — 3.

Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.

Правильные решения для тестов, в которых \(1 \le a \le b \le 1000\), будут оцениваться из 50 баллов.

Примеры

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

5
1 2 3 4 5
3 5 2

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

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

5
1 2 3 4 5
15 15 2

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

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

5
5 4 3 2 1
2 5 2

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

#3207

Чемпионат по стрельбе

Темы: [Одномерные массивы] [Линейный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача B ]

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

Расспросив папу, школьник выяснил, что количество очков, которое набрал папа, заканчивается на 5, один из победителей чемпионата стрелял раньше, а папин друг, который стрелял сразу после папы, набрал меньше очков. Теперь он заинтересовался, какое самое высокое место мог занять его папа на том чемпионате.

Будем считать, что участник соревнования занял \(k\)-е место, если ровно \((k - 1)\) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

Требуется написать программу, которая по заданным результатам чемпионата определяет, какое самое высокое место на чемпионате мог занять папа победителя школьного этапа олимпиады по информатике.

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

Первая строка входного файла содержит целое число \(n\) — количество участников чемпионата страны по стрельбе (\(3 \le n \le 10^5\)).

Вторая строка входного файла содержит \(n\) положительных целых чисел, каждое из которых не превышает 1000, — очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.

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

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

Примечание

Правильные решения для тестов, в которых \(1 \le n \le 1000\), оцениваются из 50 баллов.

Примеры

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

7
10 20 15 10 30 5 1

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

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

3
15 15 10

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

#3209

Дом у дороги

Темы: [Вычислительная геометрия] [Тернарный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D ]

Пересечение полуплоскостей за O(NlogN)

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

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

Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.

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

Первая строка входного файла содержит одно целое число \(n\) — количество наиболее важных трасс (\(1 \le n \le 10^4\)).

Последующие \(n\) строк описывают трассы. Каждая трасса описывается четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\) и \(y_2\) и представляет собой прямую, проходящую через точки \((x_1, y_1)\) и \((x_2, y_2)\). Координаты заданных точек не превышают по модулю \(10^4\). Точки \((x_1, y_1)\) и \((x_2, y_2)\) ни для какой прямой не совпадают.

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

Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать \(10^9\), гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.

Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-6}\), что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет засчитан, если значение выражения \(|x - y| / max(1, |y|)\) не превышает \(10^{-6}\).

Примечание

Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны, оцениваются из 20 баллов.

Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны осям координат, оцениваются из 20 баллов.

Правильные решения для тестов, в которых \(n \le 100\), оцениваются из 70 баллов (в эти баллы включаются также по 20 баллов за случаи, описанные в предыдущих двух абзацах).

Примеры

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

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

0.5000000004656613 0.4999999995343387

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

7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339

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

4040.9996151750674 12003.999615175067