В одной прямоугольной стране месяц состоит из n… (информатика)

HРабочие дни

В одной прямоугольной стране месяц состоит из $n$ дней, а неделя из $m$ дней, дни в месяце нумеруются от 1 до $n$ , дни недели нумеруются от 1 до $m$ . В рабочем календаре все числа месяца, как и обычно, записываются в несколько строк, каждая из которых представляет собой одну неделю, то есть имеет длину $m$ . При этом первая и/или последняя строка месяца может быть меньше $m$ . Если для первой строки это так, то первая строка начинается в некоторый $k$ -й день недели и заканчивается в $m$ -й день недели. Если для последней строки это так, то она начинается в 1-й день недели и заканчивается в некоторый $r$ -й день недели.

Согласно закону этой страны, распределение рабочих и выходных дней внутри одного месяца происходит так: в упомянутой записи месяца выделяется самая большая по площади прямоугольная область из рядом стоящих чисел, которые и объявляются рабочими. Все остальные числа месяца, не вошедшие в указанную выше область, объявляются выходными.

Известно, что первое число некоторого месяца приходится на $k$ -й день недели. Требуется вычислить сколько рабочих дней в этом месяце.

Формат ввода: на вход подаются три целых числа $n, m, k$ через пробел — число дней в месяце, в неделе и номер дня недели, на который приходится первое число заданного месяца. $1 \leq m < n \leq 100$ , $1 \leq k \leq m$ .

Формат вывода: вывести одно целое число — количество рабочих дней в рассматриваемом месяце.

Примеры:
Ввод 39 10 6 — вывод 30
Ввод 12 5 2 — вывод 8
Ввод 13 5 2 — вывод 9
Ввод 15 4 1 — вывод 12

Решение

Идея. Календарь — это строки-промежутки столбцов:

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

Прямоугольник — это несколько подряд идущих строк, а его ширина — длина пересечения их промежутков столбцов. Строк не больше , поэтому перебираем все пары строк и берём максимум площади: (число строк) · (ширина пересечения).

Проверка на примере (): первая строка — столбцы .. ( дней), , , . Три полные строки дают . Это максимум, ответ .

Проверка на примере (): строки: , , . Первые две строки дают , все три — . Максимум .

Код (Python):

n, m, k = map(int, input().split())
rows = [(k, m)]
r = n - (m - k + )
for _ in range(r // m):
    rows.append((, m))
if r % m > :
    rows.append((, r % m))
best = 
for i in range(len(rows)):
    lo, hi = , m
    for j in range(i, len(rows)):
        lo = max(lo, rows[j][])
        hi = min(hi, rows[j][])
        if hi < lo:
            break
        best = max(best, (j - i + ) * (hi - lo + ))
print(best)

💡 Почему так

Календарь разбивается на строки-промежутки столбцов. Прямоугольник из соседних чисел — это набор подряд идущих строк с общими столбцами, поэтому достаточно перебрать все пары строк и взять наибольшую площадь.

Ответ

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

Помогло?

В одной прямоугольной стране месяц состоит из n дней, а неделя из…