소수 카드 게임
시간 제한4.5초메모리 제한512 MB
n개의 카드를 m명에게 적어도 한 장씩 나누어 주고, 각 묶음 합에서 그 합과 다른 가장 가까운 소수까지의 거리 중 최댓값을 최소로 만드는 문제입니다.
문제
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뿐이면 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