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

Обсуждение задачи 1611. Децимация

Recursion
Послано marat 26 апр 2011 15:12
It's not difficult to prove that if you optimally solved the problem with n conductors, n-1 conductors should be solved optimally too.
Let a(n,k) be minimal total number of fined fare dodgers and good conductors. Then

a(n,k) = MIN i FROM 0 TO k OF { a(n-1,i) + (n+k-[n is not a good conductor])/10 - (n-1+i)/10 }

Details:
Given k friends we should divide them into two parts. The first part should go and safe n-1 conductors and the second should stay between n-1 and n conductors. All we have to do is to count amount of fined friends in the second part + a(n-1,the first part) + whether n-th conductors is fined(1 or 0).

[logical expression A] = 1, if A is true
                         0, otherwise

What concerns test try these ones:
------------------------
10 2
1110001011
possible answer:
0
2 2 1
------------------------
10 3
0001111111
possible answer:
1
0
------------------------
10 0
0001110001
possible answer:
1
0
------------------------
20 5
11111001110001110001
possible answer:
0
3 3 2 1