ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1061. Диспетчер буферов

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Блоки данных, считываемые СУБД с жесткого диска, хранятся в оперативной памяти в фиксированном количестве предварительно выделенных буферов. Каждый буфер может содержать один блок данных. Каждый буфер может быть либо свободным, либо занятым некоторыми данными. Когда СУБД собирается считать блок данных с жесткого диска, она должна решить, какой буфер использовать для хранения этого блока данных. Если есть свободные буферы, то используется один из них. Если свободных буферов нет, то необходимо очистить один из занятых буферов, но только в том случае, если он не был заблокирован какой-то частью СУБД.
Выбор буфера для очистки критически важен для производительности СУБД. Было разработано множество алгоритмов выбора. В вашей СУБД будет реализован алгоритм Advanced Buffer Management, который считывает несколько последовательных блоков данных с жесткого диска в последовательные буферы памяти.
Буферы пронумерованы от 1 до N, где N – общее количество буферов. Каждый буфер может находиться в любом из следующих состояний: свободен, занят или заблокирован. Каждому занятому буферу присваивается целое число от 1 до 9 – ценность хранимой в нем информации. Ценность свободных буферов считается равной нулю. Заблокированные буферы не могут быть ни использованы, ни очищены, и их ценность не определена.
Получив запрос на чтение K блоков данных с жесткого диска, диспетчер буферов должен выбрать K последовательных (т.е. с номерами от L до L + K − 1) незаблокированных буферов с минимальной суммарной ценностью или сообщить о том, что это невозможно. Последнее может произойти, если некоторые буферы заблокированы или общее количество буферов меньше K.
Напишите программу, которая моделирует обработку одного запроса в диспетчере буферов по вышеуказанному алгоритму.

Исходные данные

Первая строка содержит целые числа N и K (1 ≤ N ≤ 100000; 1 ≤ K ≤ 10000).
Начиная со второй строки, дается описание состояния буферов. Состояние каждого буфера представлено одним символом:
  • 0 – соответствующий буфер свободен.
  • 1 – соответствующий буфер занят и имеет ценность 1.
  • 2 – соответствующий буфер занят и имеет ценность 2.
  • ...
  • 9 – соответствующий буфер занят и имеет ценность 9.
  • * – соответствующий буфер заблокирован.
Эти символы расположены в последовательных строках, сгруппированных по 80 символов в строке без пробелов. Таким образом, каждая строка, начиная со второй, содержит ровно 80 символов (кроме, возможно, последней строки).

Результат

Выведите целое число L – номер буфера, начиная с которого нужно выбрать K последовательных буферов для очистки, чтобы гарантировать минимально возможную суммарную ценность. Если существует несколько таких значений L, выведите наименьшее из них.
Выведите 0, если невозможно найти K последовательных незаблокированных буферов.

Примеры

исходные данныерезультат
100 53
2165745216091853477755800393859785807207523169954341**7363*9*94664808*4777717089
09825185827659480548
0
100 10
2165745216091853477755800393859785807207523169954341**7363*9*94664808*4777717089
09825185827659480548
36
Источник задачи: 2000-2001 ACM Northeastern European Regional Programming Contest