print1957. Поезд

printПоезд

Ограничения: время – 300ms/600ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Имеется состав из `N` плацкартных вагонов. Вагоны стандартные: по 54 места в каждом, места разделены на 9 блоков. Расположение мест и вагонов показано на рисунке:

26040.png

Вам требуется разместить в вагонах `М` человек так, чтобы расстояние между двумя самыми удалёнными друг от друга людьми было минимальным. Расстояние измеряется по прямой вдоль вагонов. Будем считать, что расстояние между местами в одном блоке равно нулю. Например, расстояние между любой парой мест 1, 2, 3, 4, 53 или 54 равно нулю. Между местами в соседних блоках расстояние равно 1. Например, между 1 и 6, 53 и 7. Расстояние между вагонами равно 6. То есть расстояние между местом 33 первого вагона и местом 1 второго вагона равно 6.
Рассмотрим пример из одного вагона (первый тест):

26041.png

Серым помечены занятые места, а белым – свободные. Нужно разместить 6 человек. Оптимально будет занять места 30, 32, 37, 38, 39, 40 в конце вагона. Наибольшее расстоянием будет равно 1.
В первой строке входного файла содержатся 2 целых числа `N` (`1\ ≤\ N\ ≤\ 10\ 000`) и `M` (`1\ ≤\ M\ ≤\ 10^6`).
Каждая из следующих `N` строк содержит по 54 символа — информацию о местах в соответствующих вагонах: 0 — место свободно, 1 — занято.
Выведите в выходной файл одно искомое число, либо `-1`, если разместить всех людей невозможно.

Пример ввода 1

1 6
101010101110111110101010111110101111000000111111111011

Пример вывода 1

1

Пример ввода 2

2 2
011111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111011111111111111111

Пример вывода 2

22
Источник: XVI межвузовская олимпиада по программированию, Вологда, 2013
loading