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

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

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

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

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

f = open(’5.txt’)

n = int(f.readline())

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

y = x.copy()

ans = 0

cur = 1

for i in range(1, n):

    last = cur

    cur = 1

    y = x.copy()

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

    if x[0] != y[0] and x[1] != y[1] and x[0] != y[1] and x[1] != y[0]:

        cur = last + 1

    ans = max(ans, cur)

f.close()

print(ans)

Ответ: 15