Имя входного файла: cobbler.in
Имя выходного файла: cobbler.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
В некоей воинской части есть сапожник. Рабочий день сапожника длится K минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано n сапог, нуждающихся в починке.
Определите, какое максимальное количество из них сапожник сможет починить за один рабочий день.
В первой строке вводятся числа K (натуральное, не превышает 1000) и n (натуральное, не превышает 500). Затем идет n чисел — количество минут, которые требуются, чтобы починить i-й сапог (времена — натуральные числа, не превосходят 100).
Выведите одно число — максимальное количество сапог, которые можно починить за один рабочий день.
10 3
6 2 8
2
3 2
10 20
0
Имя входного файла: request.in
Имя выходного файла: request.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Вы прекрасно знаете, что в ЛКШ. Зима 2016 лекции читают лучшие преподаватели мира. К сожалению, лекционных аудиторий у нас не так уж и много, поэтому каждый преподаватель составил список лекций, которые он хочет прочитать ЛКШатам. Чтобы ЛКШата, утром идя на завтрак, увидели расписание лекций, необходимо его составить прямо сейчас. И без вас нам здесь не справиться.
У нас есть список заявок от преподавателей на лекции для одной из аудиторий. Каждая заявка представлена в виде временного интервала [si; fi) — время начала и конца лекции. Лекция считается открытым интервалом, то есть какая-то лекция может начаться в момент окончания другой, без перерыва. Необходимо выбрать из этих заявок такое подмножество, чтобы суммарно выполнить максимальное количество заявок. Учтите, что одновременно в лекционной аудитории, конечно же, может читаться лишь одна лекция.
В первой строке вводится натуральное число N, не более 1000 — общее количество заявок на лекции. Затем вводится N строк с описаниями заявок — по два числа в каждомsiиfi. Гарантируется, что si < fi. Время начала и окончания лекции — натуральные числа, не превышают 1440 (в минутах с начала суток).
Выведите одно число — максимальное количество заявок, которые можно выполнить.
1
5 10
1
3
1 5
2 3
3 4
2
Имя входного файла: printing.in
Имя выходного файла: printing.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Популярность окружной олимпиады по информатике растёт год от года. При этом организаторы должны заранее распечатать как условия задач, так и другие материалы олимпиады (анкеты, памятки и т.п.). В этом году они оценили объём печатной продукции в N листов. Фирма, готовая размножить печатные материалы, предлагает следующие финансовые условия. Один лист она печатает за A1 рублей, 10 листов — за A2 рублей, 100 листов — за A3 рублей, 1000 листов — за A4 рублей, 10000 листов — за A5 рублей, 100000 листов — за A6 рублей, 1000000 листов — за A7 рублей. При этом не гарантируется, что один лист в более крупном заказе обойдется дешевле, чем в более мелком. И даже может оказаться, что для любой партии будет выгодно воспользоваться тарифом для одного листа.
Печать конкретного заказа производится или путем комбинации нескольких тарифов, или путем заказа более крупной партии. Например, 980 листов можно распечатать, заказав печать 9 партий по 100 листов плюс 8 партий по 10 листов, сделав 98 заказов по 10 листов, 980 заказов по 1 листу или заказав печать 1000 (или даже 10000 и более) листов, если это окажется выгоднее. Требуется по заданному объему заказа в листах N определить минимальную сумму денег в рублях, которой будет достаточно для выполнения заказа.
На вход программе сначала подается число N (1 ≤ N ≤ 2×109) — количество листов в заказе. В следующих 7 строках ввода находятся натуральные числаA 1, A2, A3, A4, A5, A6, A7 соответственно (1 ≤ Ai ≤ 106).
Выведите одно число –— минимальную сумму денег в рублях, которая нужна для выполнения заказа. Гарантируется, что правильный ответ не будет превышать 2 × 109.
980
1
9
90
900
1000
10000
10000
882
980
1
10
100
1000
900
10000
10000
900
Имя входного файла: sequence.in
Имя выходного файла: sequence.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дана последовательность натуральных чисел a1..an, и известно, что ai ≤ i для любого 1 ≤ i ≤ n. Требуется определить, можно ли разбить элементы последовательности на две части таким образом, что сумма элементов в каждой из частей будет равна половине суммы всех элементов последовательности.
В первой строке входного файла находится одно целое числоn( 1 ≤ n≤ 40 000). Во второй строке находитсяnцелых чисел a1..an (1 ≤ ai ≤ i).
В первую строку выходного файла выведите количество элементов посделовательности в любой из получившихся двух частей, а во вторую строку через пробел номера этих элементов. Если построить такое разбиение невозможно, выведите -1.
3
1 2 3
1
3
Имя входного файла: apples.in
Имя выходного файла: apples.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Алисе в стране чудес попалисьnволшебных яблок. Про каждое яблоко известно, что после того, как его съешь, твой рост сначала уменьшится на ai сантиметров, а потом увеличится на bi сантиметров. Алиса очень голодная и хочет съесть всеnяблок, но боится, что в какой-то момент ее рост станет равным нулю или еще меньше, и она пропадет совсем. Помогите ей узнать, можно ли съесть яблоки в таком порядке, чтобы в любой момент времени рост Алисы был больше нуля.
В первой строке вводятся натуральные числаnиs, не более 1000 — число яблок и начальный рост Алисы. В следующихnстроках вводятся пары натуральных чиселa i, bi, не больших 1000.
Если яблоки съесть нельзя, выведите число -1. Иначе выведитеnчисел — номера яблок, в том порядке, в котором их нужно есть.
3 5
2 3
10 5
5 10
1 3 2
3 5
2 3
10 5
5 6
Имя входного файла: john.in
Имя выходного файла: john.out
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
Недавно Сережа изучил понятие инверсии. Инверсией в последовательности чисел sk называется пара si, sj, такая что i < j и si > sj.
Петя дал Сереже n карточек. На каждой карточке написано два числа: одно красное и одно синее. Сережа хочет применить свои знания об инверсиях к этому набору карточек.
Сережа хочет выложить перед собой карточки в таком порядке, чтобы количество инверсий было как можно меньше. При этом он считает число инверсий между числами одного цвета. Таким образом, он хочет выложить карточки в таком порядке, чтобы если рассмотреть отдельно красные числа в этом порядке и отдельно синие числа в этом порядке, суммарное число инверсий было как можно меньше.
Первая строка входного файла содержит числоn— число карточек в наборе (1 ≤ n ≤ 100 000). Следующие n строк описывают карточки, по одной на строке, i-я строка содержит целые числа ri и bi (1 ≤ ri, bi ≤ 109) — соответственно красное и синее число на i-й карточке.
Выведите одно число — минимальное возможное число одноцветных инверсий.
3
10 3
20 2
30 1
3
4
2 2
5 25
2 1
10 9
1
Имя входного файла: beautiful.in
Имя выходного файла: beautiful.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Будем называть ценностью перестановки ⟨a1..an⟩ величину (a1 a2 + a2 a3 + ... +an 1 an) mod r. Петя считает число красивым, если оно либо равно 0, либо число его делителей кратно 3. Например, 9 — красивое число (у него три делителя: 1, 3 и 9), а 6 — нет (у него 4 делителя: 1, 2, 3 и 6).
Вам даны n и r, найдите число перестановок, ценность которых является красивым числом.
Во входном файле заданы числа n и r (2 ≤ n ≤ 10, 2 ≤ r ≤ 1000).
Выведите в выходной файл число перестановок, ценность которых является красивым числом.
3 10
2
Комментарий В примере искомые перестановки — ⟨1, 3, 2⟩ и ⟨2, 3, 1⟩
Имя входного файла: vectors2.in
Имя выходного файла: vectors2.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Выведите в выходной файл все двоичные вектора, в которых нет двух единиц подряд.
Во входном файле задано число n (1 ≤ n ≤ 16).
В первой строке выходного файла выведите количество двоичных векторов длиныnв которых нет двух единиц подряд. В следующих строках выведите сами эти вектора в лексикографическом порядке по одному в строке.
3
5
000
001
010
100
101
Имя входного файла: sqroot.in
Имя выходного файла: sqroot.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайта
Введем в рассмотрение так называемые0-1матрицы размером 4 на 4. Такая матрица — это квадратная таблица, содержащая 16 чиселa i, j, каждое из которых равно 0 или 1.
Произведением двух матриц A и B называется матрица A · B = C
Квадратным корнем из матрицы A называется 0-1 матрица B, такая что B · B = A.
Задана некоторая 0-1 матрица размера 4 на 4. Вычислите ее квадратный корень или установите, что его не существует.
Входной файл содержит четыре строки, каждая из которых содержит четыре числа, каждое из этих чисел — либо 0, либо 1, j-е число i-й строки соответствует элементуa i, j заданной матрицы A.
Выведите в выходной файл квадратный корень из заданной матрицы в формате, аналогичном входному файлу. Если квадратного корня не существует — выведите в выходной файл NO SOLUTION.
Если решений несколько, выведите любое.
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 1
0 1 0 1
0 1 0 1
1 0 0 0
NO SOLUTION
Имя входного файла: jurassic.in
Имя выходного файла: jurassic.out
Ограничение по времени: 2 seconds
Ограничение по памяти: 256 мегабайта
Археологи недавно нашли фрагменты динозавра Юрского периода. Археологи решили, что они отправят кости динозавра в музей. Но, к сожалению, кости такие большие, что они не смогли по ложить их в один ящик. Поэтому они разделили скелет на отдельные кости и отправили каждый из них по-отдельности. Теперь сотрудникам музея предстоит собрать скелет. Для того, чтобы они могли это сделать, археологи отметили точки, в которых кости должны были быть соединены, специальными пометками. А именно — в каждой точке, где соединялись две кости, археологи написали на каждой из них одинаковые заглавные латинские буквы.
Однако пока археологи разбирали и упаковывали скелет, были обнаружены еще кости и они тоже были отправлены в музей. Причем они тоже могли быть соединены друг с другом, поэтому на них также могли быть пометки. Более того, археологи всегда использовали одинаковые пометки в точках на костях, которые должны были быть соединены, но они могли использовать одну и ту же пометку для различных соединений. Правда на каждой кости было не более одной пометки конкретной буквой. Теперь работники музея пытаются разобраться с этой ситуацией и найти хотя бы какое-нибудь теоретически возможное множество костей исходного скелета динозавра. А именно, они хотят найти множество костей, которое удовлетворяет следующим условиям.
- Кости, помеченные некоторой буквой, можно попарно соединить друг с другом. Иначе говоря, каждая пометка встречается четное число раз.
- Число костей в наборе максимально.
Первая строка входного файла содержит N — число костей (1 ≤ N ≤ 24). Следующие N строк содержат описание костей: каждая строка содержит непустую последовательность различных заглавных букв латинского алфавита — метки на костях.
На первой строке выходного файла выведитеL— максимальное вомзожное число костей, из которых можно собрать скелет. Вторая строка должна содержать L чисел — номера костей. Кости пронумерованы от 1 до N в порядке, в котором они заданы во входном файле.
6
ABD
EG
GE
ABE
AC
BCD
5
1 2 3 5 6
1
ABC
0
Имя входного файла: dowry.in
Имя выходного файла: dowry.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Дочь короля Флатландии собирается выйти за прекрасного принца. Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.
В коллекции принцаnбриллиантов, каждый характеризуется весомwiи стоимостьюvi. Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса большеR. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.
Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].
Первая строка содержит число n (1 < n < 32), L и R (0 < L < R < 1018). Следующие n строк описывают бриллианты и содержит по два числа — вес и стоимость соответствующего бриллианта (1 < wi, vi < 1015 ).
Первая строка вывода должна содержать k — количество бриллиантов, которые нужно подарить принцессе. Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.
Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.
3 6 8
3 10
7 3
8 2
1
2