Задача A квалификационного раунда Google Code Jam 2015


Задача A. Аплодирование стоя

В опере премьера, а ваша подруга – примадонна (главная певица). Вас не будет в зале, но вы хотите, чтобы зал аплодировал стоя.

Вначале все зрители сидят. У каждого зрителя своя степень застенчивости. Зритель со степенью застенчивости Si встанет и начнёт аплодировать лишь после того, как Si других зрителей будут аплодировать стоя. Если Si = 0, зритель будет аплодировать стоя независимо от того, делает ли так кто-то ещё. Например, зритель с Si = 2 встанет лишь после того, как увидит, что хотя бы два других человека стоят и хлопают.

Вам известна степень застенчивости каждого зрителя, и вы готовы пригласить друзей примадонны, чтобы все зрители аплодировали стоя. У каждого из друзей может быть любая степень застенчивости, необязательно одна и та же. Какое минимальное количество друзей гарантирует аплодисменты стоя?

Входные данные

В первой строке содержится количество наборов данных, T. Далее приводятся T наборов данных. Каждый из них состоит из одной строки с максимальной степенью застенчивости Smax и группы из Smax + 1 цифр. Цифра с индексом k (начиная с нуля) показывает количество зрителей со степенью застенчивости k. Например, строка «409» означает, что в зале 4 зрителя с Si = 0 и 9 зрителей с Si = 2 (и ни одного с Si = 1 и любым другим значением). В зале может быть от 0 до 9 зрителей с каждой степенью застенчивости.

Строка никогда не заканчивается нулём, поэтому в зале всегда есть хотя бы один зритель.

Выходные данные

Для каждого набора данных выведите строку вида «Case #x: y«, где x – номер набора данных (начиная с 1), а y – минимальное количество приглашаемых друзей.

Пределы

1 ≤ T ≤ 100.

Малый набор данных

0 ≤ Smax ≤ 6.

Большой набор данных

0 ≤ Smax ≤ 1000.

Пример

Входные данные

4
4 11111
1 09
5 110011
0 1

Выходные данные

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0

В наборе #1 зал будет аплодировать стоя без вашего вмешательства: сначала встанет зритель с Si = 0, затем зритель с Si = 1 и т.д.

В наборе #2 надо пригласить друга с Si = 0, и этого достаточно, чтобы весь зал аплодировал стоя.

В наборе #3 оптимальное решение – добавить двух человек с Si = 2.

В наборе #4 единственный зритель, который встанет сразу, поэтому никого приглашать не надо.

Реклама
Запись опубликована в рубрике перевод, программирование с метками . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s