879B: Table Tennis

난이도

어려울뻔했는데 난이도는 3/10

문제보기

http://codeforces.com/problemset/problem/879/B

n 명의 사람들이 탁구를 치는데, 일렬로 서서 게임을 하게된다. 맨 처음엔 게임은 첫 사람과 둘째 사람이 하게되는데 이긴사람은 그대로있고 진 사람은 줄의 맨 뒤로 가게된다.

어떤 사람이 k번째 이기면 게임은 종료되며, 이기고 진다는 판정은 입력받은 각 플레이어의 힘ai으로 결정된다.

출력은 k번 승리한 플레이어의 힘을 출력하면 된다.

2<=n<=500, 2<=k<=10^12,   1<=ai<=n

즉, 아래와 같이 입력되면

2 2

1 2

2명의 플레이어 중 2번 이긴사람의 힘을 출력하란거다.

정답은 2이다.

입력이

4 2

3 1 2 4

인 경우 4명중 2번이긴 사람의 힘을 출력하면되니 3을 출력하면된다.

2 1000000000000

2  1

인 경우 2를 출력하면된다.

해당문제도 꽤 쉽다.

하지마나 입력값이 어마어마하므로 몇가지 처리가필요하다. 언제까지고 k만큼이나 체크할 수 없다. 1연산수가 2억이넘으면 시간초과일것이 뻔하다. 해당 index의 파워가 최대와 같다면 걍 그녀석을 출력하면된다. 

그외에 이기고 지는 것을 처리하는 그런건 배열을 전체적으로 앞당기고 할 필요도 없이 i, j index를 설정해 i를 전판에 이겼던 놈, j를 새로온놈처럼 취급해 각각 상황에 맞게 처리하면된다.

즉 다음과 같은 경우를 생각해보자.

4 2 

2 1 3 4 

다음과 같은 알고리즘(순서도)를 생각해보았다.

cnt=k, i=0, j=1;

while (cnt){ 

2 1 3 4 ,     

i  j       ... cnt--;

2 1 3 4   

i     j    .... i=j, j++,cnt= k-1;

2 1 3 4  

      i j  .... i=j, j++, j>=n?, j=0, cnt=k-1;    

2 1 3 4

j       i ... cnt--;

}

print a[i];

나는 알고리즘은 맞았으나, k를 입력받는걸 long long으로 받지 않았기 때문에 틀렸었다. (대회에서는 몇가지 테스트케이스만 맞으면 pretest 통과라고 해주기땜시... 몰랐음 ㅡ.ㅡ;;) 

대회가 끝난 후 확인해보니 시간초과도 아니였고.... 입력 받은 자료형 때문이였단걸 확인 후 조금은 억울하기도했으나 내책임.... 푸하하 ㅠ.ㅠ

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/879B.c