Доминошки —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#45911

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

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

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

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

Вложения к задаче

3.txt

Показать ответ и решение

Решение 1 (Excel):

Скопируем все числа из файла и перенесем их в Excel с помощью специальной вставки. Для этого в левом верхнем углу в разделе Главное нажмем вставить, выберем Использовать мастер импорта текста, в новом окне выберем с разделителем $→$ пробел $→$ Готово.

Удалим первое число, отвечающее за количество доминошек, и для удобства назовем столбы в соответствии с их назначениями.

Вставим пустую строку между первой и второй строками. Для этого нажмём правой кнопкой мыши на цифру, отвечающую за вторую строку, и нажмем Вставить

Заполним строки $1$ и $0$ так, как показано на изображении. Это необходимо для того, чтобы мы не заполнили эти ячейки формулами, ведь в таком случае Excel будет выдавать ошибку, так как формулы будут ссылаться не на числовые значения, а на текст.

Напишем формулу в ячейку $C4$ =МАКС(ЕСЛИ(A4=B3;C3+1;1);ЕСЛИ(A4=A3;D3+1;1);ЕСЛИ(A4=0;МАКС(C3:D3)+1;1)), скопируем её на весь столбец $C$

Напишем формулу в ячейку $D4$ =МАКС(ЕСЛИ(B4=B3;C3+1;1);ЕСЛИ(B4=A3;D3+1;1);ЕСЛИ(B4=0;МАКС(C3:D3)+1;1)), скопируем её на весь столбец $D$

Находим максимум из столбцов $C$ и $D$ с помощью формулы =МАКС(C3:D100002). Полученное значение запишем в ответ.

Решение 2 (прога):

f = open(’3.txt’)
n = int(f.readline())

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

ans = 1
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)

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 2#45910

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

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

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

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

Вложения к задаче

2.txt

Показать ответ и решение

Решение 1 (Excel):

Скопируем все числа из файла и перенесем их в Excel с помощью специальной вставки. Для этого в левом верхнем углу в разделе Главное нажмем вставить, выберем Использовать мастер импорта текста, в новом окне выберем с разделителем $→$ пробел $→$ Готово.

Удалим первое число, отвечающее за количество доминошек, и для удобства назовем столбы в соответствии с их назначениями.

Вставим пустую строку между первой и второй строками. Для этого нажмём правой кнопкой мыши на цифру, отвечающую за вторую строку, и нажмем Вставить

Заполним строки $1$ и $0$ так, как показано на изображении. Это необходимо для того, чтобы мы не заполнили эти ячейки формулами, ведь в таком случае Excel будет выдавать ошибку, так как формулы будут ссылаться не на числовые значения, а на текст.

Напишем формулу в ячейку $C4$ =МАКС(ЕСЛИ(A4=B3;C3+1;1);ЕСЛИ(A4=A3;D3+1;1)), скопируем её на весь столбец $C$

Напишем формулу в ячейку $D4$ =МАКС(ЕСЛИ(B4=B3;C3+1;1);ЕСЛИ(B4=A3;D3+1;1)), скопируем её на весь столбец $D$

Находим максимум из столбцов $C$ и $D$ с помощью формулы =МАКС(C3:D100002). Полученное значение запишем в ответ.

Решение 2 (прога):

file = open(’1.txt’)

n = int(file.readline())
current_dom = [int(s) for s in file.readline().split()]
prev_dom = current_dom.copy()

current_len = 1
current_len_reversed = 1
answer = 1

for i in range(1, n):
    current_dom = [int(s) for s in file.readline().split()]

    old_current_len = current_len
    old_current_len_reversed = current_len_reversed
    current_len, current_len_reversed = 1, 1

    # Если начало текщей совпадает с концом предыдущей
    if (current_dom[0] == prev_dom[1]):
        current_len = old_current_len + 1
    # Если начало текущей совпадает с началом предыдущей
    if (current_dom[0] == prev_dom[0]):
        current_len = old_current_len_reversed + 1
    # Если конец текущей совпадает с концом предыдущей
    if (current_dom[1] == prev_dom[1]):
        current_len_reversed = old_current_len + 1
    # Если конец текущей совпадает с началом предыдущей
    if (current_dom[1] == prev_dom[0]):
        current_len_reversed = old_current_len_reversed + 1
    if current_len > answer:
        answer = current_len
    if current_len_reversed > answer:
        answer = current_len_reversed

    prev_dom = current_dom.copy()

print(answer)

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 3#45909

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

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

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

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

Вложения к задаче

1.txt

Показать ответ и решение

Решение 1 (Excel):

