Задача A. Чёрно-белый поворот
Условие
Чёрно-белое изображение состоит из h строк по w пикселей.
Каджый пиксель имеет значение 0 или 1.
С целью экономии памяти изображение было сжато следующим образом:
для каждой строки сначала записывается значение первого пикселя,
затем длины цепочек подряд идущих нулей и единиц.
Например, строка 00100001110 будет закодирована последовательностью
0, 2, 1, 4, 3, 1.
Данное сжатое чёрно-белое изображение требуется повернуть на 90 градусов
по часовой стрелке, и вывести, используя тот же метод сжатия.
Формат входного файла
Входной файл содержит числа
w h, за которыми следует последовательность
чисел, описывающая исходное изображение.
Формат выходного файла
Выходной файл должен содержать последовательность чисел,
описывающую повёрнутое изображение.
Ограничения
w, h ≥ 1,
w × h ≤ 108, гарантируется, как исходное, так и повёрнутое
изображение содержат в сжатом виде не более
106 чисел.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 3
1 3
1 1 1 1
0 2 1
|
0 1 2
0 2 1
1 3
|
| 2 |
2 4
1 2 1 2 0 2 0 2
|
0 2 2
0 2 2
|
Задача B. Морская метеорология
Условие
Метеорологическая станция обслуживает участок моря, имеющий форму многоугольника.
Станция собирает данные с буёв, которые должны быть расположены в узлах квадратной решётки.
Другими словами, следует провести горизонтальные и вертикальные линии,
параллельные осям координат, с одним и тем же шагом, и разместить буи в точках пересечения,
попадающих внутрь многоугольника. Кроме того, вершины многоугольника также должны
попадать в узлы решётки.
Требуется по данному многоугольнику определить максимальный целочисленный
шаг решётки, при котором выполняются приведённые выше условия,
и вычислить количество буев, которые необходимо установить.
Рекомендуется рассмотреть частичные решения для следующих случаев
- Участок — треугольник.
- Участок — прямоугольник со сторонами, параллельными осям координат.
Формат входного файла
Во входном файле содержится число вершин многоугольника
N.
За ним следует
N пар целых чисел
xi yi, — координаты вершин многоугольника, перечисленных в порядке обхода.
Граница многоугольника не имеет самопересечений,
но многоугольник не обязательно является выпуклым.
Формат выходного файла
В выходном файле должно содержаться два числа — шаг сетки и количество буёв.
Ограничения
3 ≤ N ≤ 100,
−5000 ≤ xi, yi ≤ 5000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
-1 -1
-1 1
3 -1
|
2 4
|
| 2 |
4
0 0 0 1 5 1 5 0
|
1 12
|
Задача C. Переворот бокалов
Условие
На столе стоят в ряд
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
|
