Олимпиадный тренинг

Задача . Социальное дистанцирование II


Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции xi. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

Входные данные
Первая строка ввода содержит N. Каждая из последующих N строк описывает одну корову двумя числами x и s, где x - позиция коровы, а s равно 0 для здоровой коровы и 1 для больной. Как минимум 1 корова больна. И все коровы, которые могли стать больными от распространения болезни уже больны.
Выходные данные
Определите минимальное количество коров, которые изначально были больны, перед любым распространением болезни.
Примеры
Входные данные Выходные данные
1 6
7 1
1 1
15 1
3 1
10 0
6 1
3



time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя