--->
8 задач
<---
Источники
#513
Темы:
[Двумерные массивы]
[Клеточная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Из шахматной доски по границам клеток выпилили связную (не распадающуюся на части) фигуру без дыр. Требуется определить ее периметр.
Входные данные
Сначала вводится число \(N\) (1 ≤ \(N\) ≤ 64) – количество выпиленных клеток. В следующих \(N\) строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.
Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).
Пояснения к примерам
1) Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.
2) Вырезана одна клетка. Ее периметр равен 4.
Примеры
Входные данные
3 1 1 1 2 2 1
Выходные данные
8
Входные данные
1 8 8
Выходные данные
4
#594
Темы:
[Двумерные массивы]
[Клеточная геометрия]
Источники:
[
Личные олимпиады,
Московская олимпиада школьников,
10-11 классы,
2006,
1 день,
Задача D
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Вася нарисовал на клетчатой бумаге многоугольник, все стороны которого проходят по линиям сетки. После этого в каждой клетке он написал число, равное количеству сторон данной клетки, которые принадлежат сторонам многоугольника. Затем он стер многоугольник так, что остался листок бумаги, в каждой клетке которого написано число.
Восстановите нарисованный Васей многоугольник.
Входные данные
В первой строке входных данных содержатся два натуральных числа: \(Y\) - количество строк и \(X\) - количество столбцов листа (3 <= \(Y\) <= 1000, 3 <= \(X\) <= 1000). В каждой из следующих \(Y\) строк задается по \(X\) целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.
Выходные данные
Выведите искомый многоугольник в следующем формате.
Выходные данные должны содержать \(Y\) строк по 2\(X\)-1 символов в каждой (по одному символу на клетку и линию между клетками).
В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.
Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.
Примеры
Входные данные
4 4 0 0 1 0 0 2 3 1 1 3 2 1 0 1 1 0
Выходные данные
...._.. .._|.|. .|_._|. .......
#1028
| 0 | 2 | 2 | 2 | 2 |
| 0 | 2 | 2 | 2 | 2 |
| 1 | 1 | 2 | 2 | 2 |
| 1 | 1 | 0 | 0 | 0 |
На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.
Получившуюся ситуацию записали в таблицу чисел (каждой клетке поля соответствует клетка таблицы). Если клетка поля не закрыта прямоугольником, то в соответствующую клетку таблицы записали число 0. Если же клетка закрыта одним или несколькими прямоугольниками, то в соответствующую клетку таблицы записали число, соответствующее номеру самого верхнего прямоугольника, закрывающего эту клетку.
По содержимому таблицы требуется определить положение и размеры прямоугольников.
Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
Входные данные
В первой строке входного файла записаны целые числа N, M, K (1N200, 1M200, 1K255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.
Выходные данные
В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.
Примеры
Входные данные
4 5 2 0 2 2 2 2 0 2 2 2 2 1 1 2 2 2 1 1 0 0 0
Выходные данные
0 0 2 2 1 1 5 4
#1337
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2009,
Задача A
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Для проведения олимпиады школьников по информатике требуется соединить компьютеры в сеть. Организаторы олимпиады разработали схему соединения компьютеров. В соответствии с этой схемой некоторые пары компьютеров должны быть соединены кабелем, и сигнал сможет дойти по кабелям от любого компьютера до любого другого, возможно, через другие компьютеры.
Некоторые компьютеры могут быть соединены циклически. Цикл называется простым, если каждый компьютер из этого цикла соединён ровно с двумя другими компьютерами этого цикла, и в этот цикл никакой кабель не входит более одного раза. Некоторые кабели могут не входить ни в какой цикл.
Известно, что в разработанной схеме никакой кабель не принадлежит двум простым циклам одновременно.
Организаторам олимпиады поручено разместить компьютеры в зале соревнований. При размещении должны выполняться следующие условия:
1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.
2.Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 106.
3.Никакие два компьютера не располагаются в одной точке.
4.Кабели являются отрезками прямых.
5.Кабели не пересекаются между собой и не проходят через точки размещения компьютеров, к которым они не подключены.
Требуется написать программу, выполняющую размещение компьютеров по заданному описанию схемы.
Входные данные
В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.
Выходные данные
Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.
Примечания
Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.
Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.
Пример входных и выходных данных
|
Ввод |
Вывод |
|
13 14 11 12 11 13 1 3 3 5 5 8 8 9 8 6 6 3 4 6 4 2 6 10 10 11 10 7 7 4 |
1 0 3 0 1 1 3 1 0 2 2 2 4 2 1 3 1 4 3 3 3 4 2 5 4 5 |
Выбрано
:
|