Всем привет!

Записал занятие про двоичный поиск.

Огромное спасибо Stepavly и Supermagzzz за помощь с конспектом и задачами.

В нашем курсе уже пять занятий (и скоро будет больше!):

• двоичный поиск,
• дерево отрезков, часть 1,
• дерево отрезков, часть 2,
• z-функция,
• суффиксный массив.

Подробнее об учебном подразделе на Codeforces (и его β-тестировании) можно прочитать по ссылке.

Как обычно, приветствуем ваши комментарии. Пишите, чего не хватает и что можно было бы сделать лучше. Фидбек очень важен.

Приятного прохождения занятия и удачи на контестах!

Закончились лекции весеннего семестра моего курса "Алгоритмы и структуры данных" в ИТМО.

На лекциях первого курса были деревья отрезков, деревья поиска и структуры на деревьях (двоичные подъемы, Heavy-Light декомпозиция, центроиды, и т. д.)

На лекциях второго курса были паросочетания, потоки, немножко теории чисел и FFT.

Может быть, кому-то поможет на контестах :)

Также на канале есть записи стримов, которые я иногда провожу на твиче. На них я решаю простые задачи, в основном с AtCoder Beginner Contest.

Привет!

Лучше поздно, чем никогда! Наконец записал вторую часть занятия про дерево отрезков.

На второй части мы разберем, как делать массовые операции на дереве отрезков.

Огромное спасибо Stepavly и Supermagzzz за помощь с конспектом.

Таким образом в нашем курсе уже четыре занятия:

• дерево отрезков, часть 1,
• дерево отрезков, часть 2,
• z-функция,
• суффиксный массив.

Подробнее об учебном подразделе на Codeforces (и его β-тестировании) можно прочитать по ссылке.

Как обычно, приветствуем ваши комментарии. Пишите, чего не хватает и что можно было бы сделать лучше. Фидбек очень важен.

Приятного прохождения занятия и удачи на контестах!

Апрельский кубок Санкт-Петербургской олимпиады по программированию 2020 прошел вместо очной олимпиады Санкт-Петербурга для 3-7 классов (но мы планируем все-таки провести ее, когда карантин закончится!)

Социальная дистанция (первая лига A)

Если $$$d\ge x$$$, то условие уже соблюдается, поэтому ответ 0, иначе ответ равен $$$x-d$$$.

Пример кода на языке Python:

d = int(input())
x = int(input())
if d >= x:
  print(0)
else:
  print(x - d)

Три оценки (первая лига B)

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

Если $$$n\le 11$$$, то можно сделать первую оценку равной 1, а остаток распределить между второй и третьей оценкой, только надо делать это аккуратно, чтобы обе оценки были от 1 до 5. Один из способов это сделать — разделить на две примерно равные части, как сделано в приведенном ниже коде.

Если $$$n\ge 11$$$, то можно последние две оценки сделать равными 5, а остаток сделать первой оценкой.

Пример кода на языке Python:

n = int(input())
if n <= 11:
    print(1, (n - 1) // 2, n // 2)
else:
    print(n - 10, 5, 5)

Делим конфетки (первая лига C, высшая лига A)

Для того, чтобы распределить конфеты между $$$n$$$ участниками так, чтобы они получили различное число конфет, нужно как минимум $$$s=1+2+\ldots+n$$$ конфет. Эту сумму можно посчитать либо циклом, либо по формуле суммы арифметической прогрессии, как в коде ниже. Если у нас конфет меньше, чем $$$s$$$, то распределить не получится. Если же больше, чем $$$s$$$, то можно лишние конфеты отдать участнику на первом месте, и после этого все еще все будут получать различное число. Таким образом, нам нужно просто проверить, что $$$m\ge s$$$.

Пример кода на языке Python:

n = int(input())
m = int(input())
s = n * (n + 1) // 2
if m >= s:
    print("Yes")
else:
    print("No")

Игрушечная машинка (первая лига D, высшая лига B)

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

Пример кода на языке Python:

n = int(input())
s = input()
v = 0
l = 0
for c in s:
    if c == '+':
        v += 1
    elif v > 0:
        v -= 1
    l += v
print(l)

Пилообразная последовательность (первая лига E, высшая лига C)

Задача получилась неожиданно сложной. Решение этой задачи — это жадный алгоритм. Посмотрим на первые два числа. Если для них условие $$$a_1 < a_2$$$ не выполняется, то для того, чтобы оно стало выполняться, нужно либо уменьшить первое число, либо увеличить второе. Оба действия приближают нас к результату одинаково, но второе (увеличение второго числа) так же приближает нас к соблюдению следующего условия ($$$a_2 > a_3$$$), если оно еще не выполнено, поэтому будем увеличивать второе число, а не уменьшать первое. Далее продолжим по той же схеме добиваться того, чтобы выполнялось второе условие, и т. д.

В приведенном ниже коде в переменной $$$x$$$ мы вычисляем значение, до которого нужно увеличить или уменьшить элемент $$$a_i$$$, чтобы выполнялось условие для $$$a_{i-1}$$$ и $$$a_i$$$. Далее прибавляем к ответу число действий, которое нужно сделать, чтобы $$$a_i$$$ стало равным $$$x$$$, и затем заменяем $$$a_i$$$ на $$$x$$$.

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]
s = 0
for i in range(1, n):
    if i % 2 == 1:
        x = max(a[i], a[i - 1] + 1)
    else:
        x = min(a[i], a[i - 1] - 1)
    s += abs(a[i] - x)
    a[i] = x
