실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
새로운 기숙사는 N개의 큰 방 (2 <= N <= 3,000,000)로 이루어진 원형으로, 방은 0부터 N-1까지 번호가 매겨져 있으며, 방 N-1은 방 0과 인접해 있습니다.
하루가 끝나면 학생들은 천천히 기숙사로 돌아옵니다. 각 학생들은 차지하고 싶은 선호하는 방이 있습니다. 그러나 선호하는 방이 이미 다른 학생에 의해 점유되어 있다면, 그녀는 그 방으로부터 순차적으로 스캔을 시작하여 최초의 빈 방을 찾아 그 방을 차지합니다. 만약 그녀가 N-1번 방을 넘어가면, 그녀는 0번 방부터 스캔을 계속합니다.
각 학생의 선호 방이 주어진 대로, 모든 학생들이 기숙사로 돌아온 후에 남아있는 방 중 가장 작은 인덱스를 결정해 주세요. 이 질문에 대한 답은 학생들이 기숙사로 돌아오는 순서에 영향을 받지 않습니다.
거대한 양의 입력을 읽는 문제를 피하기 위해, 이 문제의 입력은 K줄 (1 <= K <= 10,000)인 간결한 형식으로 지정됩니다. 지정된 형식은 다음과 같습니다:
X Y A B
이들 줄 중 하나는 XY 학생들에 대한 선호 방을 지정합니다: X 학생들은 각각 방 f(1) .. f(Y)를 선호합니다. 여기서 f(i) = (Ai + B) mod N입니다. A와 B의 값은 0...1,000,000,000 범위내에 있습니다.
모든 문제에 대한 표준 메모리 제한 64MB를 잊지 마세요.
10 3 3 2 2 4 2 1 0 1 1 1 1 7
5
출처: USACO 2013 November Contest, Gold Problem 1. Empty Stalls