Codeforces Round 216 (Div. 2) |
---|
Закончено |
Одним прекрасным утром n дураков выстроились в ряд. После этого они пронумеровали друг друга номерами от 1 до n включительно. Каждый дурак получил уникальный номер. Дураки решили не менять своих номеров до конца веселья.
У каждого дурака есть ровно k патронов и пистолет. Вероятность того, что дурак с номером i убьет дурака, в которого совершит выстрел, равна pi процентов.
Дураки решили провести несколько раундов веселья. Каждый раунд веселья состоит в следующем: каждый еще живой дурак совершает выстрел в другого живого дурака с наименьшим номером (дураки не настолько глупы, чтобы стрелять в самих себя). Все выстрелы совершаются одновременно. Если остался ровно один живой дурак, то он не совершает выстрелов.
Назовем ситуацией множество номеров всех живых дураков на некоторый момент времени. Будем говорить, что ситуация возможна, если для некоторого целого числа j (0 ≤ j ≤ k) существует ненулевая вероятность, что через j раундов веселья будет иметь место именно такая ситуация.
Валера знает числа p1, p2, ..., pn и k. Помогите Валере определить количество различных возможных ситуаций.
В первой строке заданы два целых числа n, k (1 ≤ n, k ≤ 3000) — изначальное количество дураков и количество патронов у каждого дурака.
Во второй строке задано n целых чисел p1, p2, ..., pn (0 ≤ pi ≤ 100) — указанные вероятности (в процентах).
Выведите единственное число — ответ на задачу.
3 3
50 50 50
7
1 1
100
1
2 1
100 100
2
3 3
0 0 0
1
В первом примере любая ситуация возможна, кроме ситуации {1, 2}.
Во втором примере ровно один дурак, поэтому он не совершает выстрелов.
В третьем примере возможны ситуации {1, 2} (после нуля раундов) и «пустая» ситуация {} (после одного раунда).
В четвертом примере возможна только ситуация {1, 2, 3}.
Название |
---|