print(s)

Коллекционирование карт (первая лига F, высшая лига D)

Для начала переведем все времена в числа (число секунд от полуночи). Далее перебираем все времена и храним последний момент, когда мы получили новую карту. Если очередной момент времени отличается от него как минимум на $$$x$$$, то мы получаем новую карту: увеличиваем счетчик и запоминаем новое время.

Пример кода на языке Python:

n, x = map(int, input().split())
a = []
for i in range(n):
    s = input()
    a.append(int(s[0:2]) * 60 * 60 + int(s[3:5]) * 60 + int(s[6:8]))

res = 1
t = a[0]
for i in range(n):
    if a[i] >= t + x:
        t = a[i]
        res += 1

print(res)

Кролики (первая лига G, высшая лига E)

Если немного поиграть и посмотреть, как могут двигаться кролики, то становится понятно, что кролики двигаются парами. Действительно, посмотрим на два самых правых кролика. Пусть это кролики A и B. Тогда сначала единственное действие, которое можно сделать — это A перепрыгивает через B. После этого A находится правее B, и единственное действие, которое может сделать кролик B — перепрыгнуть через A, и т. д. Таким образом, если кроликов нечетное число, то решения нет, потому что у самого левого кролика не будет пары. Иначе Разбиваем кроликов на пары и двигаем их вправо одну за другой.

Пример кода на языке Python:

n, k = map(int, input().split())
if k % 2 == 1:
    print(-1)
    exit()

print((n - k) * k // 2)
for i in range(k // 2):
	for j in range(n - k):
        print(k + j - i * 2 - 1, end=" ")

Падающие буквы (первая лига H, высшая лига F)

Есть много способов решать эту задачу, например такой. Будем двигаться по каждому столбцу $$$j$$$ снизу вверх, при этом будем хранить в переменной $$$k$$$ номер клетки, на которую должна упасть очередная буква. Изначально $$$k=n-1$$$ (нумерация с 0). Если видим букву, то перемещаем ее на клетку $$$k$$$ и уменьшаем $$$k$$$ на единицу. Проделываем такую операцию с каждым столбцом по отдельности, в результате получим нужную таблицу.

Пример кода на языке Python:

n, m = map(int, input().split())
a = [list(input()) for x in range(n)]
for j in range(m):
    k = n - 1
    for i in range(n - 1, -1, -1):
        if a[i][j] != '.':
            a[k][j], a[i][j] = a[i][j], a[k][j]
            k -= 1
for i in range(n):
    print("".join(a[i]))

Прыжки (высшая лига G)

В этой задаче нужна небольшая математическая интуиция.

Давайте сначала поймем, для каких $$$k$$$ точно не получится допрыгать до точки $$$x$$$. Пусть $$$s=1+2+\ldots+k$$$. Если $$$s<x$$$, то допрыгать не получится, потому что суммарной дальности прыжков не достаточно. Во вторых, если четности $$$s$$$ и $$$x$$$ не совпадают, то мы также не сможем допрыгать, потому что на каждом прыжке четность меняется одинаково, вне зависимости от того, прыгаем мы влево или вправо.

Давайте найдем минимальное $$$k$$$, для которого не выполняется ни одно из этих ограничений. Покажем, что для этого $$$k$$$ существует способ допрыгать до $$$x$$$. Действительно, сделаем сначала все прыжки вправо, попадем в точку $$$s$$$. Теперь посмотрим на разность $$$d = s-x$$$, она должна быть четным числом. Сделаем прыжок на $$$d/2$$$ не вправо, а влево, тогда общее перемещение уменьшится как раз на $$$d$$$, и мы попадем в точку $$$x$$$ (на самом деле, нужно еще показать, что $$$d/2 \le k$$$, но это оставлю вам в качестве упражнения).

UPD: BlackBear справедливо отметил, что в предыдущем абзаце написана неправда, может быть такое, что $$$d/2 > k$$$. В этом случае нужно развернуть несколько прыжков, в сумме составляющих $$$d/2$$$.

Более простой способ решения такой: найдем минимальное подходящее $$$k$$$, дальше будем двигаться с конца, от точки $$$x$$$, делая прыжки на $$$k, k-1, \ldots 1$$$, при этом каждый раз будем делать прыжок в сторону 0 (то есть, если стоим в положительной точке, двигаемся влево, а если в отрицательной, то вправо). Можно показать, что если выполняются оба условия на $$$k$$$, описанные выше, то этот процесс приведет нас в конце в точку 0. После этого осталось развернуть массив точек, которые мы посетили, и получим ответ.

Пример кода на языке Python:

x = int(input())
s = 1
k = 1
while s < x or s % 2 != x % 2:
    k += 1
    s += k

p = [x]
for i in range(k, 1, -1):
    if p[-1] > 0:
        p.append(p[-1] - i)
    else:
        p.append(p[-1] + i)
p = p[::-1]
print(len(p))
print(*p)

Развороты скобок (высшая лига H)

Это была действительно сложная задача, в ней требовалось не только разобраться, как работает предложенная модель, и придумать алгоритм, но и написать достаточно много кода.

Для начала скажем, что ограничение на пять операций было избыточным, наше решение всегда будет делать не более трех операций (есть решение, которое делает не более двух операций, попробуйте его придумать сами).

Чтобы было проще понять решение, давайте представлять скобочную последовательность в виде ломаной, которая начинается в точке 0, идет вверх, когда скобка открывается, и вниз, когда закрывается. Например, для скобочной последовательности (()())() получим такую ломаную:

Скобочная последовательность будет правильной, если выполняется два условия: во-первых, ломаная должна заканчиваться на уровне 0 (то есть все открытые скобки закрылись), а во-вторых, ломаная не может уходить ниже 0 (это бы означало, что закрывается скобка, которая еще не была открыта до этого)

Теперь посмотрим, что же делает операция разворота отрезка. Она берет кусок ломаной и зеркально отражает его:

Давайте попробуем такими операциями сделать так, чтобы соблюдались оба условия. Сначала сделаем, чтобы соблюдалось первое. Для этого посмотрим, на какой высоте заканчивается ломаная, пусть это число $$$b$$$. Найдем такое начало ломаной, на котором высота ломаной равна $$$b/2$$$, и развернем это начало. После этого конец ломаной переместится в точку 0.

Теперь сделаем так, чтобы соблюдалось второе условие. Для этого найдем самую низкую вершину ломаной, и развернем куски ломаной до нее и после нее. После этого оба условия будут соблюдаться, и мы получим правильную скобочную последовательность.

Пример кода на языке Python:

s = list(input())
n = len(s)
res = []


def reverse(l, r):
    ss = s[l:r]
    ss.reverse()
    s[l:r] = ss
    for i in range(l, r):
        if s[i] == '(':
            s[i] = ')'
        else:
            s[i] = '('
    res.append("".join(s))


b = 0
for i in range(n):
    if s[i] == '(':
        b += 1
    else:
        b -= 1

if b != 0:
    c = 0
    for i in range(n):
        if s[i] == '(':
            c += 1
        else:
            c -= 1
        if c == b // 2:
            reverse(0, i + 1)
            break

b = 0
minb = 0
mini = 0
for i in range(n):
    if b < minb:
        minb = b
        mini = i
    if s[i] == '(':
        b += 1
    else:
        b -= 1

if minb < 0:
    reverse(0, mini)
    reverse(mini, n)

print(len(res))
for x in res:
    print(x)

Привет!

Несмотря на карантин (а, может, и благодаря ему) я записал еще одно занятие для раздела EDU. На этот раз мы поговорим про дерево отрезков. Это довольно богатая тема, поэтому я решил разбить ее на несколько занятий, и это первое из них.

В этом занятии мы разберем, как устроено простое дерево отрезков (без массовых операций), и как выполнять на нем основные операции. Также разберем несколько примеров его использования в различных задачах.

Большое спасибо Aksenov239 за помощь с конспектом.

Таким образом в нашем курсе сейчас три занятия:

• дерево отрезков, часть 1,
• z-функция,
• суффиксный массив.

Подробнее об учебном подразделе на Codeforces (и его β-тестировании) можно прочитать по ссылке.

Как обычно, приветствуем ваши комментарии. Пишите, чего не хватает и что можно было бы сделать лучше. Фидбек очень важен.

Приятного прохождения занятия и удачи на контестах!

Февральский кубок Санкт-Петербургской олимпиады по программированию 2020 получился немного проще, чем декабрьский, но задачи, как мне кажется, были не менее интересные.

Три города (первая лига A)

Есть два принципиальных варианта маршрута: сделать круг из трех перелетов, заплатив $$$a+b+c$$$, либо выбрать два самых дешевых перелета, и пролететь их в обе стороны.

Пример кода на языке Python:

a = int(input())
b = int(input())
c = int(input())
print(min(a + b + c, 2 * a + 2 * c, 2 * a + 2 * b, 2 * b + 2 * c))

Плохой пин-код (первая лига B)

Просто проверим три пары соседних символов. Если хотя бы одна из пар совпадает, то код плохой.

Пример кода на языке Python:

a = input()
if a[0] == a[1] or a[1] == a[2] or a[2] == a[3]:
    print('bad')
else:
    print('good')

Результат проверки (первая лига C, высшая лига A)

Пройдемся по всем результатам, найдем первый, который не равен AC. Выведем его и номер теста. Если не найдем, выводим AC.

Пример кода на языке Python:

n = int(input())
a = input().split()
for i in range(n):
    if a[i] != "AC":
        print(a[i], i + 1)
        break
else:
    print("AC")

Лучший круг (первая лига D, высшая лига B)

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

Пример кода на языке Python:

n = int(input())
a = []
for i in range(n + 1):
    s = input()
    a.append(int(s[0:2]) * 60 * 60 + int(s[3:5]) * 60 + int(s[6:8]))

d = [a[i + 1] - a[i] for i in range(n)]
print(min(d))

Уборка букв (первая лига E, высшая лига C)

Есть много способов решить эту задачу. Например, можно перебрать все буквы от a до z, посчитать, сколько раз буква входит в строку, и если это число больше 0, вывести соответствующую группу.

Пример кода на языке Python:

s = input()
for i in range(26):
    c = chr(ord('a') + i)
    x = s.count(c)
    if x > 0:
        print('(' + c * x + ')', end="")

Одинаковые пары (первая лига F, высшая лига D)

Отсортируем стопки по возрастанию. Теперь очевидно, что нужно брать в пары соседние стопки в отсортированном порядке. Разобьем стопки на пары и посчитаем для каждой разность высот. Сложим, получим ответ.

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
res = 0
for i in range(0, n, 2):
    res += a[i + 1] - a[i]
print(res)

Игра с шариками (первая лига G, высшая лига E)

Пусть i — текущая позиция белого шарика. Изначально i = 0. Далее каждый раз проверяем, можно ли сдвинуть его на 1 или 2 позиции вправо. Если можно, двигаем. В конце собираем строку с ответом.

Пример кода на языке Python:

a = list(input())
i = 0
while True:
    if i + 1 < len(a) and a[i + 1] == '-':
        a[i], a[i + 1] = '-', 'W'
        i += 1
    elif i + 2 < len(a) and a[i + 2] == '-':
        a[i], a[i + 2] = '-', 'W'
        i += 2
    else:
        break
print(''.join(a))

Солнечные дни (первая лига H, высшая лига F)

Есть очень много способов решать эту задачу. Общая идея такая: $$$k$$$ пасмурных дней разбивают весь отпуск на $$$k+1$$$ отрезок. Чтобы минимизировать самый длинный отрезок, нужно сделать их примерно одинаковыми. То есть нужно разбить все $$$n-k$$$ солнечных дней на $$$k+1$$$ группу примерно одинакового размера. В приведенной ниже реализации мы просто заводим $$$k+1$$$ строку, и раскладываем $$$n-k$$$ букв S по очереди в каждую из строк. В результате длина этих строк будет отличаться не более, чем на 1.

Пример кода на языке Python:

n = int(input())
k = int(input())
a = [""] * (k + 1)
for i in range(n - k):
    a[i % (k + 1)] += 'S'
print('R'.join(a))

Равный дележ (высшая лига G)

В этой задаче также много правильных решений. Например можно делать так: найдем пирата, у которого сумма больше чем надо. Если такой есть, то есть и другой пират, у которого меньше, чем надо. Передадим излишек от первого пирата второму. Тогда у первого станет ровно столько, сколько нужно, и он больше не будет участвовать в обменах. Продолжаем так делать пока есть хотя бы один пират с излишком.

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]

s = sum(a) // n

res = []
while True:
    i = 0
    while i < n and a[i] <= s:
        i += 1
    if i == n:
        break
    j = 0
    while j < n and a[j] >= s:
        j += 1
    d = a[i] - s
    res.append((i, j, d))
    a[i] -= d
    a[j] += d

print(len(res))
for p in res:
    print(p[0] + 1, p[1] + 1, p[2])

Наибольший прямоугольник (высшая лига H)

Нужно найти две пары одинаковых отрезков, причем из всех таких пар выбрать две самые большие. Самый простой способ это сделать — отсортировать отрезки, тогда одинаковые будут рядом. Разобьем их на пары жадно. В конце посмотрим на две самые большие пары, которые у нас получились. Если пар меньше 2, выведем -1.

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
p = []
i = 0
while i < n - 1:
    if a[i] != a[i + 1]:
        i += 1
    else:
        p.append(a[i])
        i += 2

if len(p) < 2:
    print(-1)
else:
    print(p[-2] * p[-1])

В этом семестре записал на видео все лекции курса "Алгоритмы и структуры данных", который я читаю в ИТМО. Лекции стримились в прямом эфире на твич и потом выкладывались на ютуб.

Курс скорее академический, а не олимпиадный, но думаю многим начинающим (и не только) олимпиадникам тоже будет интересно. Например, эти лекции:

ДП по профилю

Алгоритм Ахо-Корасик

Лекции первого курса: https://www.youtube.com/watch?v=apR9GhhjBjM&list=PLrS21S1jm43geDXVdeQy96P-f59pXeyPC

Лекции второго курса: https://www.youtube.com/watch?v=80icIrhJ6G0&list=PLrS21S1jm43iF3DKP3rvpN8hoTBqHVYbr

Надеюсь кому-то будет полезно. Удачи на контестах!

Задача A. Отпуск

Если $$$x+y < n$$$, то было $$$n-x-y$$$ дней без шторма и холодов, если же $$$x+y\ge n$$$, значит не было ни одного такого дня.

Пример кода на языке Python:

n = int(input())
x = int(input())
y = int(input())
if x + y < n:
    print(n - x - y)
else:
    print(0)

Задача B. Простая игра

Минимальное число ходов будет, если все время будет выпадать 6. В этом случае число ходов будет равно $$$n / 6$$$, округленное вверх до ближайшего целого. В большинстве языков по умолчанию делается с округлением вниз, чтобы сделать округление вверх, проще всего использовать формулу $$$(n + 5) / 6$$$, при этом деление делается с округлением вниз. Максимальное число ходов будет очевидно равно $$$n$$$.

Пример кода на языке Python:

n = int(input())
print((n + 5) // 6, n);

Задача C. Алфавит

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

Пример кода на языке Python:

s = input()
a = "abcdefghijklmnopqrstuvwxyz"
res = 0
for i in range(len(s)):
    if s[i] == a[i]:
        res += 1
    else:
        break
print(res)

Задача D. Верные утверждения

Эта задача вызвала, к сожалению, больше вопросов у участников, чем предполагало жюри олимпиады. Давайте разбираться, что в ней происходит. Есть $$$n$$$ утверждений вида "Ровно $$$a_i$$$ из этих утверждений верны". Нужно найти максимальное число верных утверждений, которое может быть среди них. Пусть среди них ровно $$$k$$$ верных утверждений, тогда все утверждения, для которых $$$a_i = k$$$ верны, а остальные нет. Такое может быть, если утверждений, для которых $$$a_i=k$$$ ровно $$$k$$$. Посчитаем для каждого $$$k$$$, сколько всего утверждений, в которых $$$a_i = k$$$, после чего переберем подходящие $$$k$$$ и выберем максимальное.

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

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]
c = [0] * (n + 1)
for x in a:
    c[x] += 1
 
res = -1
for k in range(n + 1):
    if c[k] == k:
        res = k
        
print(res)

Задача E. Овечка

Для начала найдем позицию, в которой находится овечка. Затем будем двигаться от нее влево и вправо, пока не встретим камень или конец поля. Получим левую и правую границы отрезка, на котором может пастись овечка. Тогда ответом будет $$$r-l+1$$$.

Пример кода на языке Python:

s = input()
i = s.find("@")
l = i - 1
while l >= 0 and s[l] == '.':
    l -= 1
r = i + 1
while r < len(s) and s[r] == '.':
    r += 1

print(r - l - 1)

Задача F. Сортировка сыра

Есть много способов решать эту задачу. Самый простой и эффективный способ такой. Пойдем справа налево. Последний столбик уменьшать смысла нет, так как он должен быть самым высоким. Посмотрим на предпоследний столбик. Если он меньше, чем последний, то его опять же нет смысла уменьшать, а если выше — то его следует уменьшить до той же высоты. И так далее, каждый раз сравниваем столбик со следующим, если он выше, то уменьшаем его, чтобы они стали равны.

Пример кода на языке Python:

n = int(input())
a = [int(x) for x in input().split()]

res = 0
for i in range(n - 2, -1, -1):
    if a[i] > a[i + 1]:
        res += a[i] - a[i + 1]
        a[i] = a[i + 1]

print(res)

Задача G. Задачи для олимпиады

Довольно сложная задача. Можно решать ее, разбирая множество частных случаев, но так достаточно легко допустить ошибку. Чтобы упростить решение, можно зафиксировать один из параметров так, чтобы остальные вычислялись легко. Например, можно перебрать число туров, которые мы хотим провести. Если это число равно $$$x$$$, то как проверить, хватит ли у нас задач? Посмотрим на первую задачу. Это должна быть задача сложности 1 или 2. Понятно, что надо в первую очередь брать задачи сложности 1, потому что задачи сложности 2 можно использовать еще и на второй позиции. Тогда нам надо использовать $$$q=max(0, x - a[0])$$$ задач сложности 2. Теперь так же посмотрим, хватает ли нам задач на вторую позицию, при этом в первую очередь используем задачи сложности 2 и 3, а затем уже 4. В конце посмотрим, хватает ли нам задач сложности 4 и 5 на третью позицию.

Пример кода на языке Python:

a = [int(input()) for i in range(5)]
x = 0
while True:
    x += 1
    if a[0] + a[1] < x:  # хватает ли задач на позицию 1
        break
    q = max(0, x - a[0])
    if a[1] + a[2] + a[3] - q < x:  # хватает ли задач на позицию 2
        break
    w = max(0, x - a[1] - a[2] + q)
    if a[3] + a[4] - w < x:  # хватает ли задач на позицию 3
        break
print(x - 1)

Задача H. Покраска доминошек

Пойдем слева направо и будем считать, сколько есть вариантов покрасить каждую доминошку. Каждый раз к картинке будет добавляться либо одна вертикальная доминошка, либо две горизонтальных. Рассмотрим четыре случая:

• Случай 1: добавили вертикальную доминошку, и перед ней стояла тоже вертикальная. Тогда есть два способа покрасить новую доминошку.
• Случай 2: добавили вертикальную доминошку, и перед ней стояли две горизонтальные. Тогда есть только один способ покрасить новую доминошку.
• Случай 3: добавили две горизонтальные доминошки, и перед ними стояла вертикальная. Тогда есть два способа покрасить новые доминошки.
• Случай 4: добавили две горизонтальные доминошки, и перед ними стояли еще две горизонтальные. Тогда есть три способа покрасить новые доминошки.

Отдельно надо рассмотреть самые левые доминошки.

Пример кода на языке Python:

n = int(input())
s1 = input()
s2 = input()

i = 0
last = 0
res = 1
while i < n:
    if s1[i] == s2[i]:
        if last == 0:
            res *= 3  # первая вертикальная доминошка
        elif last == 1:
            res *= 2  # случай 1
        last = 1
        i += 1
    else:
        if last == 0:
            res *= 6  # первые горизонтальные доминошки
        elif last == 1:
            res *= 2  # случай 3
        else:
            res *= 3  # случай 4
        last = 2
        i += 2

print(res)