시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 113 | 63 | 36 | 50.000% |
Alice와 Bob은 "소수 게임"을 즐겨한다.
소수 게임에서는 두 사람이 먼저 일정한 양의 정수 구간 (interval)을 먼저 고르고, 해당 구간에 속한 모든 정수 각각에 대해 미니 게임을 한 번씩 플레이 한다.
정확한 규칙은 아래와 같다.
예를 들어 N = 8 이라면, Alice가 자신의 처음 차례에 7을 고르면 이긴다.
N = 10이라면 Alice가 자신의 차례에 고를 수 있는 소수는 2, 3, 5, 7 중 하나이다.
따라서 N = 10인 경우, Bob이 최선을 다한다면 Alice가 이길 방법은 없다. (두 사람은 언제나 최선을 다해서 플레이 한다고 가정하자.)
Bob은 A, k가 주어졌을 때 x를 잘 골라서 자신의 승률을 최대화 하기로 했다. 만약 승률을 최대화 하는 x값이 여럿이라면 그 중 가장 작은 x를 찾기로 했다. Bob을 도와주자.
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 줄에 A와 k가 공백으로 구분되어 주어진다.
각 테스트 케이스에 대해 두 개의 정수를 공백으로 구분하여 출력한다.
첫 수는 k번의 게임 중 Bob이 최대 몇 번을 이길 수 있는지 나타내고, 두 번째 수는 이를 위해 Bob이 선택해야하는 x값 중 최소 값을 나타낸다.
5 12 2 12 3 12 4 100 11 1000 15
2 9 2 8 2 7 3 25 4 885