Предметный тур. Информатика. 3 этап

Пароль содержит 8 уникальных символов: N, T, O, F, I, 2, 0, 5. Для кодирования одного символа требуется: \[\log_2 8 = 3 \text{ бит}.\]

Для пароля длины \(l\): \[\text{Бит на пароль} = l \cdot 3.\]

1 байт = 8 бит. Чтобы найти целое число байт, округлим вверх: \[\text{Байт на пароль} = \left\lceil \frac{l \cdot 3}{8} \right\rceil.\] Эквивалентная формула для целочисленного деления: \[\text{Байт на пароль} = \frac{l \cdot 3 + 7}{8} \quad (\text{целочисленное деление}).\]

Умножим байты на пароль на количество участников \(c\): \[\text{Итого байт} = \left( \left\lceil \frac{3l}{8} \right\rceil \right) \cdot c.\]

Пример программы-решения

Ниже представлено решение на языке Python.

l = int(input())
c = int(input())
print((l * 3 + 7) // 8 * c)

Для решения задачи разобьем ее на две части:

1. Найдем координаты \((x_{max}, y_{max})\) ячейки с максимальным значением.

2. Разделим путь на два отрезка:

   • от начальной точки \((15, 15)\) до \((x_{max}, y_{max})\);
   • от \((x_{max}, y_{max})\) до конечной точки \((1, 1)\).

Пример программы-решения

Ниже представлено решение на языке Python.

def solve(a, start, end):
    x1, y1 = start
    x2, y2 = end
    n = len(a)
    m = len(a[0]) if n else 0

    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[x1][y1] = a[x1][y1]

    for i in range(x1, x2 + 1):
        for j in range(y1, y2 + 1):
            if i == x1 and j == y1:
                continue 
            dp[i][j] = a[i][j] + max(dp[i-1][j] if i > x1 else 0, dp[i][j-1] if j > y1 else 0)

    return dp[x2][y2]

n, m = 15, 15
a = [list(map(int, input().split())) for _ in range(n)]

x, y = 0, 0
for i in range(n):
    for j in range(m):
        if a[x][y] < a[i][j]:
            x, y = i, j

print(solve(a, (0, 0), (x, y)) + solve(a, (x, y), (n - 1, m - 1)) - a[x][y])

Для каждого из этих отрезков применим динамическое программирование, аналогичное задаче о максимальном пути в матрице с движениями только вверх и влево.

1. Находим позицию максимального элемента \((x_{max}, y_{max})\).

2. Вычисляем максимальную сумму на пути от \((15, 15)\) до \((x_{max}, y_{max})\):

   • Создаем матрицу \(dp1\) размером \(15 \times 15\).
   • Инициализируем \(dp1[15][15] = a[15][15]\).
   • Заполняем матрицу по правилу: \[dp1[i][j] = a[i][j] + \max(dp1[i+1][j], dp1[i][j+1])\] (с проверкой границ матрицы).

3. Вычисляем максимальную сумму на пути от \((x_{max}, y_{max})\) до \((1, 1)\):

   • Создаем матрицу \(dp2\) размером \(15 \times 15\).
   • Инициализируем \(dp2[x_{max}][y_{max}] = a[x_{max}][y_{max}]\).
   • Заполняем матрицу по правилу: \[dp2[i][j] = a[i][j] + \max(dp2[i-1][j], dp2[i][j-1])\] (с проверкой границ матрицы).
4. Итоговый результат: \(dp1[x_{max}][y_{max}] + dp2[1][1] - a[x_{max}][y_{max}]\) (вычитаем значение максимальной ячейки, так как оно учтено дважды).

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

Пример программы-решения

Ниже представлено решение на языке Python.

def solve():
    # Чтение входных данных
    grid = []
    max_val = -1
    max_pos = (-1, -1)
    
    for i in range(15):
        row = list(map(int, input().split()))
        grid.append(row)
        for j in range(15):
            if row[j] > max_val:
                max_val = row[j]
                max_pos = (i, j)
    
    start = (14, 14)  # Нижний правый угол (индексы с 0)
    end = (0, 0)       # Верхний левый угол

    # Функция для генерации всех возможных сумм до целевой точки
    def generate_path_sums(start_pos, target_pos):
        dx = start_pos[0] - target_pos[0]  # Количество шагов вверх
        dy = start_pos[1] - target_pos[1]  # Количество шагов влево
        total_steps = dx + dy
        
        sums = {}
        
        # Перебор всех комбинаций шагов
        from itertools import combinations
        for up_indices in combinations(range(total_steps), dx):
            mask = 0
            for pos in up_indices:
                mask |= 1 << pos
            
            x, y = start_pos
            current_sum = grid[x][y]
            valid = True
            
            for i in range(total_steps):
                if mask & (1 << i):
                    x -= 1  # Вверх
                else:
                    y -= 1  # Влево
                
                if x < 0 or y < 0 or x > 14 or y > 14:
                    valid = False
                    break
                
                current_sum += grid[x][y]
                
                if (x, y) == target_pos:
                    break
            
            if valid and (x, y) == target_pos:
                sums[mask] = current_sum
        
        return sums

    # Генерируем все суммы для первого отрезка
    first_part = generate_path_sums(start, max_pos)
    
    # Генерируем все суммы для второго отрезка
    second_part = generate_path_sums(max_pos, end)
    
    # Находим максимальную комбинацию
    max_sum = 0
    for sum1 in first_part.values():
        for sum2 in second_part.values():
            total = sum1 + sum2 - max_val
            if total > max_sum:
                max_sum = total
    
    print(max_sum)

solve()

Используем динамическое программирование по сумме. Определим \(dp[i]\) как количество способов набрать сумму \(i\) заданными монетами.

1. Инициализация: \(dp[0] = 1\) (существует один способ выдать 0 руб. — не выдавать ничего).
2. Для каждой монеты достоинством \(c \in \{1, 2, 5, 10\}\) для всех сумм \(i\) от \(c\) до \(x\) обновляем значение: \(dp[i] += dp[i - c]\).
3. Результат: \(dp[x]\).

Пример программы-решения

Ниже представлено решение на языке Python.

n = int(input())
coins = [1, 2, 5, 10]
dp = [0] * (n + 1)
dp[0] = 1  
for coin in coins:
    for j in range(coin, n + 1):
        dp[j] += dp[j - coin]

print(dp[n])

Перебираем все возможные комбинации монет, сумма которых равна \(x\).

• Для всех возможных количеств монет 10 рублей (\(0 \leqslant a \leqslant \lfloor x/10 \rfloor\)).
• Для всех возможных количеств монет 5 рублей (\(0 \leqslant b \leqslant \lfloor (x - 10a)/5 \rfloor\)).
• Для всех возможных количеств монет 2 рублей (\(0 \leqslant c \leqslant \lfloor (x - 10a - 5b)/2 \rfloor\)).
• Оставшуюся сумму \(d = x - 10a - 5b - 2c\) покрываем монетами 1 руб.
• Увеличиваем счетчик способов на единицу для каждой валидной комбинации \((a, b, c, d)\).

Пример программы-решения

Ниже представлено решение на языке Python.

n = int(input())
cnt = 0
for i in range(n // 10 + 1):
    ost = n - i * 10
    for j in range(ost // 5 + 1):
        ost1 = ost - j * 5
        for k in range(ost1 // 2 + 1):
            cnt += 1
print(cnt)

Разберем несколько случаев.

Если \(g > s\), то можно их поменять местами, количество стопок от этого не изменится. Если \(g < s/2\), то можно сделать только \(g\) стопок.

Если разница не столь велика, можно создать \(g-s\) стопок, выровняв количество золотых и серебряных монет, и затем можно делать стопки: 2 золотые монеты и 1 серебряная, и 2 серебряные монеты и 1 золотая. Когда в каждом типе останется менее 3, в случае остатка 2 можно сделать еще одну стопку.

Пример программы-решения

Ниже представлено решение на языке Python.

n = int(input())
m = int(input())
if n < m:
    n, m = m, n
if n >= 2 * m:
    print(m)
else:
    print((n - m) + (2 * m - n) // 3 * 2 + (1 if (2 * m - n) % 3 > 1 else 0))

С помощью рекурсии сгенерируем все числа, которые можно получить в качестве произведения чисел, состоящих только из двоек. Таких чисел немного. После этого находим наименьшее число \(y\), которое можно представить в виде произведения двоичных чисел.

Пример программы-решения

Ниже представлено решение на языке Python.

correct = set()
all = []
for i in range(18):
    all.append(int("2" * (i + 1)))

def gen(cur, last):
    global correct
    global all
    if cur > int(1e19):
       return
    correct.add(cur)
    for i in range(last, 18):
        gen(cur * all[i], i)            

x = int(input())
gen(1, 0)
correct = sorted(list(correct))

for y in correct:
    if y >= x:
        print(y)
        break