레이팅 미적용농부 존의 새 축사는 N개의 칸이 거대한 원형으로 배치된 구조이며 (2 <= N <= 3,000,000), 칸에는 0..N-1의 번호가 붙어 있고 칸 N-1은 칸 0과 인접해 있다.
매일 하루가 끝나면 FJ의 소들이 한 마리씩 축사로 돌아오는데, 각 소는 자신이 차지하고 싶은 선호 칸이 있다. 하지만 어떤 소의 선호 칸이 이미 다른 소에게 점유되어 있으면, 그 소는 그 칸부터 순서대로 앞으로 훑어가며 처음으로 비어 있는 칸을 찾아 그 칸을 차지한다. 칸 N-1을 지나치면 칸 0부터 계속 훑는다.
각 소의 선호 칸이 주어질 때, 모든 소가 축사로 돌아온 후에도 비어 있는 칸 중 번호가 가장 작은 것을 구하시오. 답은 소들이 돌아오는 순서에 의존하지 않음에 유의한다.
입력이 너무 커지는 것을 피하기 위해, 입력은 "X Y A B" 형태의 K개의 줄로 압축되어 주어진다 (1 <= K <= 10,000). 이는 총 XY마리 소의 선호 칸을 나타낸다: 칸 f(1) .. f(Y) 각각을 X마리의 소가 선호하며, 여기서 f(i) = (Ai + B) mod N이다. A와 B의 값은 0...1,000,000,000 범위이다.
모든 문제에 적용되는 표준 메모리 제한 64MB를 잊지 말 것.
첫째 줄에 공백으로 구분된 두 정수 N과 K가 주어진다.
둘째 줄부터 1+K번째 줄까지, 각 줄에 정수 X Y A B가 주어지며, 위에서 설명한 대로 해석한다. 이 줄들이 나타내는 소의 총 마릿수는 최대 N-1이다. 여러 줄이 같은 칸에 소를 추가할 수 있다.
비어 있는 칸의 최소 번호를 출력한다.
empty.in · 출력을 쓸 파일 empty.out10 3
3 2 2 4
2 1 0 1
1 1 1 75Output details: All stalls end up occupied except stall 5.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Gold