54 lines
2.7 KiB
Markdown
54 lines
2.7 KiB
Markdown
# Домино
|
||
* Городская олимпиада по информатике в Республике Молдова.
|
||
|
||
* Год 2022
|
||
|
||
* 10 класс
|
||
|
||
* 1 задача(самая сложная)
|
||
|
||
|
||
# Задача :
|
||
|
||
В игре Домино используются 28 костяшек, представляющих собой прямоугольные пластины. Каждая костяшка идентифицируется 2 цифрами, нанесенные на пластину с помощью точек,
|
||
причем каждое число принадлежит множеству {0, 1, 2, 3, 4, 5, 6}. Маркировка указанных чисел осущевствляется путем разделения поверхности каждой костяшки на 2 одинаковые области.
|
||
Рассматривая костяшки в качестве воображаемых вагонов, из n различных костяшек можно построить "железнодорожный поезд" со следующим свойством : соседние числа любых соприкасающихся
|
||
костяшек равны между собой. Длина поезда определяется количеством костяшек m из которого он состоит. Очевидно m <= n.
|
||
|
||
Напишите программу которая определяет количество костяшек в "поезде" максимальной длины, которой можно построить из n различных костяшек.
|
||
|
||
|
||
# Входные данные
|
||
|
||
Текстовый файл domino.in содержит в 1ой строке к-во костяшек n.Следующие n строк входного файла содержат по 2 целых числа, разделенных пробелом, причем каждая из этих строк
|
||
описывает отдельную костяшку.
|
||
|
||
# Выходные данные
|
||
|
||
Текстовый файл domino.out должен содержать в единственной строке к-во костяшек m "поезда" максимальной длины.
|
||
|
||
|
||
|
||
# Пример
|
||
|
||
|
||
domino.in
|
||
|
||
4
|
||
3 6
|
||
3 5
|
||
3 0
|
||
6 6
|
||
|
||
domino.out
|
||
|
||
3
|
||
|
||
|
||
# Ограниения
|
||
|
||
Для первых 10 тестов 1 <= n <= 10. Для последующих 10 тестов 11 <= n <= 28. Ограничения на время выполнения 0.1с. На память 8мб.
|
||
|
||
# Похожие задачи
|
||
1. [46 Permutations](https://leetcode.com/problems/permutations/)
|
||
|