시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 809 | 155 | 114 | 24.411% |
전설에 따르면 주사위야말로 진정한 실력을 판가름할 수 있는 도구라고 한다. 그 중 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가 되게 정육면체 주사위를 선택할 수 있는 방법이 다양하다면 그중 아무 것이나 출력해도 좋다.
N ≤ 3을 만족한다.
문제 입력에서 주어진 조건 외에 추가적인 조건이 없다.
3 1 5 3 2 10 6 1 3 8 2 5 4
2 1 18 0 1 216 1 0 0
첫 번째 테스트 케이스에서는 주사위를 다시 굴리지 않으면 눈의 합이 5 이상이 될 확률이 0이며, 굴리면 1/3이다.
두 번째 테스트 케이스에서는 두 번째 주사위만 굴리는 것이 최적이며 이 때의 확률은 1/2이다.
세 번째 테스트 케이스에서는 이미 눈의 합이 11이다. 첫 번째 주사위를 굴린 결과와 상관없이 눈의 합이 8 이상이므로 확률은 1이다.
University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Beginner Div. G번
University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Advanced Div. B번
University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Intermediate Div. D번