23023번 - 소수 카드 게임
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4.5 초 (하단 참고) | 512 MB | 54 | 22 | 17 | 37.778% |
문제
Albert는 친구들과 소수 (prime) 카드 게임을 하기로 했다. 총 m명의 플레이어가 있고, 양의 정수가 하나씩 적혀있는 n장의 카드가 있다. 편의상 카드에 적힌 수를 v[1], v[2], ..., v[n]이라 하자.
먼저 플레이어들에게 카드를 나눠준 후, 각자 점수를 계산하여 승자를 가린다.
n장의 카드는 아래 규칙에 따라 m명의 플레이어에게 나누어져야 한다:
- 각 카드는 반드시 한 명의 플레이어에게 주어진다.
- 각 플레이어는 최소 한 장의 카드를 받는다.
n장의 카드를 모두 분배한 후 아래 규칙에 따라 각자 점수를 계산한다:
- 먼저, 자신이 받은 카드에 적힌 수를 모두 더한다. 이를 S라 하자.
- S에 가장 가까우면서 S가 아닌 소수(prime number)를 P라 하자 (그런 소수가 여럿인 경우 아무 것 하나를 P라 한다).
- 해당 플레이어의 점수는 | S - P | 이다 ('|'는 절대값 기호이다).
예를 들어 n = m = 3이고 카드에 적힌 수가 [1, 2, 3]이라 하자. 이 때, 각 플레이어는 정확히 한 장씩 카드를 받는다.
- 1이 적힌 카드를 받은 플레이어의 점수는 1이다 (1에 가장 가까운 소수는 2이다).
- 2가 적힌 카드를 받은 플레이어의 점수는 1이다 (2에 가장 가까운 (2가 아닌) 소수는 3이다).
- 3이 적힌 카드를 받은 플레이어의 점수느 1이다 (3에 가장 가까운 소수는 2이다).
- 이 예제에서는 모든 플레이어의 점수가 1로 동일하다 (모두가 공동 승자이다).
다른 예로, n = 3, m = 2이고 카드에 적힌 수가 [23, 29, 41]이라 하자. 이 때, 한 플레이어는 카드 한 장을 받고 다른 플레이어는 두 장을 받게 된다. 아래와 같은 세 가지 방법으로 카드를 분배할 수 있다.
- 방법 1: [23] 과 [29, 41]로 분배하는 경우, 23에 가장 가까운 소수는 19이고 (29+41)에 가장 가까운 소수는 71이다. 따라서 두 플레이어의 점수는 각각 4와 1이다.
- 방법 2: [29] 과 [23, 41]로 분배하는 경우, 29에 가장 가까운 소수는 31이고 (23+41)에 가장 가까운 소수는 67이다. 따라서 두 플레이어의 점수는 2로 같다.
- 방법 3: [41] 과 [23, 29]로 분배하는 경우, 41에 가장 가까운 소수는 43이고 (23+29)에 가장 가까운 소수는 53이다. 따라서 두 플레이어의 점수는 각각 2와 1이다.
Albert는 게임의 흥미를 위해 승자의 점수가 최소가 되도록 카드를 나눠주고 싶다. 위에 언급한 두 번째 예제의 경우 방법 1은 승자의 점수가 4이고 방법 2와 3은 승자의 점수가 2가 되므로 정답은 2가 된다. Albert가 달성 할 수 있는 승자의 점수 최소값을 구해보자.
소수 (prime number): 양의 정수 P가 1보다 크고 P의 약수가 1과 P뿐이면 소수이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
첫 줄에 n과 m이 공백으로 구분되어 주어진다.
둘째 줄에 n개의 정수가 (v[1], ..., v[n]) 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 6
- 1 ≤ m ≤ n ≤ 15
- 1 ≤ v[i] ≤ 5,000,000
- v[i]의 총합 <= 5,000,000
예제 입력 1
6 3 3 1 2 3 3 3 23 29 41 3 2 23 29 41 4 4 23 29 31 37 5 2 10 20 30 40 50 5 3 10 20 30 40 50
예제 출력 1
1 4 2 4 1 1
예제 1: 본문에서 다루었다.
예제 2: 추가 설명 없음.
예제 3: 본문에서 다루었다.
예제 4: 추가 설명 없음.
예제 5: 가령 [10, 20, 30, 50]과 [40]을 나눠주면 두 플레이어 모두 1점을 얻게 된다.
예제 6: 가령 [10], [40], 그리고 [20, 30, 50]을 나눠주면 모든 플레이어가 각각 1점을 얻게 된다.
시간 제한
- Java 8: 4 초
- PyPy3: 20 초
- Java 8 (OpenJDK): 4 초
- Java 11: 4 초
- Kotlin (JVM): 4 초
- Java 15: 4 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호