31531번 - 공들의 리듬게임 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 116 | 44 | 36 | 41.379% |
문제
무한히 긴 직선 위에 공 $N$개가 놓여 있다. 각 공은 정지해 있거나, 왼쪽으로 움직이거나, 오른쪽으로 움직인다. 초기 공들의 위치는 모두 다르다.
리듬게임 장인인 현제는 공들이 계속 움직이다가 다른 공과 충돌하는 모습을 보며 일정한 리듬이 있다고 생각하다 게임을 만들었다. 처음에는 $0$점으로 시작하며, 공들끼리 충돌할 때 다음과 같이 점수를 얻고 공들의 상태가 바뀐다.
- 왼쪽으로 움직이던 공과 오른쪽으로 움직이던 공이 충돌하면, 두 공 모두 진행 방향이 반대로 바뀌게 된다. 이 경우 $1$점을 얻는다.
- 움직이던 공과 정지해 있던 공이 충돌하면, 움직이던 공은 그 자리에 정지하며, 정지해 있던 공은 움직이던 공이 이동하던 방향으로 움직인다. 이 경우 $2$점을 얻는다.
- 왼쪽으로 움직이던 공과 정지해 있던 공, 오른쪽으로 움직이던 공이 동시에 충돌하면, 왼쪽으로 움직이던 공과 오른쪽으로 움직이던 공은 모두 진행 방향이 반대로 바뀌게 되며, 정지해 있던 공은 계속 정지해 있는다. 이 경우 $5$점을 얻는다.
한 번의 충돌이 여러 조건을 만족할 경우, 점수가 가장 높은 조건만 적용된다.
공이 더 이상 충돌하지 않을 만큼의 시간이 지났을 때 총점을 구해보자. 여기서 총점은 얻은 점수의 합이다.
움직이는 공들은 모두 $1$의 속력을 유지하며, 충돌 이후 새로 움직이는 공의 속력도 마찬가지이다. 공은 길이나 부피가 무시할 만큼 작아 없다고 가정하며, 충돌을 제외하고는 공의 운동 방향, 속력 등의 상태가 유지된다.
입력
첫 번째 줄에 공의 개수 $N$이 주어진다. $(1\le N\le 500\,000)$
다음 $N$줄에 걸쳐 각 공의 위치와 초기 상태를 나타내는 정수 $a_i$와 $d_i$가 공백으로 구분되어 주어진다. $(\lvert a_i\rvert\le 10^{18};$ $\lvert d_i\rvert\le 1)$
$a_i$는 직선 위의 공의 좌표이며, $d_i$에 따라 초기 상태는 다음과 같다.
- $d_i=0$: 정지해 있다.
- $d_i=-1$: 왼쪽으로 움직인다.
- $d_i=1$: 오른쪽으로 움직인다.
모든 공들의 위치는 다르다.
출력
공이 더 이상 충돌하지 않을 만큼의 시간이 지났을 때 총점을 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | 모든 $d_i = 0$ |
| 2 | 50 | 모든 $\lvert d_i\rvert = 1$ |
| 3 | 50 | $N\le 50;$ 모든 $\lvert a_i\rvert \le 1\,000$ |
| 4 | 75 | 추가적인 제한 조건 없음 |
예제 입력 1
2 -4 -1 5 1
예제 출력 1
0
두 공은 영원히 충돌하지 않으므로 총점은 $0$점이다.
예제 입력 2
2 -4 1 5 -1
예제 출력 2
1
두 공은 $4.5$초 뒤 $0.5$의 위치에서 첫 번째 유형의 충돌을 하고 더 이상 충돌하지 않으므로 총점은 $1$점이다.
예제 입력 3
3 -1 1 0 0 1 -1
예제 출력 3
5
세 공은 $1$초 뒤 $0$의 위치에서 세 번째 유형의 충돌을 하고 더 이상 충돌하지 않으므로 총점은 $5$점이다.
예제 입력 4
4 4 1 5 0 6 0 8 -1
예제 출력 4
9
해당 예제는 다음과 같은 과정을 통해 일어난다.
이후 공들이 더 이상 충돌하지 않으므로 총점은 $9$점이다.
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring 연습 세션 PC번
- 문제를 만든 사람: alex04, kidw0124
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: devluyten, finimage, lighter, rachel2003, sshs29hanul, tikiliki0417, tlsdydaud1, utilforever, w8385, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호