2924번 - 천재 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 242 | 74 | 65 | 40.625% |
문제
준규는 천재다. 하지만 준규의 발명품은 용도가 좀 애매하다. 준규의 최신 발명품인 'Shuffle-o-matic 3175' 역시 좀 애매하다. Shuffle-o-matic은 아주 특별한 방식으로 사용된다. 먼저 1부터 N까지의 수가 적힌 N개의 카드를 이 기계에 위에 놓는다. 그 다음 셔플 수열을 입력하고 작동 버튼을 누르면, 기계가 자동으로 카드의 숫자를 읽어서 그 수열을 테입에 출력한다. 그 후 기계는 셔플 수열대로 카드를 섞은 후 카드의 숫자를 읽어 테입의 다음 줄에 출력한다. 같은 방식으로 한 번 더 셔플 수열대로 카드를 섞고 다시 카드의 수를 테입의 다음 줄에 출력한다. 테입이 다 떨어질 때 까지 이 과정을 반복한다.
준규는 자신의 발명품을 테스트 해 본 후 좀 쉬기로 했다. 그러다 출력 테입의 한 조각을 발견했다. 그리고 모든 줄은 앞에서부터 C개의 수와 뒤에서부터 D개의 수가 지워져 있었다.
준규는 섞기 전의 수열을 1번째 수열이라고 했을때, A번째 수열에서 B번째 수열까지의 수열 중 맨 처음 섞기 전의 순서와 적힌 부분이 모두 일치하는 수열이 몇 개인지 궁금해졌다. 이를 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 정수 N, A, B, C, D (1 ≤ N ≤ 500 000, A ≤ B ≤ 10^12, 0 ≤ C, D ≤ N, C + D < N)가 차례로 주어진다.
둘째 줄에는 셔플 수열이 주어진다. 이 수열에는 1부터 N까지의 수가 한 번씩 등장한다. 만약 수열의 k번째 숫자가 x라면, 이는 카드를 섞을 때 k번째 수를 x번째로 옮긴다는 의미이다.
출력
준규가 찾는 수열의 개수를 출력한다.
예제 입력 1
4 1 5 0 1 1 3 4 2
예제 출력 1
2
예제 입력 2
7 3 8 1 2 2 3 1 6 4 7 5
예제 출력 2
0
예제 입력 3
6 2 11 3 0 6 3 5 4 2 1
예제 출력 3
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호