#111522

Раскраска автобусов

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2013, Задача E ]

Ваш друг по-прежнему работает главным экономистом в компании, владеющей сетью маршруток. В связи с новыми веяниями по введению корпоративной раскраски на транспортных средствах, компания решила окрасить все свои маршрутки в новом стиле. Директор компании своим личным распоряжением приказал принять следующий способ окраски. Сначала все автобусы окрашиваются фоновой красной краской, поверх которой наносится серый узор.

Узор создается следующим образом. Если бы борт маршрутки был бы бесконечным в две стороны: вправо и вверх, — то узор рисовали бы так. Разделим борт на бесконечное количество вертикальных полос одинаковой (единичной) ширины, занумеруем их слева направо, начиная с единицы. Полосы с нечетными номерами красить серой краской вообще не будем. Полосы, номера которых делятся на два, но не делятся на четыре, закрасим снизу до высоты, равной единице длины (т.е. образуется серый квадрат). Полосы, номера которых делятся на четыре, но не делятся на восемь, закрасим снизу до высоты, равной двум единицам длины; полосы, номера которых делятся на восемь, но не делятся на 16 — до высоты, равной 3; номера которых делятся на 16, но не делятся на 32 — до высоты, равной 4, и т.д.

Получим следующий узор:

Естественно, у реальных маршруток ширина борта ограничена (высоту мы для простоты будем считать неограниченной). Можно было бы на каждой маршрутке рисовать начало такого узора, но это не интересно — поэтому было решено для каждой маршрутки выбрать два числа, \(l\) и \(r\), и нарисовать на борту фрагмент этого узора с \(l\)-ого столбика по \(r\)-ый включительно. Определите, сколько на это уйдет серой краски, считая, что единица краски уходит на единичный квадрат узора.

Входные данные

Во входном файле находятся два числа — \(l\) и \(r\). Гарантируется, что \(1\leq l\leq r \leq 10^{18}\).

Выходные данные

Выведите в выходной файл одно число — общую площадь фрагмента узора между \(l\)-ым и \(r\)-м столбиками включительно.

Примечание

В примере используются столбики с 5 по 10 включительно. Их площади — соответственно 0, 1, 0, 3, 0, 1 единичных квадратов; соответственно, суммарная их площадь равна 5.

Среди тестов будут такие, в которых \(r\leq 10^5\), общей стоимостью 40 баллов, и тесты с \(r>10^5\), но \(r-l\leq 10^5\), общей стоимостью еще 20 баллов.

Примеры

Входные данные

5 10

Выходные данные

#111523

Руммикуб

Темы: [Динамическое программирование по профилю]

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2013, Задача F ]

В игре «Руммикуб» используются фишки, которые бывают четырех различных цветов, и на каждой из которых написано одно натуральное число от 1 до 13. Для каждого числа и для каждого цвета в наборе фишек есть ровно две соответствующие фишки, т.е. всего в наборе \(8\cdot 13 = 104\) фишки.

Число, написанное на фишке, будем называть ее достоинством; цвета будем обозначать латинскими буквами A, B, C и D, и каждую фишку будем обозначать, записывая сначала ее цвет, а потом — ее достоинство. Например, C12 — это фишка цвета C и достоинством 12.

Комбинацией в игре называется набор из как минимум трех фишек, удовлетворяющий любому из следующих условий:

Достоинства всех фишек одинаковы, а цвета — попарно различны; или
Цвета всех фишек одинаковы, а достоинства являются последовательными натуральными числами.

Например, следующие наборы фишек являются комбинациями:

C12, A12, B12;
C12, A12, B12, D12;
C5, C6, C7;
A3, A4, A5, A6, A7.

При этом следующие наборы не являются комбинациями:

A3, B3 (слишком мало фишек);
A3, B3, C3, D3, B3 (цвета повторяются);
A3, A4, A4, A5, A6 (достоинства повторяются);
A3, A4, A6, A7, A8 (число 5 пропущено).

Одна из основных задач в руммикубе состоит в том, чтобы данный набор фишек распределить на комбинации так, чтобы каждая фишка входила ровно в одну комбинацию. Напишите программу, которая будет это делать.

Входные данные

В первой строке входного файла находится одно натуральное число \(K\) — количество фишек. Далее следуют \(K\) строк, на каждой из которых находится описание одной фишки — цвет и достоинство.

Гарантируется, что эти фишки являются корректным подмножеством фишек из некоторого комплекта для игры в руммикуб; т.е. гарантируется, что каждый цвет — это латинская заглавная буква от A до D, что каждое достоинство — это натуральное число, не превосходящее 13, и что для для каждой пары (цвет, достоинство) в наборе есть не более двух таких фишек.

Выходные данные

