--->
4 задач
<---
Страница:
1
Отображать по:
#40
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
|
+ |
||||
|
+ |
(4,3) |
+ |
||
|
+ |
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
- закрасить клетку (i,j) в черный цвет.
- для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
Входные данные
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 105), а затем сами команды. Команды записаны по одной в строке в следующем формате:
Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).
1 ≤ i ≤ N, 1 ≤ j ≤ M.
Выходные данные
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.
Оценка задачи
1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.
Примеры
Входные данные
5 5 6 Color 4 2 Neighbors 4 3 Color 2 3 Color 3 3 Neighbors 4 3 Neighbors 5 1
Выходные данные
3 4 4 1 4 4 3 3 5 3 4 4 1 4 4 1 3 5 3 2 5 2 4 1
#866
Темы:
[Двумерные массивы]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига Б,
Задача G
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Прямоугольную таблицу, состоящую из N строк и M столбцов, раскрашивают следующим образом. Каждый столбец таблицы и каждую строку красят либо в синий, либо в желтый цвет. В итоге клетки, оказавшиеся на пересечении синего столбца и синей строки оказываются синими, желтого столбца и желтой строки — желтыми, а клетки на пересечении синего столбца и желтой строки, или, наоборот, желтого столбца и синей строки — зелеными.
Раскраска всех клеток таблицы (или просто сама таблица) называется правильной, если она может быть получена описанным выше способом.
Вам дана прямоугольная таблица, которую нужно раскрасить таким образом. Про некоторые клетки известно, какого цвета они должны быть, а остальные клетки могут в итоге быть любого цвета. Определите, как нужно раскрасить остальные клетки таблицы, чтобы раскраска была правильной.
Входные данные
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:
0 — клетка может в итоге быть любого цвета
1 — клетка должна быть синей
2 — клетка должна быть желтой
3 — клетка должна быть зеленой
Выходные данные
Выведите N строк по M чисел в каждой — раскраску таблицы, которая является правильной, и в которой нужные клетки имеют нужный цвет. Если вариантов несколько, выведите любой из них. Если покрасить таким образом таблицу невозможно, выведите одно число 0.
Примеры
| Входные данные | Выходные данные |
| 3 4 1 0 0 0 3 0 0 0 0 0 0 0 | 1 1 1 1 3 3 3 3 1 1 1 1 |
| 2 2 3 3 3 3 | 3 3 3 3 |
| 2 2 2 2 2 3 | 0 |
#1242
Темы:
[Задачи на моделирование]
[Двумерные массивы]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.
Когда луч приходит в угол, через который проходят зеркальные стены, дальше он идет так, как показано на рисунках (серым цветом показаны клетки, которые окружены зеркальными стенами). Аналогичным образом луч ведет себя, когда приходит на границу лабиринта.
Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).
Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.
Примеры
Входные данные
3 5 X.... ..... .....
Выходные данные
XXXXX XXXXX XXXXX
Входные данные
3 3 ... ..X ...
Выходные данные
/X\ X.X \X/
#3593
Темы:
[Двумерные массивы]
[Словари]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2011,
Лига Б,
Задача A
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.
В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.
Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».
По заданному набору доминошек определите, сколько пар «дружных доминошек» можно составить из него. Пары, отличающиеся хотя бы одной доминошкой, считаются различными. По-разному составленная пара из одних и тех же доминошек считается один раз.
Входные данные
В первой строке входного файла содержится натуральное число N — количество доминошек (1 ≤ N ≤ 40 000).
В каждой из последующих строк содержится описание доминошки: два целых числа X и Y (0 ≤ X, Y ≤ 6) — количество точек на каждой из половинок доминошки.
Выходные данные
Выведите одно число — количество пар дружных доминошек.
Примечание
Во втором тесте дружными являются следующие пары:
1-2 2-3
1-2 3-1
2-3 3-1
2-3 4-3
2-3 4-3
3-1 4-3
3-1 4-3
4-3 4-3
Примеры
Входные данные
2 1 2 2 1
Выходные данные
1
Входные данные
5 1 2 2 3 3 1 4 3 4 3
Выходные данные
8
Страница:
1
Отображать по:
Выбрано
:
|