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

27.06 Доминошки

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

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

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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!