Если данный набор фишек можно разбить на комбинации так, чтобы каждая фишка входила ровно в одну комбинацию, то в первую строку выходного файла выведите одно число \(M\) — количество комбинаций в вашем решении. Далее выведите \(M\) строк, в \(i\)-ой из которых выведите \(i\)-ую комбинацию. А именно, сначала выведите количество фишек в комбинации, а потом сами фишки, разделенные между собой и отделенные от количества фишек пробелами. В пределах каждой комбинации фишки можете выводить в произвольном порядке; комбинации также можете выводить в произвольном порядке.

Если есть несколько решений, выведите любое. Если решений нет, то выведите в выходной файл одно число -1.

Примеры

Входные данные

3
A2
A3
A5

Выходные данные

-1

Входные данные

3
A2
A4
A3

Выходные данные

1
3 A2 A4 A3

Входные данные

7
A12
A13
A13
B13
C13
D13
A11

Выходные данные

2
3 A11 A12 A13
4 A13 B13 C13 D13

#111531

Футбол

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2011-2012, Заключительный этап, Тур 1, Задача A ]

Футбольный клуб «Инжир» не имеет проблем с финансированием, поэтому приобрел N полевых игроков. После долгих месяцев тренировок и тестов тренерский коллектив подробно изучил каждого игрока и собирается выбрать оптимальный стартовый состав.

Каждый игрок характеризуется тремя целыми неотрицательными числами: d_i — умение играть в защите, m_i — умение играть в полузащите и a_i — умение играть в нападении. Играть было решено по схеме 5-3-2. Это означает, что в основном составе будет 5 игроков защиты, 3 полузащитника и 2 нападающих. Цель тренерского штаба — выбрать 10 игроков так, чтобы сумма соответствующих умений была максимальна (для игрока обороны значение имеет только его умение играть в защите, аналогично для других позиций). Разумеется, каждый игрок может играть не более чем на одной позиции. Ваша задача — помочь тренерскому штабу подобрать оптимальный состав.

Входные данные

В первой строке входного файла находится одно целое число N — количество игроков в клубе. Следующие N строк файла содержат по три целых числа каждая d_i, m_i и a_i — умения футболиста с номером i играть в обороне, полузащите и нападении соответственно.

Выходные данные

Выходной файл должен содержать ровно три строки. Первая строка должна содержать пять чисел — номера игроков обороны. Вторая строка должна содержать ровно три числа — номера игроков полузащиты. Третья строка должна содержать ровно два числа — номера игроков нападения. Если оптимальных ответов несколько, можно вывести любой.

Примеры тестов

Входные данные

Выходные данные

10 9 8 7 6
3 4 5
1 2

Входные данные

Выходные данные

10 5 2 6 7
1 8 9
3 4

Примечание

Тесты состоят из пяти групп. Во всех группах 0 ≤ d_i, m_i, a_i ≤ 10⁷.

Тесты 1–2, из условия, оцениваются в 0 баллов.
В тестах этой группы N = 10. Эта группа оценивается в 20 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 10 ≤ N ≤ 40. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
В тестах этой группы 10 ≤ N ≤ 10 000. Эта группа также оценивается в 20 баллов, они начисляются только при прохождении всех тестов группы.
10 ≤ N ≤ 500 000. Баллы за тесты этой группы начисляются только при прохождении всех тестов всех предыдущих групп. Некоторые тесты этой группы объединяются в подгруппы, тесты за каждую подгруппу ставятся только при прохождении всех тестов подгруппы.

#111532

Уголки

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2011-2012, Заключительный этап, Тур 1, Задача C ]

После почти повсеместного закрытия казино у нас в стране, предприимчивые дельцы стали создавать клубы по игре в различные азартные, но пока еще не запрещенные игры. Одной из таких игр стала игра «Уголки».

Игроку выдается карточка, на которой нарисована таблица, состоящая из M строк и N столбцов, каждым элементом которой является целое число. Строки и столбцы пронумерованы, начиная с единицы, клетка с номером (1, 1) находится в левом верхнем углу.

Игрок может сделать несколько ходов по следующим правилам. Первым ходом он может указать на любой элемент таблицы (r₁, c₁), и все числа в прямоугольнике (1, 1)–(r₁, c₁) меняют свой знак на противоположный. Здесь первое число обозначает номер строки, а второе — номер столбца. Следующие ходы игрока аналогичны, то есть выбирается прямоугольник (1, 1)–(r_i, c_i) и все числа опять меняют знак, однако каждый следующий прямоугольник должен полностью содержать предыдущий выбранный, но не совпадать с ним. Количество ходов при этом естественным образом ограничено размерами таблицы. При желании ходы можно и не выполнять совсем.

Например, если таблица состоит из 10 строк и 9 столбцов, то возможна в том числе такая последовательность ходов: (2, 2)–(4, 4)–(4, 6)–(5, 6).

После того как все желаемые ходы выполнены, подсчитывается результат игры — сумма значений элементов преобразованной таблицы. Если сумма положительная, то игрок получает от заведения соответствующую сумму денег, а если отрицательная — платит ее.

Помогите игроку добиться наилучшего результата: выиграть как можно больше или хотя бы проиграть как можно меньше.

Входные данные

