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