시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 136 | 26 | 19 | 26.027% |
둘레의 길이가 \(L\)인 원형 레일이 있다. 경근이는 레일을 \(L\)등분하여 각 지점에 시계방향으로 \(0\)에서 \(L-1\)까지의 번호를 붙였다. 그리고 번호를 붙인 지점 중 몇 개를 선택하여 시계방향으로 레일 위를 움직이는 개미 \(N\)마리와 반시계방향으로 레일 위를 움직이는 개미 \(M\)마리를 놓았다. 이때 같은 지점에 두 마리 이상의 개미가 있는 경우는 없다.
레일 위에 올라온 모든 개미는 1초에 1의 거리를 움직인다. 레일의 폭은 최대 한 마리의 개미만이 움직일 수 있을 정도로 매우 좁아서, 서로 반대방향으로 움직이는 개미들이 어느 한 위치에서 부딪치고 난 다음에는 그 즉시 서로 방향을 반대로 바꾸어 움직인다. 개미의 크기는 매우 작아서 점으로 취급하여, 정확히 같은 위치에 존재하게 되어야 부딪친다고 하자.
경근이는 모든 개미를 구별할 수 있어서, 모든 개미가 처음과 같은 위치에서 같은 속도를 가지게 되려면 최소한 몇 초가 필요한지 궁금해졌다. 경근이를 도와 이 시간이 몇 초인지 알려주는 프로그램을 작성하라.
첫 번째 줄에 원형 레일의 둘레를 의미하는 \(L\), 시계방향으로 레일 위를 움직이는 개미의 수를 의미하는 \(N\), 반 시계방향으로 레일 위를 움직이는 개미의 수를 의미하는 \(M\)이 공백으로 구분되어 주어진다.
두 번째 줄에는 시계방향으로 움직이는 개미들이 있는 지점을 의미하는 \(N\)개의 정수가 공백으로 구분되어 주어진다.
세 번째 줄에는 반시계방향으로 움직이는 개미들이 있는 지점을 의미하는 \(M\)개의 정수가 공백으로 구분되어 주어진다.
이 문제는 두 개의 부분 문제로 이루어져 있다.
1번 문제의 입력은 \(1 \leq L \leq 600\), \(1 \leq N, M, N+M\leq 600\)을 만족하며 해결하면 20점을 얻을 수 있다.
2번 문제의 입력은 \(1 \leq L \leq 10^{12}\), \(1 \leq N, M, N+M\leq 10^6\)을 만족하며 해결하면 80점을 얻을 수 있다.
첫 번째 줄에 모든 개미들이 처음과 같은 위치, 같은 속도를 가지게 되려면 최소한 몇 초가 필요한지 출력하라.
2 1 1 0 1
2
0.5초와 1.5초에 부딪친 후 2초가 되면 처음과 같은 상태가 된다.
Contest > Coder's High > Coder's High 2015 Side Contest A2번