17634번 - 이상한 기계 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 268 | 67 | 53 | 28.495% |
문제
고고학자들은 고대 문명이 남긴 이상한 기계를 발견하였다. 이 기계는 두 정수 x와 y를 출력하는 두 부분이 있다.
이 기계를 조사해보고, 고고학자들은 이 기계가 과거의 어느 시점부터 시작하여 시점 t에 대한 정보를 출력 하는 특별한 시계라는 결론을 내렸다. 시점 T에서 첫 번째 출력 부분에서는 정수 x = ((t + ⌊t/B⌋ ) mod A)를 출력하고, 두번째 출력 부분에서는 정수 y = (t mod B)를 출력한다. (⌊x⌋는 x 이하이면서 가장 큰 정수를 나타낸다.)
분석을 해 보니 이 기계가 항상 동작하는 것은 아니며, n개의 연속된 구간 [li, ri]에서만 동작하는 것을 알게 되었다. 향후 연구를 위해서, 고고학자들은 당신에게 이 기계가 출력하는 순서쌍 (x, y) 중 서로 다른 것이 모두 몇 개인지를 알아내는 프로그램을 작성하도록 부탁했다.
두 순서쌍 (x1, y1)와 (x2, y2)는 만약 x1 ≠ x2이거나 y1 ≠ y2이라면 서로 다르다.
입력
첫 줄에는 세 정수 n, A, B가 주어진다. (1 ≤ n ≤ 106; 1 ≤ A, B ≤ 1018).
다음 n줄의 각각에는 두 정수 li와 ri가 주어지는데, 이 기계가 동작하는 구간 [li, ri]의 시작 시점과 종료 시점을 나타낸다. (0 ≤ li ≤ ri ≤ 1018 , ri < li+1).
출력
이 기계가 동작하는 동안 출력하는 서로 다른 순서쌍 (x, y)의 수를 출력한다.
예제 입력 1
3 3 3 4 4 7 9 17 18
예제 출력 1
4
예제 입력 2
3 5 10 1 20 50 68 89 98
예제 출력 2
31
예제 입력 3
2 16 13 2 5 18 18
예제 출력 3
5
힌트
첫 번째 테스트에서, 이 기계는 시점 4에서 (2, 1)을, 시점 7에서 (0, 1)을, 시점 8에서 (1, 2)를, 시점 9 에서 (0, 0)를, 시점 17에서 (1, 2)를, 시점 18에서 (0, 0)를 출력한다. 따라서 서로 다른 네 개의 순서쌍 (0, 0),(0, 1),(1, 2),(2, 1)을 출력한다.
출처
Olympiad > Asia-Pacific Informatics Olympiad > APIO 2019 A번
- 데이터를 추가한 사람: klimmek55
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호