Задача A. Обход матрицы: спиральный обход
Условие
По данному числу
N требуется заполнить квадратную матрицу размером
Nx
N
целыми числами от 1 до N
2; следующим образом:
- в левом верхнем углу находится число 1
- далее числа располагаются по спирали, закрученной вправо и внутрь
Формат входного файла
Входной файл содержит целое число
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. Обход матрицы: обход 'змейкой'
Условие
По данному числу
N требуется заполнить квадратную матрицу размером
Nx
N
целыми числами от 1 до N
2; следующим образом:
- в левом верхнем углу находится число 1
- далее числа распологаются "змейкой", т.е. по возрастанию слева направо
в нечётных строках, и справа налево — в чётных
Формат входного файла
Входной файл содержит целое число
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
Условие
Дана строка s, состоящая из N символов 0 или 1,
а также строка t, состоящая из M символов a или b,
Над строкой s разрешено производить следующие действия:
- заменять символ 0 на строку из одного или более символов a
- заменять символ 1 на строку из одного или более символов a,
либо на строку из одного или более символов b
Требуется определить, можно ли преобразовать строку 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. Маршрутка
Условие
Маршрутное такси на 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. Переворот бокалов
Условие
На столе стоят в ряд
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
|
