Вася любит писать раунды на Codeforces. Когда раунд заканчивается и начинается системное тестирование, Вася внимательно следит за всеми посылками.
Всего есть $$$n$$$ решений, $$$i$$$-е из них нужно протестировать на $$$a_i$$$ тестах, тестирование на одном тесте занимает $$$1$$$ секунду. Решения поступают на тестирование по очереди в порядке от $$$1$$$ до $$$n$$$. Всего на серверах запущено $$$k$$$ отдельных тестирующих процессов, которые работают одновременно. Каждый из них может обрабатывать одновременно только одно решение.
В любой момент времени $$$t$$$, когда какой-то из тестирующих процессов не обрабатывает ни одно решение, он берет очередное решение из очереди и тестирует его в порядке увеличения номеров тестов. Пусть номер этого решения — $$$i$$$, тогда оно будет тестироваться на первом тесте с момента времени $$$t$$$ по момент времени $$$t + 1$$$, затем на втором тесте до момента времени $$$t + 2$$$ и так далее. Полностью это решение будет протестировано в момент времени $$$t + a_i$$$, и этот процесс сразу начнет тестировать другое решение.
Рассмотрим некоторый момент времени, пусть сейчас полностью протестировано $$$m$$$ решений. Тогда на странице с посылками отображается надпись «Системное тестирование: $$$d$$$%», где $$$d$$$ вычисляется по формуле
$$$$$$d = round\left(100\cdot\frac{m}{n}\right),$$$$$$
где $$$round(x) = \lfloor{x + 0.5}\rfloor$$$ есть функция округления числа до ближайшего целого.
Вася называет решение интересным, если существовал момент времени (возможно, не целочисленный), когда это решение исполнялось на некотором тесте $$$q$$$, и надпись сбоку гласила «Системное тестирование: $$$q$$$%». Найдите число интересных решений.
Обратите внимание, что если несколько процессов одновременно будут свободны и захотят взять первое решение из очереди (например, в начальный момент времени), то не имеет значения, в каком порядке они будут получать доступ к очереди решений.
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 100$$$) — число отправленных решений и количество тестирующих процессов, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 150$$$), где $$$a_i$$$ равно числу тестов, на которых будет тестироваться $$$i$$$-е решение.
В единственной строке выведите число интересных решений.
2 2 49 100
1
4 2 32 100 33 1
2
14 5 48 19 6 9 50 20 3 42 38 43 36 21 44 6
5
Рассмотрим первый пример. В момент времени $$$0$$$ оба решения начинают тестироваться. В момент времени $$$49$$$ первое решение полностью протестировано, поэтому в момент времени $$$49.5$$$ второе решение тестировалось на тесте $$$50$$$, а надпись сбоку гласила «Системное тестирование: $$$50$$$%» (так как протестировано одно решение из двух). Значит, это интересное решение.
Рассмотрим второй пример. В момент времени $$$0$$$ начинают тестироваться первое и второе решения. В момент времени $$$32$$$ первое решение полностью протестировано, начинает тестироваться третье решение, надпись сбоку гласит «Системное тестирование: $$$25$$$%». В момент времени $$$32 + 24.5 = 56.5$$$ третье решение тестируется на $$$25$$$-м тесте, а надпись сбоку все еще не изменилась, значит, это решение — интересное. После этого третье решение будет полностью протестировано в момент времени $$$32 + 33 = 65$$$, четверное решение будет полностью протестировано в момент времени $$$65 + 1 = 66$$$. Надпись сбоку будет гласить «Системное тестирование: $$$75$$$%», и в момент времени $$$74.5$$$ второе решение будет тестироваться на $$$75$$$-м тесте. Значит, оно тоже интересное. Значит всего есть два интересных решения.
Название |
---|