На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо \(M\)-значного числа в системе счисления с основанием \(K\) (то есть, по сути, каждый участник называет \(M\) цифр, каждая из которых лежит в диапазоне от 0 до \(K-1\)). Ведущие нули в числах допускаются.
В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также \(M\)-значное число в \(K\)-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере \(A_1\) рублей. Те, у кого совпали первые две цифры числа — получают \(A_2\) рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают \(A_3\) рублей. И так далее. Угадавшие все число полностью получают \(A_m\) рублей. При этом если игрок угадал \(t\) первых цифр, то он получает \(A_t\) рублей, но не получает призы за угадывание \(t-1\), \(t-2\) и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.
Напишите программу, которая по известным ставкам, сделанным телезрителями, находит число, которое должна назвать телеведущая, чтобы фирма-организатор розыгрыша выплатила в качестве выигрышей минимальную сумму. Для вашего удобства ставки, сделанные игроками, уже упорядочены по неубыванию.
В первой строке задаются числа \(N\) (количество телезрителей, сделавших свои ставки, \(1\le N\le 100000\)), \(M\) (длина чисел \(1\le M\le 10\)) \(K\) (основание системы счисления \(2\le K\le 10\)). В следующей строке записаны \(M\) чисел \(A_1\), \(A_2\), ..., \(A_M\), задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (\(1\le A_1\le A_2\le ... \le A_M\le 100000\)). В каждой из следующих \(N\) строк записано по одному \(M\)-значному \(K\)-ичному числу. Числа идут в порядке неубывания.
В первой строке выведите искомое число (если решений несколько — выведите любое из них), а во второй строке — сумму, которую при назывании телеведущей первого числа придется выплатить в качестве выигрыша.
10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111
011 6
1 1 10 100 0
1 0
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции.
На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым, оказывается нарушен классический принцип «от перестановки мест слагаемых сумма не меняется» ).
Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в \(1.05), потом результат — с 12 (\)1.65), и затем — с 13 (\(2.3), то всего мы заплатим \)5, если же сначала отдельно сложить 10 и 11 (\(1.05), потом — 12 и 13 (\)1.25) и, наконец, сложить между собой два полученных числа (\(2.3), то в итоге мы заплатим лишь \)4.6.
Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.
Во входном файле записано число N (2N100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.
В выходной файл выведите, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки.
4 10 11 12 13
4.60
2 1 1
0.10
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤100000. Количество этажей в небоскребе не превосходит 1000000.
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
Группы тестов:
10 1 1 1 1 1 2 3 7
7
10 1 1 3 2 1 2 3 7
9
20 100 0 1 1 2 2 5 7 2 8 17
804
Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с «Бегущим городом» назвать их «Ездящий город».
Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.
Специально по случаю соревнования между контрольными пунктами будут ходить автобусы. Перемещаться от контрольного пункта к контрольному пункту разрешается только на автобусах. При этом можно пользоваться как прямым рейсом, соединяющим контрольные пункты (если он существует), так и добираться с пересадкой через другие контрольные пункты (если это оказывается быстрее или если прямого маршрута вовсе нет), при этом в пересадочных пунктах участник не отмечается.
Известен маршрутный лист участника и расписание движения автобусов. Требуется определить минимальное время, которое понадобится участнику на прохождение маршрута.
Сначала вводится число \(N\) — общее количество контрольных пунктов (2≤\(N\)≤10000).
Далее вводится количество автобусных маршрутов \(K\) (1≤\(K\)≤50000). Далее идет \(K\) описаний автобусных маршрутов.
Каждый маршрут описывается четырьмя числами \(A_i\), \(B_i\), \(C_i\), \(D_i\), которые означают, что каждые \(C_i\) минут (т.е. в моменты времени 0, \(C_i\), 2*\(C_i\), …) автобус выходит от контрольного пункта \(A_i\) и через \(D_i\) минут прибывает к контрольному пункту \(B_i\). Все \(C_i\) и \(D_i\) — натуральные и не превышают 10000.
Будем считать, что времени на то, чтобы отметиться на контрольном пункте и на то, чтобы пересесть с автобуса на автобус, участнику не требуется. Т.е. если, например, в момент 10 он прибывает на какой-то контрольный пункт, то дальше он может уехать любым автобусом, отправляющимся от этого контрольного пункта в момент времени 10 или позднее.
Далее вводится число \(M\) — количество контрольных пунктов в маршрутном листе участника (2≤\(M\)≤50). Далее вводятся \(M\) чисел \(P_1\), \(P_2\), …, \(P_M\) — номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте \(P_1\). Временем прохождения маршрута считается момент времени, когда участник окажется в пункте \(P_M\).
Выведите одно число — минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число –1 (минус один).
2 2 2 1 3 1 1 2 5 4 3 1 2 1
7
3 4 2 1 30 10 1 2 50 40 2 3 45 10 3 1 55 10 3 1 2 1
65
2 2 1 2 3 1 1 2 5 4 3 1 2 1
-1
При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.
Проверяющей программе доступно три блока информации:
Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.
Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.
Входные данные всегда корректны. Это означает, например, что ответ участника не нужно проверять на соответствие формату и что ответ жюри точно правильный.
Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.
Тесты состоят из четырёх групп.
4 2 3 0 4 1 6 0 5 2 2 1 0 3 4 0 0
OK WA WA OK