Футбольный клуб «Инжир» не имеет проблем с финансированием, поэтому приобрел N полевых игроков. После долгих месяцев тренировок и тестов тренерский коллектив подробно изучил каждого игрока и собирается выбрать оптимальный стартовый состав.
Каждый игрок характеризуется тремя целыми неотрицательными числами: di — умение играть в защите, mi — умение играть в полузащите и ai — умение играть в нападении. Играть было решено по схеме 5-3-2. Это означает, что в основном составе будет 5 игроков защиты, 3 полузащитника и 2 нападающих. Цель тренерского штаба — выбрать 10 игроков так, чтобы сумма соответствующих умений была максимальна (для игрока обороны значение имеет только его умение играть в защите, аналогично для других позиций). Разумеется, каждый игрок может играть не более чем на одной позиции. Ваша задача — помочь тренерскому штабу подобрать оптимальный состав.
В первой строке входного файла находится одно целое число N — количество игроков в клубе. Следующие N строк файла содержат по три целых числа каждая di, mi и ai — умения футболиста с номером i играть в обороне, полузащите и нападении соответственно.
Выходной файл должен содержать ровно три строки. Первая строка должна содержать пять чисел — номера игроков обороны. Вторая строка должна содержать ровно три числа — номера игроков полузащиты. Третья строка должна содержать ровно два числа — номера игроков нападения. Если оптимальных ответов несколько, можно вывести любой.
10
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 1
10 1 2
10 9 8 7 6
3 4 5
1 2
10
1 5 1
3 2 2
3 3 5
2 1 3
4 4 5
2 0 2
1 1 1
4 5 1
1 3 3
4 5 4
10 5 2 6 7
1 8 9
3 4
Тесты состоят из пяти групп. Во всех группах 0 ≤ di, mi, ai ≤ 107.
После почти повсеместного закрытия казино у нас в стране, предприимчивые дельцы стали создавать клубы по игре в различные азартные, но пока еще не запрещенные игры. Одной из таких игр стала игра «Уголки».
Игроку выдается карточка, на которой нарисована таблица, состоящая из M строк и N столбцов, каждым элементом которой является целое число. Строки и столбцы пронумерованы, начиная с единицы, клетка с номером (1, 1) находится в левом верхнем углу.
Игрок может сделать несколько ходов по следующим правилам. Первым ходом он может указать на любой элемент таблицы (r1, c1), и все числа в прямоугольнике (1, 1)–(r1, c1) меняют свой знак на противоположный. Здесь первое число обозначает номер строки, а второе — номер столбца. Следующие ходы игрока аналогичны, то есть выбирается прямоугольник (1, 1)–(ri, ci) и все числа опять меняют знак, однако каждый следующий прямоугольник должен полностью содержать предыдущий выбранный, но не совпадать с ним. Количество ходов при этом естественным образом ограничено размерами таблицы. При желании ходы можно и не выполнять совсем.
Например, если таблица состоит из 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 пар чисел (ri, ci), описывающих сам алгоритм.
Если дающих наилучший результат алгоритмов несколько, выведите любой.
2 3
3 6 4
1 -2 -7
21
2
1 3
2 3
4 4
2 -1 -5 -1
1 -3 -3 -1
0 -5 1 1
-1 -1 0 2
22
2
2 1
4 3
Тесты состоят из четырех групп.
Недавно у градообразующего предприятия города Флатвилля сменилось руководство. Новый генеральный директор не очень-то разбирается в техническом производстве, поэтому заключает все договоры подряд. После этого (чтобы спасти положение) в дело вступает директор по расписаниям, который решает, какие из этих заказов будут выполнены, а за какие придется платить неустойку.
Каждый заказ обладает тремя параметрами: di — максимальный номер дня, к которому этот заказ должен быть выполнен; ai — доход, который получает завод, если выполняет заказ в срок; bi — неустойка, которую выплачивает завод в случае, если заказ не был выполнен к дню di включительно. Нумерация дней ведется со следующего после заключения договоров дня. Известно, что на выполнение одного заказа завод тратит непрерывный отрезок из ровно K дней, причем в один момент времени завод может быть занят только одним заказом.
В итоге перед директором по расписаниям стоит непростая задача: выбрать какие заказы выполнить (и в какое время), а за какие проще сразу заплатить неустойку.
Конкурирующая фирма хочет данное предприятие разорить. У директора конкурирующей фирмы есть возможность перехватить любое число заказов. Все остальные заказы достанутся предприятию (даже если они явно ему не выгодны). Требуется помочь директору конкурирующей фирмы выбрать такое подмножество имеющихся потенциальных заказов для перехвата, чтобы при оптимальной работе директора по расписаниям (то есть при выборе им наилучшей стратегии выполнения оставшихся заказов) доход предприятия был минимальным (он может быть и отрицательным).
В первой строке входного файла записано одно число G — номер группы тестов. Во второй строке задано два числа N и K. Следующие N строк содержат описание заказа: di, ai, bi. Числа K, ai, bi целые положительные и не превосходят 1 000. Числа di целые положительные и не превосходят 100 000.
В первой строке выведите значение искомого дохода (убытка) предприятия. Следующая строка должна содержать ровно N нулей и единиц, разделенных пробелами. Если на i-й позиции стоит 0, это означает, что этот заказ должна перехватить конкурирующая фирма; если же стоит 1, то заказ достанется предприятию.
1
4 1
1 9 9
1 4 4
1 3 3
1 3 3
-2
0 1 1 1
6
8 4
1 10 3
2 10 3
3 10 3
4 10 3
5 8 3
6 7 2
6 5 5
7 6 1
-10
1 1 1 1 1 1 1 1
Тесты состоят из девяти групп.
В Москве происходит Важное Событие. Посмотреть на Важное Событие съехалось множество людей со всей страны. Во избежание давки и соблюдения порядка полицией была организована очередь, растянувшаяся по набережной Москвы-реки от станции метро X аж до станции метро Y!
Вся очередь разделена на N секторов с помощью перегородок с турникетами. Вход на Важное Cобытие расположен перед первой перегородкой, т.е. попасть туда можно только из сектора 1.
Раз в секунду через каждую перегородку, перед которой есть хотя бы один человек, в сторону События через турникет пропускают одного человека (то есть из сектора i в сектор i - 1, и из сектора 1 — на само Событие). Внутри сектора люди передвигаются существенно быстрее, поэтому этим временем можно пренебречь.
По известному количеству людей в секторах определите, через сколько секунд на Важное Событие попадет последний человек.
В первой строке заданы число секторов N и число непустых секторов M (1 ≤ N ≤ 109, 0 ≤ M ≤ 105). В следующих M строках записаны числа ai и bi — номер i-того непустого сектора и bi — количество человек в нем (1 ≤ a1 < a2 < ... < aM ≤ N, 1 ≤ bi ≤ 109)
Выведите одно целое число — время в секундах, через которое все люди смогут попасть на Важное Событие.
3 2
1 1
3 2
4
3 2
2 2
3 2
5
Тесты состоят из четырёх групп.
Вася участвовал в недавнем эксперименте: проведи 8 часов без гаджетов. Для того чтобы убить время, он стал проделывать со случайной строкой, состоящей только из нулей и единиц, следующую процедуру. Каждый ноль этой строки он заменял на строку S, тоже состоящую из нулей и единиц, а каждую единицу — на строку T, опять же из нулей и единиц. Строки S и T он выписал заранее. С полученной строкой он опять проделывал ту же самую процедуру, не меняя при этом строки S и T. За 8 часов он успел таким образом сделать K преобразований.
Помогите Васе определить, на каком по счету месте в итоговой строке окажется N-я единица, если гарантируется, что N единиц в этой строке есть. Нумерация символов в строке, как и подсчет единиц, ведется с единицы.
В первой строке входного файла находятся числа K (0 ≤ K ≤ 100 000) и N (1 ≤ N ≤ 1018). Во второй строке файла находится исходная строка. В третьей — строка S, в четвертой — строка T. Длина каждой из строк не превосходит 1 000 символов.
Выведите одно число — номер N-й единицы в итоговой строке. Гарантируется, что ответ не превосходит 1018.
1 3
01
10
11
4
3 10
0
101
01
17
Тесты состоят из пяти групп.