Тема 27. Программирование – оптимизация по времени и по памяти

27.06 Доминошки

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование – оптимизация по времени и по памяти
Решаем задачи

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

Задача 1#18537

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

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

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

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

Вложения к задаче
Показать ответ и решение
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

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

Задача 2#23070

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

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

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

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

PIC

Вложения к задаче
Показать ответ и решение

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

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

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

Задача 3#23071

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

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

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

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

Вложения к задаче
Показать ответ и решение

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

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

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

Задача 4#23072

На столе выложили цепочку из 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 = 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

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

Задача 5#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  .

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

Вложения к задаче
Показать ответ и решение
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

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

Задача 6#30021

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

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

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

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

PIC

Вложения к задаче
Показать ответ и решение

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

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

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

Задача 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  .

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

Вложения к задаче
Показать ответ и решение

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

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#30023

На столе выложили цепочку из 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

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

Задача 9#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  .

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

Вложения к задаче
Показать ответ и решение
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

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

Задача 10#40309

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

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

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

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

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

Вложения к задаче
Показать ответ и решение
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

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

Задача 11#45909

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

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

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

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

Вложения к задаче
Показать ответ и решение

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

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

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

Находим максимум из столбца 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

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

Задача 12#45910

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

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

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

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

Вложения к задаче
Показать ответ и решение

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

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

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

Решение 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

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

Задача 13#45911

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

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

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

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

Вложения к задаче
Показать ответ и решение

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

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

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

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

PIC

Решение 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
Рулетка
Вы можете получить скидку в рулетке!