빙고는 여러 명이 함께 즐길 수 있는 운에 맡기는 게임입니다. 각 플레이어는 숫자가 적힌 종이를 받고, 게임 마스터가 무작위 순서로 숫자를 외칩니다. 플레이어들은 들은 숫자를 지우고, 모든 숫자를 가장 먼저 지우는 사람이 승리합니다. 이 기본적인 게임은 다소 차분한 편이라는 평이 있습니다. 졸지 않는 것 외에는 특별한 행동이 필요하지 않습니다.

이 문제에서는 빠른 판단력을 요구하는 더욱 역동적인 버전의 빙고를 분석해 보겠습니다. 스피드 빙고라고 불리는 이 버전에서는 게임 마스터가 시트에 적힌 숫자를 무작위 순서로 외칩니다. 하지만 숫자가 불려질 때마다, 해당 숫자를 가장 먼저 외친 플레이어만 시트에서 해당 숫자를 지울 수 있습니다. 한 플레이어가 같은 숫자를 여러 번 가지고 있을 경우, 한 번에 한 개만 지울 수 있습니다. 여러 플레이어가 시트에 같은 숫자를 가지고 있을 경우, 반응 속도가 가장 빠른 사람이 스피드 빙고에서 승리할 확률이 높습니다. 하지만 그 이점이 얼마나 클까요? 바로 이 점을 알아내기 위해 여러분의 도움이 필요합니다.

형식적으로는 다음과 같습니다. N명의 각 플레이어는 (아마도) 서로 다른 k개의 숫자(반드시 서로 다를 필요는 없음)를 받습니다. 플레이어 1은 플레이어 2보다 반응 속도가 빠르고, 플레이어 2는 플레이어 3보다 빠르며, 이런 식으로 플레이어 n이 가장 느립니다. 첫 번째 샘플 입력에 해당하는 다음 예를 살펴보겠습니다. 세 명의 플레이어가 각각 네 개의 숫자를 받습니다.

숫자 "1"이 처음 불릴 때, 더 빠른 플레이어 1이 자신의 시트에서 해당 숫자를 지울 수 있습니다. 두 번째 "1"이 불릴 때는 플레이어 2가 해당 숫자를 지울 수 있습니다. 따라서 평균적으로 플레이어 1이 플레이어 2와 3보다 더 나은 성적을 거둘 것으로 예상됩니다. 두 플레이어 모두 플레이어 1이 먼저 도달할 수 있는 숫자가 필요하기 때문입니다. 그러나 플레이어 2와 3은 공통된 숫자가 없기 때문에 플레이어 2가 플레이어 3보다 빠르더라도 그들의 성적은 서로 독립적입니다.

모든 플레이어가 자신의 숫자를 모두 지울 때까지, 즉 모든 플레이어가 자신의 숫자를 지울 때까지 게임이 진행된다고 가정해 보겠습니다. 모든 시트의 숫자(적절한 반복 횟수 포함)를 읽었습니다. 숫자 순서가 균일하게 무작위라고 가정할 때, 각 플레이어가 마지막에 끝날 확률은 얼마입니까?

#8512 upload - done - how_to_reg - auto_awesome Special judge stop_circle Grading on hold

Bingo for the Win! timer 1s memory 1024MB

#8512
Special judge

Grading on hold

Bingo for the Win! 1s 1024MB