Скопируем все числа из файла и перенесем их в Excel с помощью специальной вставки. Для этого в левом верхнем углу в разделе Главное нажмем вставить, выберем Использовать мастер импорта текста, в новом окне выберем с разделителем $→$ пробел $→$ Готово.

Удалим первое число, отвечающее за количество доминошек, и для удобства назовем столбы в соответствии с их назначениями.

Вставим пустую строку между первой и второй строками. Для этого нажмём правой кнопкой мыши на цифру, отвечающую за вторую строку, и нажмем Вставить

Заполним строки $1$ и $0$ так, как показано на изображении. Это необходимо для того, чтобы мы не заполнили эти ячейки формулами, ведь в таком случае Excel будет выдавать ошибку, так как формулы будут ссылаться не на числовые значения, а на текст.

Напишем формулу в ячейку $C4$ =МАКС(ЕСЛИ(A4=B3;C3+1;1);ЕСЛИ(A4=A3;D3+1;1)), скопируем её на весь столбец $C$

Напишем формулу в ячейку $D4$ =МАКС(ЕСЛИ(B4=B3;C3+1;1);ЕСЛИ(B4=A3;D3+1;1)), скопируем её на весь столбец $D$

В ячейку $E4$ запишем формулу =МАКС(C4:D4), скопируем её на весь столбец $D$

Находим максимум из столбца $E$ с помощью формулы =МАКС(E2:E100002). Полученное значение запишем в ответ.

Решение 2 (прога):

file = open(’1.txt’)


n = int(file.readline())
current_dom = [int(s) for s in file.readline().split()]
prev_dom = current_dom.copy()

current_len = 1
current_len_reversed = 1
answer = 1

for i in range(1, n):
    current_dom = [int(s) for s in file.readline().split()]

    old_current_len = current_len
    old_current_len_reversed = current_len_reversed
    current_len, current_len_reversed = 1, 1

    # Если начало текщей совпадает с концом предыдущей
    if (current_dom[0] == prev_dom[1]):
        current_len = old_current_len + 1
    # Если начало текущей совпадает с началом предыдущей
    if (current_dom[0] == prev_dom[0]):
        current_len = old_current_len_reversed + 1
    # Если конец текущей совпадает с концом предыдущей
    if (current_dom[1] == prev_dom[1]):
        current_len_reversed = old_current_len + 1
    # Если конец текущей совпадает с началом предыдущей
    if (current_dom[1] == prev_dom[0]):
        current_len_reversed = old_current_len_reversed + 1
    if current_len > answer:
        answer = current_len
    if current_len_reversed > answer:
        answer = current_len_reversed

    prev_dom = current_dom.copy()

print(answer)

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 4#40309

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

Определите максимальную длину цепочки костяшек домино, которую можно получить. Под цепочкой понимается последовательность костяшек, в которой второе число первой костяшки равно первому числу второй.

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

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

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

Вложения к задаче

D1.txt

Показать ответ и решение

file = open("D1.txt", "r")
n = int(file.readline())
current_dom = [int(s) for s in file.readline().split()]
prev_dom = current_dom.copy()

current_len = 1
answer = 1

for i in range(1, n):
    current_dom = [int(s) for s in file.readline().split()]

    old_current_len = current_len
    current_len = 1

    # Если начало текущей совпадает с концом предыдущей
    if (current_dom[0] == prev_dom[1]):
        current_len = old_current_len + 1

    if current_len > answer:
        answer = current_len

    prev_dom = current_dom.copy()

file.close()
print(answer)

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 5#30024

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

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

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

Вложения к задаче

5_domino.txt

Показать ответ и решение

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

Ошибка.
Попробуйте повторить позже

Задача 6#30023

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

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

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

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

Вложения к задаче

4_domino.txt

Показать ответ и решение

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

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

Ошибка.
Попробуйте повторить позже

Задача 7#30022

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

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

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

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

Вложения к задаче

3_domino.txt

Показать ответ и решение

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

f = open(’3.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] and x[0] != 0:
        cur = max(cur, last + 1)
    if x[0] == y[0] and x[0] != 0:
        cur = max(cur, last_p + 1)
    if x[1] == y[1] and x[1] != 0:
        cur_p = max(cur_p, last + 1)
    if x[1] == y[0] and x[1] != 0:
        cur_p = max(cur_p, last_p + 1)

    ans = max(ans, cur, cur_p)

f.close()
print(ans)

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

