정올 기상관측센터는 다음 날의 일기예보를 위해 구름을 덩어리 단위로 관측한다.

관측 결과, 관측한 지역에 동풍이 불고 있으며, 모든 구름이 왼쪽에서 오른쪽으로 이동하고 있음을 알아냈다.

구름은 각각 다른 크기를 가지고 있으며, 1부터 N까지의 좌표를 가진 수직선 상단에 제각기 다른 속도를 가지고 떠다닌다.

1, 2, 3,…N까지의 각 정수 좌표에는 도시들이 위치한다.

속도 v_i를 가진 구름은 하루에 v_i만큼 오른쪽으로 움직인다.

두 개의 구름은 한 도시 상공에서 만났다고 해서 서로 합쳐지지는 않고 다음 날 각자의 속도를 가지고 움직인다.

어느 날 어느 도시 상공에, 구름 크기의 총합이 100 이상이면, 그 도시 지역은 그 날 비가 온다.

예를 들어 N=7개의 도시가 있는 상태에서, 오늘 관측한 구름이 다음과 같이 위치해 있다고 하자.

구름

크기

40

50

70

도시

1

2

3

4

5

6

7

도시 1 상공에 위치한 구름의 속도가 3,

도시 3 상공의 구름 속도가 2,

도시 4 상공의 구름 속도가 1이라고 하자.

다음 날 오른쪽 두 구름이 도시 5 상공에서 만나 총 120의 구름량이 도시 5 위에 생긴다. 따라서 도시 5에 비가 오게 된다.

구름

크기

40

50+70

도시

1

2

3

4

5

6

7

그 다음 날 크기 40의 구름과, 크기 50의 구름이 도시 7 상공에서 만나 총 90의 구름량이 도시 7 상공에 생기지만, 총합이 100이 넘지 않으므로 이 날 도시 7엔 비가 내리지 않는다.

구름

크기

70

40+50

도시

1

2

3

4

5

6

7

오늘 하늘의 구름의 상태를 입력받아, 1번부터 N까지의 도시 중에, K일 뒤 비가 내리는 도시의 수를 출력하는 프로그램을 작성하라.

#4378 upload 131 done 36 how_to_reg 31

구름 timer 1s memory 16MB

#4378

구름 1s 16MB