Февральский кубок Санкт-Петербургской олимпиады по программированию 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,

Пример кода на языке 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])