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

Чемпионат Урала 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Децимация

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Децимация — казнь каждого десятого по жребию,
высшая мера дисциплинарных наказаний в древнеримской армии.
Вы думаете, легко работать кондуктором в трамвае? Заядлые безбилетники так и норовят проехать бесплатно. А контролёры безжалостно штрафуют не только безбилетников, но и самих кондукторов — за то, что те не справляются со своими обязанностями.
В ходе операции «Безбилетник-2008», которую недавно провела Ассоциация контролёров города Екатеринбурга, выяснилось, что более чем в половине трамваев в момент проверки ехал хотя бы один безбилетник. Главный Контролёр Екатеринбурга рассвирепел и решил прибегнуть к наказанию: выстроить провинившихся кондукторов в колонну и каждого десятого тут же оштрафовать в размере средней месячной зарплаты кондуктора.
Главному Безбилетнику Екатеринбурга стало жалко бедных кондукторов, и он решил им помочь, так как знал, что среди них есть хорошие, вполне справляющиеся со своими обязанностями. Просто некоторые их пассажиры в момент проверки еще не успели оплатить проезд. Перед тем как кондукторов начнут штрафовать, Главный Безбилетник может поставить в колонну некоторых своих друзей-безбилетников. При этом Главный Контролёр, конечно, не догадывается о том, что не все стоящие в колонне — кондуктора. Он оштрафует каждого, чей порядковый номер делится на 10 (люди в колонне нумеруются начиная с единицы). Каким образом Главный Безбилетник должен расставить своих друзей, чтобы в сумме было оштрафовано как можно меньше безбилетников и хороших кондукторов?

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

В первой строке через пробел записано два целых числа: n — количество провинившихся кондукторов (1 ≤ n ≤ 10000), и k — количество друзей Главного Безбилетника, готовых помочь кондукторам (0 ≤ k ≤ 50). Вторая строка состоит из n символов: i-й символ равен «1», если изначально на i-м месте в колонне стоит хороший кондуктор, и «0» — если плохой.

Результат

В первой строке выведите минимальное суммарное количество оштрафованных безбилетников и хороших кондукторов. Во второй строке выведите число m — сколько безбилетников следует поставить в колонну, и затем m целых чисел — их номера в получившейся колонне. Все числа в строке должны быть разделены пробелами.

Примеры

исходные данныерезультат
10 2
0000000001
0
2 5 12
10 2
1111111111
1
0
Автор задачи: Александр Ипатов (идея — Станислав Васильев)
Источник задачи: XII чемпионат Урала по спортивному программированию, 29 марта 2008 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1611. Децимация