with open("3.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] and x[k] != 0:
                    cur[k] = max(last[j] + 1, cur[k])

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

print(ans)

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 8#30021

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

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

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

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

Вложения к задаче

domino_3.txt

Показать ответ и решение

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

f = open(’domino_3.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()

print(ans)

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

f = open(’domino_3.txt’)
p = [[1, 1, 1]]
r = []
ans = 1
n = int(f.readline())
for i in range(n):
    x, y, z = map(int, f.readline().split())
    r.append([x, y, z])
for i in range(1, n):
    p.append([1, 1, 1])
    for t in range(3):
        for j in range(3):
            if r[i][t] == r[i - 1][j]:
                for w in range(3):
                    if w != j:
                        p[i][t] = max(p[i][t], p[i - 1][w] + 1)
    ans = max(ans, max(p[i]))
print(ans)

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 9#30020

Дано натуральное число n, затем последовательность из $n$ целых чисел. Из нее необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было больше предыдущего. Какую максимальную сумму может иметь подпоследовательность из выбранных чисел?

Пример входных данных:

$|--| -1-- |2 | |--| |6-| -4-- |7 | |--| -9--$

Для указанных входных данных ответом должно быть число $20$ – максимальная сумма элементов возрастающей последовательности. В ответе укажите только целую часть числа.

Вложения к задаче

1_domino.txt

Показать ответ и решение

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    sum = a[i]
    for j in range(i + 1, n):
        if a[j] > a[j - 1]:
            sum += a[j]
        else:
            break
    ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

f = open("27B.txt")
n = int(f.readline())
ans = 0
last = -1000000000
summa = 0

for i in range(n):
    cur = int(f.readline())
    if cur > last:
        summa += cur
        if summa > ans:
            ans = summa
    else:
        summa = cur
    last = cur

f.close()
print(ans)

Ответ: 22

Ошибка.
Попробуйте повторить позже

Задача 10#23073

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

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

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

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

Вложения к задаче

5__k8r4.txt

Показать ответ и решение

f = open(’5.txt’)
n = int(f.readline())

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

ans = 1
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

Ошибка.
Попробуйте повторить позже

Задача 11#23072

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

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

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

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

Вложения к задаче

4__k8r1.txt

Показать ответ и решение

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

f = open(’4.txt’)
n = int(f.readline())

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

ans = 1
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

Ошибка.
Попробуйте повторить позже

Задача 12#23071

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

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

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

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

Вложения к задаче

3__k8r0.txt

Показать ответ и решение

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

f = open(’3.txt’)
n = int(f.readline())

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

ans = 1
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] and x[0] != 0:
        cur = max(cur, last + 1)
    if x[0] == y[0] and x[0] != 0:
        cur = max(cur, last_p + 1)
    if x[1] == y[1] and x[1] != 0:
        cur_p = max(cur_p, last + 1)
    if x[1] == y[0] and x[1] != 0:
        cur_p = max(cur_p, last_p + 1)

    ans = max(ans, cur, cur_p)

f.close()
print(ans)

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

with open("3.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] and x[k] != 0:
                    cur[k] = max(last[j] + 1, cur[k])

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

print(ans)

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 13#23070

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

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

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

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

Вложения к задаче

2__k8r5.txt

Показать ответ и решение

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

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

Ошибка.
Попробуйте повторить позже

Задача 14#18537

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

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

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

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

Вложения к задаче

domino.txt

Показать ответ и решение

file = open("domino.txt", "r")
n = int(file.readline())
current_dom = [int(s) for s in file.readline().split()]
prev_dom = current_dom.copy()

current_len = 1
current_len_reversed = 1
answer = 1

for i in range(1, n):
    current_dom = [int(s) for s in file.readline().split()]

    old_current_len = current_len
    old_current_len_reversed = current_len_reversed
    current_len, current_len_reversed = 1, 1

    # Если начало текщей не совпадает с концом предыдущей
    if (current_dom[0] != prev_dom[1]):
        current_len = old_current_len + 1
    # Если начало текущей не совпадает с началом предыдущей
    if (current_dom[0] != prev_dom[0]):
        current_len = max(current_len, old_current_len_reversed + 1)
    # Если конец текущей не совпадает с концом предыдущей
    if (current_dom[1] != prev_dom[1]):
        current_len_reversed = old_current_len + 1
    # Если конец текущей не совпадает с началом предыдущей
    if (current_dom[1] != prev_dom[0]):
        current_len_reversed = max(current_len_reversed, old_current_len_reversed + 1)
    if current_len > answer:
        answer = current_len
    if current_len_reversed > answer:
        answer = current_len_reversed

    prev_dom = current_dom.copy()

file.close()
print(answer)

Ответ: 82154