Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | bakery.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | bakery.out | |||
Максимальный балл: | 100 |
Пекарня города Малоярославца способна произвести до ci буханок хлеба в i-ый день. При этом каждая буханка хлеба обойдется пекарне в fi условных Малоярославских долларов. Известно, что для обеспечения города продовольствием в день требуется di буханок хлеба, которые успешно будут употреблены населением. Оставшиеся буханки отправляются на склад и могут быть использованы в следующие дни. На складе можно в ночь с i ого на i+1 день хранить не более gi буханок, при этом хранение каждой буханки хлеба на складе обойдется пекарне в ei Малоярославских долларов.
Ваша задача — определить наименьшее количество денег, которое пекарня потратит на производство и хранение, чтобы обеспечить Малоярославец хлебом в течение n дней.
В первой строке содержится натуральное число n. Далее в n строках содержатся числа ci, fi, di. Затем в n − 1 строках содержатся числа gi, ei.
Выведите единственное число — минимальное количество денег, необходимое пекарне. Если удовлетворить требованиям города невозможно, выведите -1.
1 ≤ n ≤ 105;
0 ≤ ci, fi, di, gi, ei ≤ 109;
№ | Входной файл (bakery.in ) |
Выходной файл (bakery.out ) |
---|---|---|
1 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | division.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | division.out | |||
Максимальный балл: | 100 |
Даны числа a и b в 31-ричной системе счисления. Известно, что a делится на b. Найдите последние k цифр частного от деления a на b (также записанного в 31-ричной системе).
В первой строке содержится целое положительное число a, состоящее не более чем из миллиона (31-ричных) цифр, записанное в 31-ричной системе счисления (цифры от 0 до 9 соответствуют сами себе, заглавные буквы от 'A' до 'U' соответствуют цифрам от 10 до 30) без ведущих нулей. Во второй строке аналогично записано число b. Гарантируется, что a делится на b без остатка. В третьей строке записано число k.
Выведите ровно k 31-ричных цифр — последние k цифр частного. Если у частного меньше k цифр, дополните его слева ведущими нулями. Все выводимые буквы должны быть заглавными.
1 ≤ k ≤ 104
№ | Входной файл (division.in ) |
Выходной файл (division.out ) |
---|---|---|
1 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 4 сек | |
Входной файл: | lca.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | lca.out | |||
Максимальный балл: | 100 |
Дан ориентированный граф. Подсчитайте, сколько пар вершин (i,j) имеют общего предка. Общим предком вершин i и j называется такая вершину k, что и i, и j достижимы из k.
В первой строке входного файла содержатся целые числа — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N. Пара чисел (a,b) означает, что из вершины a есть ребро в вершину b.
Выведите одно целое число — количество пар.
1 ≤ N ≤ 104
0 ≤ M ≤ 104
№ | Входной файл (lca.in ) |
Выходной файл (lca.out ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | numbers.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | numbers.out | |||
Максимальный балл: | 100 |
Даны N целых неотрицательных чисел. Мы рассматриваем их попарные суммы (все N2 сумм). Для каждого двоичного разряда от 0 до K нужно посчитать, сколько раз в этих суммах в нем стояла единица.
Решение, работающее для K ≤ 20 и N ≤ 106, будет набирать не менее 70 баллов.
Числа N, K, P, Q. Последовательность чисел a0, ... , aN−1 генерируется так. a0 = 1, ai+1 = (ai ⋅ P + Q) mod 2K
В первой строке выведите K + 1 целое число — количества единичек в разрядах (Можно было бы вывести остальные количества, не только первые K + 1. Но они нули.) Первым выводить нужно ответ для младшего разряда.
0 ≤ N ≤ 107;
1 ≤ K ≤ 24;
1 ≤ P, Q ≤ 109 + 7;
P и Q — простые;
№ | Входной файл (numbers.in ) |
Выходной файл (numbers.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | tpath.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | tpath.out | |||
Максимальный балл: | 100 |
Задан неориентированный невзвешенный связный граф G=(V, E) с выделенным множеством вершин T ⊂ V. T-путь — простой путь, начинающийся и заканчивающийся в различных вершинах множества T. Найдите длину кратчайшего T-пути в графе, а также остаток количества различных кратчайших T-путей по модулю 1 000 000 007.
В первой строке записаны числа n, m, t — количество вершин, рёбер графа и размер множества T соответственно. На второй строке записаны t различных чисел — элементы множества T. На следующих m строках записаны пары чисел x, y — номера вершин, соединённых ребром (x ≠ y, 1 ≤ x, y ≤ n). В графе нет петель и кратных ребер.
Выведите два числа — длину кратчайшего T-пути и количество различных кратчайших T-путей по модулю 1 000 000 007.
2 ≤ n ≤ 105;
1 ≤ m ≤ 5⋅ 105;
2 ≤ t ≤ n;
№ | Входной файл (tpath.in ) |
Выходной файл (tpath.out ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | aug.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | aug.out | |||
Максимальный балл: | 100 |
Задан ориентированный граф из n вершин и m1 рёбер. Известно, что в графе есть вершины s и t такие, что все вершины достижимы из s, и из всех вершин достижима t. Также на том же множестве вершин задано другое множество рёбер, состоящее из m2 элементов. Рёбрам из этого множества приписаны некоторые целые веса.
Вам необходимо добавить к графу некоторые рёбра из второго множества так, чтобы выполнялись следующие требования:
В первой строке находится целое число n. Во второй строке находится целое неотрицательное число m1. Далее в m1 строках находятся описания ребер исходного графа. Каждое ребро задается номерами начала и конца. В следующей строке находится целое неотрицательное число m2. Далее в m2 строках находятся описания ребер, которые можно добавить. Каждое ребро задаётся номерами начала и конца и своим весом — целым числом от −109 до 109, включительно.
В первую строку выведите YES или NO в зависимости от того, существует ли решение задачи. Если решение существует, выведите три строки. В первой из них вывeдите суммарный вес добавленных рёбер. Во второй выведите количество добавленных рёбер. В третьей через пробел выведите номера добавленных рёбер. Рёбра нумеруются с единицы в том порядке, в котором они перечислены во входном файле. Каждое добавленное ребро нужно выводить ровно один раз.
1 ≤ n ≤ 105;
0 ≤ m1 + m2 ≤ 5dot 105
№ | Входной файл (aug.in ) |
Выходной файл (aug.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 15 сек | |
Входной файл: | kinc.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | kinc.out | |||
Максимальный балл: | 100 |
Рассмотрим последовательность a1, …, an. Назовём её k-почтимонотонной, если среди неравенств a1 ≤ a2, a2≤ a3, …, an−1≤ an ровно k неверных.
Даны числа 0 ≤ b1, b2, …, bm ≤ n, где b1 + b2 + … + bm = n. Найдите количество k-почтимонотонных последовательностей, в которой число 1 встречается b1 раз, 2 встречается b2 раз, …, m — bm раз.
Ответ требуется вывести по модулю 109 + 9.
В первой строке заданы два натуральных числа k и m. В следующей строке задано m натуральных чисел bi.
Выведите единственное число — ответ на поставленную задачу.
1 ≤ k ≤ 100;
1 ≤ m ≤ 26;
1 ≤ bi ≤ 100;
№ | Входной файл (kinc.in ) |
Выходной файл (kinc.out ) |
---|---|---|
1 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 3 сек | |
Входной файл: | tree.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | tree.out | |||
Максимальный балл: | 100 |
Недавно учёные обнаружили необычные связи между некоторыми звёздами в созвездии Краба. Задаваемый этими связями граф представляет собой дерево из n вершин. Каждая связь характеризуется мощностью — вещественным числом от 0.5 до 1.
Учёные решили разбить созвездие на k частей по результатам этого исследования. Для этого они исключат из рассмотрения k − 1 связь из данных и будут рассматривать получившиеся деревья. Оптимальным они считают такое разбиение, что:
k−1∑i=1ei × k∏j=1mj→ max
Здесь ei — это мощность i-й исключённой связи, а mj — количество вершин в j-м из получившихся деревьев.
Первая строка входных данных содержит два целых числа n и k. Следующие n − 1 строки содержат по три числа каждая: номера звезд, соединённых связью, а также её мощность. Известно, что мощности связей, а также их структура, случайны.
Выведите с максимально возможной точностью одно вещественное число — значение указанной функции для оптимального разбиения. Ответ считается корректным, если относительная погрешность не превышает 10−9.
1 ≤ n ≤ 100;
1 ≤ k ≤ n;
№ | Входной файл (tree.in ) |
Выходной файл (tree.out ) |
---|---|---|
1 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | painter.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | painter.out | |||
Максимальный балл: | 100 |
Художник Вася Ниимович рисует абстрактные картины. Новая его картина выглядит как прямая, части которой раскрашены в разные цвета. Рисовал он её так. Вначале он нарисовал отрезок первого цвета от точки l1 до точки r1. Потом отрезок второго цвета от l2 до r2, и так далее. Последний отрезок, нарисованный им, проходил от ln до rn и имел цвет с номером n.
Все отрезки были разных цветов, однако некоторые оказались полностью закрашены другими. Тогда Вася задумался: возможно, если бы он рисовал отрезки в тех же местах, но в другом порядке, то различных цветов на картине было бы больше? Помогите ему выбрать такой порядок рисования отрезков, при котором после того, как он нарисует все отрезки, количество видимых цветов на картине будет максимально. Отрезки считаются замкнутыми.
В первой строке написано целое число n. В следующих n строках будут написаны по два целых числа через пробел. В i-ой из этих строк находятся числа li и ri.
В первой строке выведите количество цветов, которые будут видны при оптимальном порядке рисования. Во второй строке должно быть написано n чисел — i-ое число обозначает, какой отрезок надо нарисовать i-ым для достижения оптимального результата. Отрезки нумеруются, начиная с единицы, в том же порядке, в котором они заданы во входном файле.
1 ≤ n ≤ 300;
−109 ≤ li ≤ ri ≤ 109
№ | Входной файл (painter.in ) |
Выходной файл (painter.out ) |
---|---|---|
1 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 10 сек | |
Входной файл: | rhombe.in | Ограничение памяти: | 512 Мб | |
Выходной файл: | rhombe.out | |||
Максимальный балл: | 100 |
Дано поле H × W. В некоторых клетках стоят фишки. Нужно выбрать ромб, целиком лежащий на поле, и такой, что он содержит как можно больше фишек, но при этом не содержит ни одной пары фишек, стоящих в клетках с общей стороной.
В первой строке заданы через пробел два целых числа H и W (1 ≤ W, H ≤ 3000). Следующие H строк содержат по W символов каждая. Символ `\t{*}' обозначает фишку, а символ `\t{.}' — её отсутствие.
Выведите четыре числа N, cx, cy и r через пробел — количество покрытых фишек, координаты центра ромба и его радиус (1 ≤ cx ≤ W, 1 ≤ cy ≤ H). Ромб задаётся уравнением |cx − x| + |cy − y| ≤ r. Если оптимальных ответов несколько, можно вывести любой из них.
№ | Входной файл (rhombe.in ) |
Выходной файл (rhombe.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | Жюри летних сборов 2009 | Ограничение времени: | 2 сек | |
Входной файл: | string.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | string.out | |||
Максимальный балл: | 100 |
Сотрудник небезызвестного НИИИДС Василий обнаружил, наконец, на своём рабочем месте компьютер. Не будучи слишком опытным пользователем, он не стал использовать все возможности этого загадочного агрегата. Однако из школьного курса Василий помнит, что программисты пользуются таким понятием, как \emph{переменные}. Как ими пользоваться, он не очень помнит, поэтому решил применить одну следующим образом:
В первой и единственной строке содержится данная строка s (1 ≤ |s| ≤ 10 000). Она состоит из строчных букв латинского алфавита.
Выведите оптимальный набор: в первой строке t, а во второй — g.
№ | Входной файл (string.in ) |
Выходной файл (string.out ) |
---|---|---|
1 |
|
|