3689번 - 셔플 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 18 | 11 | 11 | 64.706% |
문제
힙찌리 쇼미충 정주경은 음악 듣는 것을 좋아한다. 주경이는 음악을 들을 때 음악 플레이어의 shuffle 기능을 이용한다. 음악 플레이어는 랜덤으로 순열을 생성하여 플레이리스트의 음악을 재생하고, 모든 음악이 다 재생되면 다시 셔플이 되어 음악이 또 재생이 된다.
주경이는 이제껏 재생이 된 음악 목록을 가지고 있었는데, 이 재생 목록이 처음 음악이 재생될 때부터 완벽하게 기록을 하지 않았다는 것을 알게되었다. 이 기록을 가지고 주경이는 다음 셔플이 어떻게 될지를 알고싶어한다.
플레이 리스트의 음악의 수를 s라 할 때 음악 재생 목록을 길이 s인 구간으로 나눌 수 있는데, 처음과 마지막 구간은 s보다 작게끔 나눌수도 있다. 이때 각 구간의 음악은 겹쳐서는 안 된다.
입력
첫째 줄에는 테스트케이스의 수가 주어진다. 최대 100이다.
그 이후 각 테스트케이스마다 첫째 줄에는 s와 n(1 ≤ s, n ≤ 100 000)이 주어진다. s는 플레이리스트의 곡의 수이고, n은 이제껏 재생된 곡 목록의 곡의 수이다.
둘째 줄에는 n개의 x1, x2, . . . , xn (1 ≤ xi ≤ s) 재생된 음악이 주어진다.
출력
각 테스트 케이스마다
첫째 줄에 다음 셔플이 어떻게 되는 지 경우의 수를 출력한다. 만약 가능한 경우의 수가 없다면 0을 출력한다.
예제 입력 1
4 4 10 3 4 4 1 3 2 1 2 3 4 6 6 6 5 4 3 2 1 3 5 3 3 1 1 1 7 3 5 7 3
예제 출력 1
1 6 0 7
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2008 J번
- 문제를 번역한 사람: jsa3824
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호