Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1549. Доска объявлений
Другие задачи на графыОлимпиадные задачи на русском языке
| 19/03/2011 | Южно-Уральский открытый командный чемпионат по программированию (F) |
| 12/07/2019 | Лето 2019 - 6 (командное) (J) |
Ограничения: время – 1000ms/2000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В коридоре общежития студентов-химиков имени товарища Семашко висит доска для объявлений
размером `n\ times\ m`. Доска покрыта объявлениями размером `1\ times\ 2`,
так что каждая клетка доски оказалась покрыта объявлениями в 2 слоя.
Необходимо убрать половину объявлений, чтобы оставшиеся объявления были полностью видны и
на доске не было свободного места, т.е. чтобы каждая клетка доски
была покрыта объявлениями в один слой.
Первая строка содержит два целых числа `n` и `m` (`2\ ≤\ n,m\ ≤\ 500`,
хотя бы одно из чисел `n` или `m` четно).
Далее следует `n*m` строк, каждая строка содержит три целых числа `r_i`, `c_i` и `d_i`,
где `(r_i,\ c_i)` – координаты верхней левой клетки, покрытой `i`-м объявлением,
`d_i=0` если объявление расположено горизонтально, и `d_i=1` если объявление расположено вертикально.
Вывести строку, содержащую `n*m/2` номеров удаляемых объявлений в порядке возрастания номеров.
Пример ввода 1
2 2 1 1 0 1 1 1 2 1 0 1 2 1
Пример вывода 1
1 3
Пример ввода 2
2 3 1 1 0 1 1 1 2 1 0 1 2 0 1 3 1 2 2 0
Пример вывода 2
1 3 5
