Informatica Online Judge

  왕 게임 #2 [2386 / 0952]

Time Limit(Test case) : 5500(ms)
Number of users who solved : 4   Total Tried : 4


The Champion of this Problem (C++) : gs17078 - ms / 688byte
My Best Submission (C++) : N/A

[35th 이석현(gs17085)]
Writer ID : [gs17085]

Background

석현이는 35기 학생이라면 누구나 그 이름을 알 정도로 인기가 매우 많은 "인싸"이다.
오늘도 할 짓이 없어 심심해하는 친구들을 위해 석현이는 새로운 놀이를 개발해냈다.
이른바 "왕 게임"이라 불리는 이 놀이는 다음과 같이 진행된다 :
1. 우선 N명의 학생들이 원형으로 배치된 N개의 의자에 반시계방향으로 차례차례 앉는다.
2. 석현이가 1번 의자에 앉은 학생의 뒤에 서서 게임을 시작한다.
3. 석현이는 매 순간순간 두 "행동" 중 하나를 골라 시행한다:
- "포상" : 원 둘레를 반 시계방향(1->2->3->..)으로 돌면서 만나는 k명의 학생에게 몇 개의 사탕을 준다. 모두에게 똑같은 개수를 주는 것은 재미없으므로,
l개, l+1개,, 이렇게 이전 학생에게 주었던 사탕에서 1개씩 더 올려서 준다. 마지막 학생에게 사탕을 준 후에는 그 바로 다음 자리에서 정지한다.

- "제거" : 원 둘레를 반 시계방향으로 돌면서, 현재 있는 위치로부터 정확히 k번째 뒷쪽 자리에 앉아있는 학생을 "퇴출"하며,
이때 "대장"은 학생을 "퇴출"할때마다 갖고 있는 메모지에 그 학생이 갖고 있던 사탕의 개수를 체크한다..
(이 학생의 자리는 없던 취급한다. 즉 1 2 3번 학생이 차례차례 앉아있었고, 만약 2번 학생이 "퇴출"당한다면, 1번 학생 바로
다음이 3번 학생이 된다. 그리고 이 상황에서 1번 학생부터 "포상"을 2번 반복하면, 1번 학생과 3번 학생이 "포상"을 받게 되는 것이다.),
이 활동을 l번 반복한다. 학생을 "퇴출"한 다음에는 그 바로 다음 자리부터 다시 수를 세서, 똑같이 k번째 뒷쪽 자리에 앉아있는 학생을 퇴출한다.
마지막 "제거"가 끝난 후에는 그 바로 다음 자리에서 정지한다.

N명의 학생들이 이 놀이를 한다고 할 때, 석현이가 할 행동들이 주어진다면 이 놀이가 끝나고 난 후 석현이가 최종적으로 체크한
사탕의 수를 구하는 프로그램을 작성하시오.
단, 수가 너무 커질 수 있으니 이 수를 10억 7로 나눈 나머지를 출력하시오.

Input

첫 번째 줄에 학생의 수 N과 석현이가 할 행동의 개수 M이 주어진다.
그 다음 줄부터 M줄에 걸쳐 석현이가 할 행동이 3개의 정수열로 주어진다:
이 줄이 1로 시작한다면 이는 "포상"이며, 그 다음 2개의 정수는 사탕을 줄 학생의 수 k와 줄 사탕의 개수 l이다.
이 줄이 2로 시작한다면 이는 "제거"이며, 그 다음 2개의 정수는 "퇴출"될 학생의 순서 k와 그 행동을 반복할 횟수 u이다.

[입력값의 정의역]
1<= N <= 80000, 1<= M <= 80000
1 <= l <= 300, 1<= sigma(u) <= N-1

[sub-task info]
#1 : 1<=N<=8000, 1<=M<=8000
#2 : 1<= N <= 80000, 1<= M <= 80000

Output

메모지에 최종적으로 쓰여있게 될 수를 10억 7로 나눈 나머지를 출력한다.

IO Example

입력
4 4
1 2 3
2 3 2
1 4 2
2 3 1

출력
13

설명 : 다음 그림을 참고















Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]