4개의 댓글이 있습니다.
-
-
amok -
https://algospot.com/judge/submission/detail/365509
정수연산만을 이용했는데 안 되는데요...
그런데 지금과 같은 상황에서 실수연산을 피하는 것이 무슨 의미가 있죠?
8년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
amok
POKTANJU
로직은 맞는 것 같은데 오답이 뜨네요.
검색해 보니까 문제에 출제자가 의도한 함정이 있는 것 같은데... 뭔지 모르겠네요.
답은 K에상관없이 1/(N-1) 아닌가요?
제 풀이는 다음과 같습니다:
이 문제의 게임을 하되, 둥글게 둘러앉아서 하는 것이 아니라
1 2 3 4 5 ... N-2 N-1 N
처럼 일렬로 늘어서서 게임하고, 1번이 왼쪽으로 술병을 보내거나 N번이 오른쪽으로 술병을 보냈을 때 게임이 끝난다고 한다면, 1번이 왼쪽으로 술병을 보내서 게임이 끝날 확률은 N/(N+1) 이고, N번이 오른쪽으로 술병을 보내서 게임이 끝날 확률은 1/(N+1) 이다.
원래 문제의 게임을 플레이하다 보면 언젠가 K-1번이나 K+1번에게 술병이 가는 순간이 오는데, 일반성을 잃지 않고, 둘 중 K+1번에게 먼저 술병이 돌아갔다고 가정하자. 이 때 아직 K에게는 술병이 돌아가지 않았다. 사람들이 둥글게 앉은 모습을 일렬로 펴서 나타내면 다음과 같다.
K K+1 K+2 ... N-1 N 1 2 3 ... K-2 K-1 (현재 술병은 K+1번이 가지고 있다)
이 상황에서 K번과 K-1번 둘 중 K-1번에게 먼저 술병이 돌아가면 (K번을 제외한 나머지 모두가 술취했으므로) K번은 술 대신 물을 마시게 된다. 이 확률은 위에서 관찰했다시피 1/(N-1)이다.
K = 2 이거나 K = N 일 때도 과정이 거의 같고, 구하려는 확률 역시 같다.
그런데 이렇게 구할 수 있다면 문제 조건의 N<=20000이라는 제한이 필요없는데...
다른 제출 답안들의 수행 시간을 봐도 그렇게 간단하게는 안 풀리고 O(N)정도에 풀리는 문제같네요.
제가 뭔가 잘못 생각하고 있는 게 있다면 지적 부탁드립니다.
8년 전