뼈대까지 돌아가기
면접 대비시간 제한1초메모리 제한256 MB
N개 주사위의 현재 눈과 목표 K가 주어질 때, 일부 주사위를 한 번 다시 던져 눈의 합이 K 이상이 될 최대 확률을 구하고, 그 확률에 6^N을 곱한 값과 최적 선택을 출력합니다.
문제
전설에 따르면 주사위야말로 진정한 실력을 가릴 수 있는 도구라고 한다. 그중에서도 1부터 6까지의 수가 적힌 정육면체 주사위가 으뜸이라고 전해진다. 정육면체 주사위를 던졌을 때 각 면이 나올 확률은 1/6로 모두 같다. 상헌이는 주사위의 시험을 받게 되었다. 정육면체 주사위 N개를 던져 나온 눈의 합이 K 이상이어야 한다.
그런데 상헌이는 주사위 컨트롤 실력이 아직 부족하므로, 주사위 N개를 던진 다음 마음에 안 드는 주사위를 골라 다시 한 번 던질 기회를 얻었다. 어느 주사위도 던지지 않아도 된다.
상헌이는 고민에 빠졌다. 어떤 주사위를 골라야 모든 눈의 합이 K 이상이 될 확률이 가장 높을까? 상헌이는 실력을 가리기 전에 확률을 계산해 보려고 여러분에게 도움을 청했다.
입력
입력의 첫 줄에는 테스트 케이스의 개수를 뜻하는 정수 T가 주어진다. (1 ≤ T ≤ 1,000)
각 테스트 케이스는 두 줄로 이루어져 있고, 테스트 케이스 사이에 빈 줄은 없다.
각 테스트 케이스의 첫째 줄에는 상헌이가 가진 정육면체 주사위의 개수와 눈의 합의 최소 목표치를 뜻하는 두 정수 N과 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 20, N ≤ K ≤ 6N)
각 테스트 케이스의 둘째 줄에는 N개의 정수 a1, a2, ..., aN이 공백으로 구분되어 주어진다. ai는 i번째 정육면체 주사위를 던져서 나온 눈을 뜻하며, 1 이상 6 이하의 자연수이다.
출력
출력은 각 테스트 케이스마다 두 줄로 이루어진다. 따라서 총 2T개의 줄에 걸쳐 출력해야 한다. 각 테스트 케이스에서 정육면체 주사위를 적절히 골라 다시 던진 뒤 모든 눈의 합이 K 이상이 될 확률의 최댓값을 p라고 하자.
각 테스트 케이스마다 첫째 줄에는 정수 6N × p를 출력한다. 이 값은 32비트 정수에 담기에는 매우 클 수 있다.
각 테스트 케이스마다 둘째 줄에는 어떻게 골라 던져야 위의 확률 p가 나오는지를 뜻하는 N개의 정수 x1, x2, ..., xN을 공백으로 구분하여 출력한다. xi는 i번째 정육면체 주사위를 던져야 하는 경우 1이고 그렇지 않을 경우 0이다. 확률이 p가 되도록 정육면체 주사위를 고를 수 있는 방법이 여러 가지라면 그중 아무 것이나 출력해도 좋다.