시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 431 | 88 | 74 | 25.342% |
건모는 매일 새벽까지 코딩하고 아침 일찍 출근한다. 빠르게 알람을 맞추고 자기 위해 알람을 두 개만 키려고 한다. 하지만, 알람을 듣지 못할 걸 대비해 일어나야 하는 시간까지 가장 많이 울릴 수 있는 알람 두 개를 키려고 한다. 졸린 건모를 위해 켜야 할 알람을 골라 보도록 하자.
건모가 사용하는 알람엔 스누즈 버튼이 있다. 스누즈 버튼이란, 울리고 있는 알람을 끄고 잠시 후 알람을 다시 울리게 하는 버튼이다.
건모는 일어나야 하는 시간까지 모든 알람이 울리자마자 스누즈 버튼을 누른다. 계속 스누즈 버튼을 누르다 보면 동일한 시간에 두 개 알람이 울리는 경우가 생긴다. 이때 두 알람이 하나로 울리며, 둘 중 하나라도 스누즈 버튼을 누르게 되면 두 알람에 대해 각각 스누즈 버튼을 누른 것처럼 동작한다.
예를 들어, 켤 수 있는 알람 리스트가 다음과 같이 주어졌다고 가정해보자. 스누즈 시간 $K$는 스누즈 버튼을 눌렀을 때 알람이 다시 울리기까지 걸리는 시간이다.
알람 번호 | 알람이 사작되는 시각 $T$ | 스누즈 시간 $K$ | 설명 |
---|---|---|---|
1 | 0 | 2 | 시각이 0, 2, 4, 6, $\ldots$일 때 알람이 울린다. |
2 | 5 | 5 | 시각이 5, 10, 15, 20, $\ldots$일 때 알람이 울린다. |
3 | 6 | 3 | 시각이 6, 9, 12, 15, $\ldots$일 때 알람이 울린다. |
4 | 0 | 10000 | 시각이 0, 10000, 20000, $\ldots$일 때 알람이 울린다. |
건모가 일어나야 하는 시각이 $30$이라면, 다음과 같이 알람을 들을 수 있다.
알람 번호 | 알람이 울리는 시각 | 총 울린 횟수 |
---|---|---|
1 | 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 | 16 |
2 | 5, 10, 15, 20, 25 | 5 |
3 | 6, 9, 12 ,15, 18, 21, 24, 27, 30 | 9 |
4 | 0 | 1 |
1번과 3번 알람을 켜게 된다면, 다음과 같이 알람이 스무 번 울린다. 시각 (6, 12, 18, 24, 30)에 울리는 알람은 한 번만 울린 것으로 계산한다.
빨간 점이 있는 위치는 알람이 울리는 시각이다.
다른 알람을 고를 수도 있지만, 같거나 더 많이 울리는 알람을 고를 수 없다.
첫 번째 줄에 두 정수 알람의 개수 $N$, 건모가 일어나야 하는 시각 $D$가 공백으로 구분되어 주어진다. $(2 \le N \le 1\,000$, $1 \le D \le 10^9)$
둘째 줄부터 $N$개 줄의 $i$번째 줄에는 알람이 시작되는 시각 $T_i$와 알람의 스누즈 시간 $K_i$가 공백으로 구분되어 주어진다. $(0 \le T_i \le D$, $1 \le K_i \le 10^9)$
단, 입력으로 주어지는 값은 모두 정수이며 모든 $i$에 대해 $T_i$가 $K_i$의 배수임이 보장된다.
첫 번째 줄에 건모가 켜야 할 알람 번호 두 개를 공백으로 구분하여 오름차순으로 출력한다.
단, 정답이 여러 가지일 경우 사전 순으로 가장 빠른 결과를 출력한다.
두 번째 줄에 알람이 울리는 횟수를 출력한다.
4 30 0 2 5 5 6 3 0 10000
1 3 20
5 80 0 171 33 33 0 37 78 39 14 2
3 5 36
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Beginner Division B번