Задача A. Обход матрицы: спиральный обход

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

Условие

По данному числу N требуется заполнить квадратную матрицу размером NxN целыми числами от 1 до N2; следующим образом:

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

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

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

Выходной файл должен содержать заполненную матрицу в виде N строк по N целых чисел в каждой.

Ограничения

1 <= N <= 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
4 3
2
3
1 2 3
8 9 4
7 6 5

Задача B. Обход матрицы: обход 'змейкой'

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

Условие

По данному числу N требуется заполнить квадратную матрицу размером NxN целыми числами от 1 до N2; следующим образом:

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

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

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

Выходной файл должен содержать заполненную матрицу в виде N строк по N целых чисел в каждой.

Ограничения

1 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
4 3
2
3
1 2 3
6 5 4
7 8 9

Задача C. 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

Задача D. Маршрутка

Автор: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

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

Автор:Кленин А.С.
Входной файл: 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.059s 0.005s 15