В первой строке входного файла заданы два натуральных числа M и N (M ≤ 1 000, N ≤ 1 000). Каждая из следующих M строк содержит N целых чисел, по модулю не превышающих 1 000, — элементы таблицы.

Выходные данные

В первой строке выходного файла выведите максимальную сумму, которую можно получить с помощью оптимальной стратегии игры по описанным правилам. Во второй строке выведите целое число K — количество действий в алгоритме, дающем наилучший результат. В следующих K строках выведите последовательность из K пар чисел (r_i, c_i), описывающих сам алгоритм.

Если дающих наилучший результат алгоритмов несколько, выведите любой.

Примеры тестов

Входные данные

2 3
3 6 4
1 -2 -7

Выходные данные

Входные данные

4 4
2 -1 -5 -1
1 -3 -3 -1
0 -5 1 1
-1 -1 0 2

Выходные данные

Примечание

Тесты состоят из четырех групп.

Тесты 1–2, из условия, оцениваются в 0 баллов.
В тестах этой группы M = 1, 1 ≤ N ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ M ≤ 100, 1 ≤ N ≤ 100. Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый тест оценивается независимо от других.

#111533

Банкротство

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2011-2012, Заключительный этап, Тур 1, Задача D ]

Недавно у градообразующего предприятия города Флатвилля сменилось руководство. Новый генеральный директор не очень-то разбирается в техническом производстве, поэтому заключает все договоры подряд. После этого (чтобы спасти положение) в дело вступает директор по расписаниям, который решает, какие из этих заказов будут выполнены, а за какие придется платить неустойку.

Каждый заказ обладает тремя параметрами: d_i — максимальный номер дня, к которому этот заказ должен быть выполнен; a_i — доход, который получает завод, если выполняет заказ в срок; b_i — неустойка, которую выплачивает завод в случае, если заказ не был выполнен к дню d_i включительно. Нумерация дней ведется со следующего после заключения договоров дня. Известно, что на выполнение одного заказа завод тратит непрерывный отрезок из ровно K дней, причем в один момент времени завод может быть занят только одним заказом.

В итоге перед директором по расписаниям стоит непростая задача: выбрать какие заказы выполнить (и в какое время), а за какие проще сразу заплатить неустойку.

Конкурирующая фирма хочет данное предприятие разорить. У директора конкурирующей фирмы есть возможность перехватить любое число заказов. Все остальные заказы достанутся предприятию (даже если они явно ему не выгодны). Требуется помочь директору конкурирующей фирмы выбрать такое подмножество имеющихся потенциальных заказов для перехвата, чтобы при оптимальной работе директора по расписаниям (то есть при выборе им наилучшей стратегии выполнения оставшихся заказов) доход предприятия был минимальным (он может быть и отрицательным).

Входные данные

В первой строке входного файла записано одно число G — номер группы тестов. Во второй строке задано два числа N и K. Следующие N строк содержат описание заказа: d_i, a_i, b_i. Числа K, a_i, b_i целые положительные и не превосходят 1 000. Числа d_i целые положительные и не превосходят 100 000.

Выходные данные

В первой строке выведите значение искомого дохода (убытка) предприятия. Следующая строка должна содержать ровно N нулей и единиц, разделенных пробелами. Если на i-й позиции стоит 0, это означает, что этот заказ должна перехватить конкурирующая фирма; если же стоит 1, то заказ достанется предприятию.

Примеры тестов

Входные данные

Выходные данные

-2
0 1 1 1

Входные данные

Выходные данные

-10
1 1 1 1 1 1 1 1

Примечание

Тесты состоят из девяти групп.

Тесты 1–2, из условия, оцениваются в 0 баллов.
В тестах этой группы 1 ≤ N ≤ 100 000, K = 1, d_i = 1, a_i = b_i для всех i. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 100 000, K = 1, d_i = 1 для всех i. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 100 000, a_i = b_i, d_i = d_j, для всех i, j. То есть все заказы имеют одинаковый срок выполнения, и для всех заказов прибыль равна неустойке. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 1 000, d_i = d_j, для всех i, j. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 100 000, d_i = d_j, для всех i, j. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 15. Эта группа оценивается в 10 баллов, баллы начисляются только при прохождении всех тестов группы.
В тестах этой группы 1 ≤ N ≤ 100, a_i = b_i. На этой группе будут тестироваться только решения, прошедшие хотя бы одну из групп 1 - 6. Группа состоит из 20 тестов, за каждый тест участник получает либо 0, либо 1 балл. Участник получает за тест 1 балл, если его ответ корректен и никакое другое решение (другого участника или жюри) не находит ответ лучше.
В тестах этой группы 1 ≤ N ≤ 100. На этой группе будут тестироваться только решения, прошедшие хотя бы одну из групп 1 - 6. Группа состоит из 20 тестов, за каждый тест участник получает либо 0, либо 1 балл. Участник получает за тест 1 балл, если его ответ корректен и никакое другое решение (другого участника или жюри) не находит ответ лучше.