Задача A. Маршрутка ≡

Автор:unknown
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

Маршрутное такси на P посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров. Каждый пассажир имеет цель — попасть на некоторую остановку, расположенную дальше по маршруту.

На каждой остановке:

Каждый пассажир платит водителю 5 рублей. На первой остановке, в отличие от остальных, водитель по своему усмотрению ограничивает количество севших пассажиров f. Требуется определить наибольший доход, который может получить водитель, выбрав оптимальное значение f.

Формат входного файла

В первой строке входного файла содержатся числа N и P. В следующих N − 1 строках находятся числа Ki di,1… di,Ki — количество пассажиров на очередной остановке и цель каждого пассажира. (На конечной остановке пассажиры не садятся).

Формат выходного файла

Выходной файл должен содержать единственное целое число — максимальный доход водителя в рублях.

Ограничения

2 ≤ N ≤ 50, 1 ≤ P ≤ 20

0 ≤ Ki < P, i < di,j ≤ N

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 3
2 2 4
3 3 3 3
2 4 4

30

Задача B. 0 - a, 1 - ab ≡

Автор:algolist
Входной файл: input.txt   Ограничение времени:4 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

Формат входного файла

Первая строка входного файла содержит числа N M.

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

Формат выходного файла

Выходной файл должен содержать единственный символ Y или N.

Ограничения

1 ≤ N, M ≤ 10000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
101
bab
 
Y
2 
4 3
1001
bab
 
N

Задача C. Переворот бокалов ≡

Автор:Кленин А.С.
Входной файл: input.txt   Ограничение времени:10 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

На столе стоят в ряд N бокалов, пронумерованных слева направо от 1 до N. Первоначально все бокалы стоят дном вниз. Над бокалами можно выполнить операцию переворот. За один переворот ровно M любых бокалов переворачиваются так, что те бокалы, которые стояли дном вниз, оказываются перевернутыми вверх дном, а остальные из M бокалов ставятся вниз дном. Требуется за минимальное количество переворотов добиться того, чтобы все бокалы оказались перевернутыми вверх дном, или определить, что это невозможно.

Формат входного файла

Входной файл содержит числа N и M.

Формат выходного файла

Выходной файл должен в первой строке содержать число переворотов K, а в последующих K строках - разделенные пробелами номера бокалов, которые нужно перевернуть при очередном перевороте. Если перевернуть все бокалы невозможно, то выходной файл должен содержать единственное число 0 (ноль).

Ограничения

1 < N < 1000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
7 3
 
3
1 2 3
3 4 5
3 6 7
0.038s 0.005s 11