Компьютерный центр г. Светлогорска

Рассмотрим метод подсчёта на основе следующей задачи:

Задача

У бухгалтера есть годовой отчёт, содержащий большое количество чисел. Нужно обработать все эти данные, используя кнопочный калькулятор. Бухгалтер знает, что калькуляторы, которые продают в ближайшем магазине, не очень качественные. Он даже знает статистику по каждой кнопке: сколько нажатий она выдерживает, не ломаясь. Бухгалтер хочет узнать, сколько калькуляторов ему нужно закупить, чтобы обработать весь отчёт.

Основная идея решения этой задачи – посчитать, сколько раз встречается в отчете каждая цифра. Для подсчета можно использовать отдельные переменные cnt0 – для подсчёта нулей, cnt1 – для подсчёта единиц и т.д. Эти переменные можно объединить в единую структуру – список подсчётов из \(10\) элементов: cnt[0], cnt[1], ..., cnt[9], в котором индекс элемента соответствует цифре, а значение элемента – количеству раз, в котором эта цифра встречается в отчёте.

Сохраним информацию о прочности кнопки в списке press, где press[i] – это количество нажатий, которые выдерживает кнопка с цифрой i.

Для получения ответа необходимо поделить каждое значение cnt[i] на press[i] с округлением вверх – так мы для каждого i получим, сколько минимум калькуляторов нужно, чтобы обработать все цифры i в отчёте. Далее, из результата для каждой цифры достаточно выбрать максимальный.

Рассмотрим пример:

Список ncalc – это список, хранящий минимальное количество калькуляторов для каждой кнопки. Кнопка \(2\) требует больше всего калькуляторов – \(20\), поэтому и итоговый ответ равен двадцати. Простое и лаконичное решение получается именно из-за удобного хранения данных в списке подсчётов.

n = int(input())
a = list(map(int, input().split()))
press = list(map(int, input().split()))

cnt = [0] * 10
for ai in a:
    cnt[ai] += 1

mx = float('-inf')
for i in range(10):
    k = (cnt[i] + press[i] - 1) // press[i]
    mx = max(mx, k)
print(f"{mx}")

Ещё одна ситуация упорядоченности, которая встречается в задачах – алфавитный или лексикографический порядок для объектов-строк.

Задача

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

Поставим в соответствие каждому символу строки его ASCII-код. Коды заглавных английских символов идут подряд от \(65\) до \(90\). Создадим список подсчетов, где будем хранить количество букв 'A' в cnt[65], букв 'B' – в cnt[66], ..., букв 'Z' – в cnt[90]. Упорядоченность индексов списка будет поддерживать и алфавитный порядок символов.

s = input()

cnt = [0] * 100
for c in s:
    cnt[ord(c)] += 1

ans = ""
for i in range(90, 64, -1):
    ans += chr(i) * cnt[i]
print(f"{ans}")

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

Практические задания