Informatica Online Judge

  위 아래 [1299 / 0513]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 4   Total Tried : 39


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 김성윤)]

Background

경곽이는 이상한 자료를 너무 많이 봐서 지옥에 갇혔다.

지옥은 경곽이의 현위치보다 한칸 위에 있는 n개의 계단으로 이루어져 있으며, 경곽이는 1초에 최대 p칸을 오르거나 내릴 수 있다.

각 계단에는 1,0,-1이 적혀 있고, 맨 위의 타일에는 0이 적혀있다.

경곽이의 현위치 한 칸 아래에는 경곽이의 위치보다 더 위로 올라가면 경곽이가 죽게 만드는 물이 있다.

1이라고 적혀있는 타일을 밟으면 물이 한칸 올라오고, -1이라고 적혀있는 타일을 밟으면 물이 한칸 내려간다. 또, 0이라고 적혀있는 타일을 밟으면 아무 일도 일어나지 않는다.

그런데, 경곽이를 지옥에 집어넣은 악마는, 이렇게 두면 경곽이가 무한히 오래 살 수 있음을 알아내고, -1이라고 적혀있는 계단을 밟으면 그 수가 1로 바뀌도록 설정했다.

과연 경곽이는 얼마나 오래 살 수 있을까?

Input

두 정수 n과 p를 입력받는다.

그 뒤에, n개의 1,0,또는 -1을 입력받는다.

[입력값의 정의역]
1 <= n <= 50,000
1 <= p <= 100

[SubTask Info]
#1 : n <= 10, p <= 5 (25%)
#2 : n <= 50,000, p <= 100 (75%)

Output

얼마나 오래 살 수 있을지를 출력한다. 만약 무한히 오래 살 수 있다면 Infinite을 출력한다.

IO Example

입력
3 2
1 -1 0

출력
10

설명) 다음과 같이 움직이면 10초동안 살 수 있다.

(물의위치,현재 경곽이의 위치)
(-1,0)>(-2,2)>(-2,3)>(-1,2)>(-1,3)>(0,2)>(0,3)>(1,2)>(1,3)>(2,2)>(2,3)

입력2
5 4
0 1 -1 1 0

출력2
Infinite

설명) 첫번째와 다섯번째 칸을 무한히 많이 왔다갔다할 수 있다.

입력3
10 2
-1 0 1 1 1 0 1 -1 1 0

출력3
28



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]