Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №1

Просмотров 7 Комментарии 0

На столе выложили цепочку из $N$ костяшек по принципу тримино (то же, что и домино, но на костяшках по $3$ числа) . Под костяшкой понимается тройка любых неотрицательных чисел, каждое не превышает $100$ . В наборе могут быть одинаковые костяшки. Переставлять местами костяшки нельзя, но можно поворачивать любое количество костяшек, получая, например, из костяшки 1-2-3 костяшку 1-3-2 или 3-1-2 и так далее. Определите максимальную длину цепочки костяшек тримино, которую можно получить с помощью переворачиваний. Под цепочкой понимается последовательность костяшек, в которой соприкающиеся числа каждой костяшки равны. (Рисунок ниже)

Входные данные

Дан входной файл, он содержит в первой строке количество троек $N$ $(1 ≤ N ≤ 100000)$ . Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $100$ .

В ответе укажите одно число: искомое значение для файла.

Первое решение:

f = open("2.txt")
n = int(f.readline())

x = [int(s) for s in f.readline().split()]
y = x.copy()

cur_0, cur_1, cur_2 = 1, 1, 1  # curr_i - макс длина цепочки такой,
# что последняя триминошка присоединяется своим i-тым концом
ans = 1

for i in range(1, n):
    last_0, last_1, last_2 = cur_0, cur_1, cur_2
    cur_0, cur_1, cur_2 = 1, 1, 1

    x = [int(s) for s in f.readline().split()]

    if x[0] == y[0]:
        cur_0 = max(cur_0, last_1 + 1, last_2 + 1)
    if x[0] == y[1]:
        cur_0 = max(cur_0, last_0 + 1, last_2 + 1)
    if x[0] == y[2]:
        cur_0 = max(cur_0, last_0 + 1, last_1 + 1)

    if x[1] == y[0]:
        cur_1 = max(cur_1, last_1 + 1, last_2 + 1)
    if x[1] == y[1]:
        cur_1 = max(cur_1, last_0 + 1, last_2 + 1)
    if x[1] == y[2]:
        cur_1 = max(cur_1, last_0 + 1, last_1 + 1)

    if x[2] == y[0]:
        cur_2 = max(cur_2, last_1 + 1, last_2 + 1)
    if x[2] == y[1]:
        cur_2 = max(cur_2, last_0 + 1, last_2 + 1)
    if x[2] == y[2]:
        cur_2 = max(cur_2, last_0 + 1, last_1 + 1)

    ans = max(ans, cur_0, cur_1, cur_2)













































































































































































































    y = x.copy()

f.close()
print(ans)

Ответ: 8