В начале XIX века еще не было самолетов, поездов и автомобилей, поэтому все междугородние зимние поездки совершались на санях. Как известно, с дорогами в России тогда было даже больше проблем, чем сейчас, а именно на N существовавших тогда городов имелась ровно N-1 дорога, каждая из которых соединяла ровно два города. К счастью, из каждого города можно было добраться в любой другой (возможно, через некоторые промежуточные города). В каждом городе имелась почтовая станция (или, как ее называют, «ям»), на которой можно было пересесть в другие сани. При этом ямщики могли долго запрягать (для каждого из городов известно время, которое ямщики в этом городе тратят на подготовку саней к поездке) и быстро ехать (также для каждого города известна скорость, с которой ездят ямщики из него). Можно считать, что количество ямщиков в каждом городе не ограничено.
Если бы олимпиада проводилась 200 лет назад, то путь участников занимал бы гораздо большее время, чем сейчас. Допустим, из каждого города в Москву выезжает участник олимпиады и хочет добраться до Москвы за наименьшее время (не обязательно по кратчайшему пути: он может заезжать в любые города, через один и тот же город можно проезжать несколько раз). Сначала он едет на ямщике своего города. Приехав в любой город, он может либо сразу ехать дальше, либо пересесть. В первом случае он едет с той же скоростью, с какой ехал раньше. Решив сменить ямщика, он сначала ждет, пока ямщик подготовит сани, и только потом едет с ним (естественно, с той скоростью, с которой ездит этот ямщик). В пути можно делать сколько угодно пересадок.
Жюри стало интересно, какое время необходимо, чтобы все участники олимпиады доехали из своего города в Москву 200 лет назад. Все участники выезжают из своих городов одновременно.
В первой строке входного файла дано натуральное число N, не превышающее 2000 — количество городов, соединенных дорогами. Город с номером 1 является столицей.
Следующие N строк содержат по два целых числа: Ti и Vi — время подготовки саней в городе i, выраженное в часах, и скорость, с которой ездят ямщики из города i, в километрах в час (0 ≤ Ti ≤ 100, 1 ≤ Vi ≤ 100).
Следующие N–1 строк содержат описания дорог того времени. Каждое описание состоит из трех чисел Aj, Bj и Sj, где Aj и Bj — номера соединенных городов, а Sj — расстояние между ними в километрах (1 ≤ Aj ≤ N, 1 ≤ Bj ≤ N, Aj ≠ Bj, 1 ≤ Sj ≤ 10000). Все дороги двусторонние, то есть если из A можно проехать в B, то из B можно проехать в A. Гарантируется, что из всех городов можно добраться в столицу.
Сначала выведите одно вещественное число — время в часах, в которое в Москву приедет последний участник.
Далее выведите путь участника, который приедет самым последним (если таких участников несколько, выведите путь любого из них). Выведите город, из которого этот участник выехал первоначально, и перечислите в порядке посещения те города, в которых он делал пересадки. Последовательность должна заканчиваться столицей.
При проверке ответ будет засчитан, если из трех величин «время путешествия по выведенному пути», «выведенное время» и «правильный ответ» каждые две отличаются менее чем на 0.0001.
Комментарий к примеру тестов
1. Участник из города 1 уже находится на своем месте и тратит на дорогу 0 часов. Участник из города 2 ждет 10 часов ямщика в своем городе, а затем проезжает 300 км от города 2 до города 1 за 10 часов, т.е. тратит на дорогу 20 часов. Участник из города номер 3 ждет ямщика 5 часов, а затем доезжает до города 1 за 10 часов, т.е. тратит на дорогу 15 часов. Участник из города 4 может доехать до города 1 с ямщиком из города 4 за 1 + 40 = 41 час или доехать до города номер 2 за 1 + 10 = 11 часов, прождать там 10 и доехать до столицы за 10 часов. Таким образом, он может добраться до города 1 минимум за 31 час. Это и есть самое большое время и ответ к задаче.
2. Участнику из города 2 выгоднее добраться сначала до третьего города, где ездят быстрее, а потом поехать в столицу, не делая пересадки в своём городе.
4 1 1 10 30 5 40 1 10 1 2 300 1 3 400 2 4 100
31.0000000000 4 2 1
3 1 1 0 10 0 55 1 2 100 2 3 10
3.0000000000 2 3 1
Вот уже три года майор Пронин ведёт борьбу с подпольной группой по производству контрафактной продукции. Недавно его коллега, внедрившийся под прикрытием в эту организацию, передал ему важнейший документ, описывающий местонахождение главной фабрики преступников. К несчастью, сразу после этого он был раскрыт.
Майор понимал, что у него совсем немного времени до того, как придут и за ним. Поэтому он выбрал некоторый кусок документа и переслал Вам, своему ближайшему соратнику по борьбе со злом (майор боялся, что не хватит времени отправить документ целиком). Сразу после этого к нему ворвались злоумышленники и схватили Пронина. Чтобы не вызывать никаких подозрений, преступники решили не удалять документ, а просто закодировать его некоторым образом. Известно лишь, что каждый символ был заменён ровно на один символ, при этом разные символы перешли в разные, одинаковые – в одинаковые. Известно, что и до, и после перекодировки документ состоял только из символов с ASCII-кодами от 32 до 255 включительно.
Получив часть документа S, Вы немедленно отправились выручать Пронина из беды, но его дом оказался пуст. На его компьютере остался закодированный документ. Ни майор, ни его коллега на связь не выходят. Вы поняли, что единственный способ отыскать их – проникнуть на главную фабрику организации. Для этого необходимо раскодировать весь документ. Прежде чем передать его лингвистам, нужно произвести техническую обработку.
Возможно, что в тексте есть несколько фрагментов, которые могут являться кодом имеющегося у вас фрагмента S. Вы наудачу предположили, что имеющийся у вас фрагмент S в закодированном тексте является самым первым из фрагментов, в которые он мог быть закодирован.
Ваша задача – вычислить, какие символы документа могут быть определены однозначно исходя из приведённых соображений.
В первой строке записан перекодированный документ, во второй – часть документа S, оказавшаяся у вас. Обе строки имеют длину не более 106 символов и состоят только из символов с ASCII-кодами от 32 до 255 включительно. Длина S меньше длины документа.
Если на каком-то этапе произошла ошибка и входные данные некорректны, выведите Impossible. Иначе запишите в первой строку Possible, а во вторую – результат раскодировки. Символы, которые невозможно определить однозначно, замените на ?.
Подзадача 0 (0 баллов) тесты из условия.
Подзадача 1 (30 баллов) Обе строки состоят только из латинских маленьких букв. Длина каждой строки не превосходит 100. Балл за группу начисляется при прохождении всех тестов группы.
Подзадача 2 (30 баллов) Длина каждой строки не превосходит 1000. Балл за группу начисляется при прохождении всех тестов группы.
Подзадача 3 (40 баллов) Без дополнительных ограничений. В подгруппе 8 тестов каждый из которых оценивается в 5 баллов.
ababc ab
Possible abab?
fadacabba bcc
Possible ?b?b?bccb
abcdef ee
Impossible
cdcd ab
Possible abab
Параллель восьмых классов написала контрольную работу. В результате ровно A% учащихся получили 5, ровно B% — 4, ровно C% — 3, а остальные D% написали её на 2. Какое минимальное количество школьников должно быть в параллели восьмых классов для того, чтобы могли получиться такие результаты?
Вводятся 4 целых числа от 0 до 100 — A, B, C, D (A + B + C + D = 100).
Выведите единственное целое положительное число — минимальное возможное количество учащихся в параллели.
40 50 5 5
20
Сегодня в школе Васе рассказывали про числовые промежутки. Каждый из них задаётся парой чисел — своими началом и концом, и информацией о том, включается ли в него каждый из концов. Таким образом, существует четыре типа промежутков:
Рассмотрим пример: [\(3 \over 2\), 4) В данном случае \(d\) = 1, поэтому вместо \(4 \over 1\) пишут просто 4. В этом множестве содержится два целых числа: 2 и 3, а число 4 не содержится.
Помогите Васе с домашней работой — напишите программу, которая по заданному числовому промежутку посчитает количество целых чисел, содержащихся в нём.
Первым символом идёт открывающаяся квадратная или круглая скобка. Далее записано число x в формате \(a \over b\) либо a, где |a| ≤ 109, 0 < b ≤ 109. После следует запятая и пробел. Потом — число y в таком же формате. Далее — закрывающаяся квадратная или круглая скобка. После неё идёт перевод строки и конец файла.
Гарантируется, что данный числовой промежуток не является пустым (то есть содержит в себе хотя бы одно число, не обязательно целое).
По заданному числовому промежутку выведите единственное число — количество целых чисел в нём.
[3/2, 4)
2
[-2/4, 5/3]
2
[-1000, 1000]
2001
[-2, 4/3]
4
Этим летом у бабушки был большой урожай яблок. Она собрала яблоки в корзину и отдала своим \(K\) внукам.
Первый внук взял из корзины половину всех яблок и еще \(a_1\) яблоко (если количество яблок не делилось на два, то результат деления на два он мог округлить как в большую сторону, так и в меньшую). К примеру, если в корзине было 7 яблок и \(a_1 = 1\), то он мог взять либо 4, либо 5, а если было 6 яблок и \(a_1 = 1\), то он взял ровно 4.
Второй внук взял половину от всех оставшихся яблок и ещё \(a_2\) (если яблок было нечетное количество, то он также мог округлить половину как в большую, так и в меньшую сторону). И так далее, \(K\)-ый внук взял половину яблок, оставшихся после \(K - 1\) внука, и ещё \(a_k\). В итоге в корзине ничего не осталось.
Теперь они задумались, насколько же большой урожай был у бабушки. Ни один из них не помнит, делилось ли количество яблок на 2 нацело при его выборе, а если нет, то в какую сторону он округлил половину яблок. Внуков интересует минимальное и максимальное изначальное количество яблок в корзине, при которых могли произойти описанные события.
Сначала вводится целое положительное число \(K\) (\(1 \le K \le 1\,000\)). Далее записано \(K\) целых неотрицательных чисел \(a_1, \dots , a_K\) (\(0 \le a_i \le 1\,000\)).
Выведите два неотрицательных целых числа без ведущих нулей, каждое в новой строке - минимальное и максимальное возможное количество яблок в корзине соответственно.
1 1
1 3
2 0 1
1 7