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

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

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

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

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

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

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

f = open(’4.txt’)

n = int(f.readline())

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

y = x.copy()

ans = 0

cur, cur_p = 1, 1

for i in range(1, n):

    last, last_p = cur, cur_p

    cur, cur_p = 1, 1

    y = x.copy()

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

    if x[0] == y[1] or x[0] == 0 or y[1] == 0:

        cur = max(cur, last + 1)

    if x[0] == y[0] or x[0] == 0 or y[0] == 0:

        cur = max(cur, last_p + 1)

    if x[1] == y[1] or x[1] == 0 or y[1] == 0:

        cur_p = max(cur_p, last + 1)

    if x[1] == y[0] or x[1] == 0 or y[0] == 0:

        cur_p = max(cur_p, last_p + 1)

    ans = max(ans, cur, cur_p)

f.close()

print(ans)

Второе решение:

with open(«4.txt», «r») as f:

    n = int(f.readline())

    ans = 0

    cur = [1, 1]

    x = list(map(int, f.readline().split()))

    y = x.copy()

    for i in range(n — 1):

        last = cur.copy()

        cur = [1, 1]

        y = x.copy()

        x = list(map(int, f.readline().split()))

        for k in range(2):

            for j in range(2):

                if x[k] == y[1 — j] or x[k] == 0 or y[1 — j] == 0:

                    cur[k] = max(last[j] + 1, cur[k])

        ans = max(ans, cur[0], cur[1])

print(ans)

Ответ: 9