Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1574. Четыре краски и треугольный мир
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 27/02/1998 | Командные соревнования университета по программированию (3) |
| 10/12/2013 | Занятие 11 для начинающих (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Известно, что для любой плоской карты требуется для
раскрашивания не более 4 красок (страны с общей границей
при раскрашивании должны получить разный цвет). Предположим, что имеется
карта треугольного мира, в котором отдельные регионы (районы) стран также
имеют форму равносторонних треугольников, и некто раскрасил ее в
четыре цвета по указанным правилам. Требуется определить, сколько стран нарисовано на этой карте.
Формат входного файла: в первой строке находится длина стороны `h` (`1\ ≤\ h\ <\ 10`) большого
треугольника, в последующих `h` строках содержатся цвета (номер цвета от 1 до 4) маленьких
треугольников порядно через один пробел.
В выходной файл выводится число стран на карте.
Пример ввода (см. рисунок)
4 1 1 2 1 1 1 1 1 2 2 2 2 1 3 4 2
Пример вывода
8
