Одна сказочная страна располагалась в дельте далекой реки ( far away river ).
В стране было n островов и на каждом острове находился город. Города были соединены дорогами. Причем существовал в точности один путь от каждого города до любого другого, возможно проходящий через другие города. К сожалению мосты в этой стране были неизвестны, поэтому для пересечения реки использовались понтоны, поэтому путешествия были некомфортными, т.к. приходилось ездить только на лошадях. Когда было открыто мостостроительство король решил вместо нескольких понтонов построить мосты, по которым могли бы ездить даже кареты. В силу бедности страны только k мостов могут быть построены.
Вам необходимо выбрать какие k понтонов надо заменить на мосты так, чтобы суммарное время путешествия между всеми парами городов оказалось минимальным. Вы можете считать, что по обычным дорогам можно ехать только на лошади, а по дороге с мостом — только в карете, запряженной и несколькими лошадьми.
Первая строка входных данных содержит 4 числа n, k, sh и sc — число городов, число мостов, которым можно построить, скорость лошади и скорость экипажа в метрах в секунду (1 ≤ k < n≤ 10 000, 1 ≤sh; sc·≤ 100 000). Каждая из следующих n – 1 строк содержит три целых числа bi, ei — номера соединяемых городов и длину дороги в метрах li (1 ≤ li ≤ 106). Города пронумерованы от 1 до n, дороги пронумерованы от 1 до n – 1.
6 2 1 2 1 2 5 3 2 6 1 4 4 4 6 4 4 5 5
1 3
Первая сессия обычно доставляет много проблем. Одна из них заключается в том, что студенту нужен по крайней мере целый день, чтобы подготовиться к одному экзамену. В день одного экзамена к другому готовиться невозможно. Но основная проблема заключается в том, что студенты могут начать готовиться к i-му экзамену, не раньше чем за ti дней до него, иначе они все забудут. Глеб хочет начать готовиться к экзаменам как можно позже, но он собирается все экзамены сдать.
Помогите Глебу выбрать день начала подготовки к экзаменам.
Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину ti для этого экзамена (1 ≤ ti ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.
Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.
3 Philosophy 29.06.2005 1 Algebra 30.06.2005 3 Physics 02.07.2005 10
27.06.2005
Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1W109) и бесконечной высоты. В этот стакан падают сверху N фигурок (1N100000). i-я фигурка представляет собой прямоугольник шириной в Wi клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1aiW–Wi+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.
В отличие от обычного тетриса, игрок не имеет возможности вращать фигурки или смещать их по горизонтали в процессе падения — еще бы, это пришлось бы делать быстро и не было бы времени серьёзно подумать над стратегией. Единственное, что он может — это выбрать порядок, в котором эти N фигурок упадут в стакан (каждая по одному разу). Ваша задача — помочь ему выбрать такой порядок, при котором высота образовавшейся в результате падения конструкции была бы как можно меньше. (В отличие от обычного тетриса, полностью заполненная фигурками горизонталь никуда не исчезает).
На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 2 |
| |
| 1 | 3 | ||
В первой строке входного файла записаны числа N и W, а в последующих N строках — пары чисел ai и Wi.
Выведите в выходной файл минимальную возможную высоту конструкции, а затем последовательность номеров фигурок, к этой высоте приводящую. Фигурки нумеруются натуральными числами от 1 до N в том порядке, в котором они указаны во входных данных. Если возможных вариантов несколько, выведите любой из них.
3 4 1 2 2 2 3 2
2 3 1 2
На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо \(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