최근 학교 일등 여러가지 사정으로(뭐 핑계지만...), SRM에 거의 참가하지를 못했는데,
요즘 들어서 지나쳐버린 이전 SRM 문제들을 한번씩 풀어보고 있다.
그 중에 내가 좀 놀랜 기발한 문제...
Problem Statement
John is playing with balls. All of the balls are identical in weight and considered to have a zero radius. All balls are located on the same straight line and can move only along this line. If a ball rolling to the right and a ball rolling to the left at the same speed collide, they do not change speed, but they change direction.
You are given vector <int> x. x[i] is the initial position of the i-th ball. John decides the direction for each ball (right or left) with equal probability. At time 0, he rolls the balls in the chosen directions simultaneously at a speed of one unit per second. Return the expected number of bounces between all balls during T seconds (including those collisions that happen exactly at T seconds).
간단하게 정리하면,
직선 좌표계 상의 여러 위치에 공들이 놓여져 있다.
이 공들은 완전히 제로의 지름을 가지고 있다고 가정한다. (즉, 크기는 고려하지 않는다는 이야기)
그리고 각 공들은 처음에 랜덤으로 좌측이나 우측으로 방향이 설정되어진다.
시간이 흐르기 시작하면, 그 공들은 지정된 방향으로 구르기 시작하고, 서로 부딫히는 경우에는 다시 반대방향으로 움직인다.
공의 초기 위치는 모두 양의 정수이며, 이동속도는 초당 1을 이동한다.
(다시 말해, 어떤 공이 15의 위치에 있고, 우측으로 설정되었다면, 3초후에는 18에 있는 것이 된다)
이렇게 공의 위치가 배열로 들어오고, 이동시간 T가 주어졌을때,
T초의 시간 이내에 공이 몇번을 부딫히게 되는지 충돌 기대값을 구하는 문제.
예를 하나 보자.
{5, 8}
T = 2
공이 5와 8의 위치에 있고, 2초간의 시간이 주어진다.
공은 각각 좌/우측 중 하나로 움직이기 때문에, {좌좌}, {좌우}, {우좌}, {우우}의 4가지 가능성을 가지고 있다.
그 중, {우좌}의 케이스를 제외한 3가지는 공이 충돌할 수가 없게 된다.
{우좌}의 경우는 1초후, {6, 7}이 되고, 다음 1초 이내에 절대로 공이 부딫히기 때문에,
이 케이스의 답은 0.25 (1회 부딫힐 확률이 1/4)가 된다.
만약 위의 케이스에서 T = 1 이라면,
서로 마주보고 움직인다고 하더라도, 시간이 부족해서, 충돌 기대값은 0이 된다.
좀 더 어려운 예
{4, 6, 9}
T = 3
조금 복잡하지만, 공이 3개이기 때문에 총 8가지 이동 패턴이 생긴다.
일단 좌를 L, 우를 R로 표시하면,
{LLL}, {LLR}, {LRR}, {RRR}의 경우는 충돌이 일어나지 않는다. (생각해보자)
그리고 {LRL}, {RLR}의 경우는 1회 충돌이 일어난다.
마지막으로 {RLL}, {RRL}의 경우는 부딫힌 공이 다시 다른공과 부딫히기 때문에, 총 2회 충돌이 일어난다.
결국, 각 1/8의 확률로, 1회 충돌이 2개, 2회 충돌이 2개로,
(1/8 + 1/8)*1 + (1/8 + 1/8)*2 = 6/8로서, 충돌 기대값은 0.75가 된다.
일단 해답은 접어둔다.
궁금하면 Solution
'알고리즘 관련' 카테고리의 다른 글
| P와 NP (0) | 2012/05/14 |
|---|---|
| Google Code Jam 2010 Qualification Round 통과 (2) | 2010/05/21 |
| Member SRM 458 Div 1 Easy - Bouncing Balls (7) | 2010/03/12 |
| Google Code Jam 2009, Round 3 진출 실패 (8) | 2009/09/27 |
| Google Code Jam 2009 (6) | 2009/09/14 |
| 1만엔 게임 메인 전략 결정 완료 (5) | 2009/09/02 |
