14460번 - 소가 길을 건너간 이유 12 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 287 | 105 | 72 | 33.333% |
문제
이번에는 우리가 존의 농장을 제대로 찾아가긴 했는데, 다른 이유로 계획이 실행되지 못했다. 그의 소 친밀도 이론에 오류가 발견되었기 때문이다.
존의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종이다. 만약 |a−b| ≤ K라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다. 종별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종의 소만 방목할 수 있다. i번 목초지에는 i번 소만 방목할 수 있는 것이다. 소가 길을 건널 때는 자신의 종을 방목하는 반대편의 목초지로 이동하는 것이다.
존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명할 것이다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 목초지의 순서가 뒤죽박죽이어서, a종의 소와 b종의 소가 건너는 길이 겹칠 수도 있다. 존이 목초지 건설에 주의를 기울이지 않은 탓이다. 이때 (a,b)를 "가로지르는 쌍"이라고 하자.
이번에는 횡단보도를 설치하기 전에, 사이가 안 좋으면서 가로지르는 쌍이 몇 개인지 세고 싶다. 존 도와주기 협회장의 임기가 다 끝나가기 때문에 이것이 우리에게 주어진 마지막 임무이다. 마지막으로 존을 도와주자.
입력
첫 줄에 N (1 ≤ N ≤ 100,000)과 K (0 ≤ K < N)가 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.
출력
사이가 안 좋으면서 가로지르는 쌍의 개수를 출력한다.
예제 입력 1
4 1 4 3 2 1 1 4 2 3
예제 출력 1
2
힌트
1과 4, 1과 3이 사이가 안 좋으면서 가로지르는 쌍이다.
출처
Olympiad > USA Computing Olympiad > 2016-2017 Season > USACO 2017 February Contest > Platinum 3번
- 문제를 번역한 사람: jh05013
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호