만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

주사위 합 조합

면접 대비

시간 제한5초메모리 제한512 MB

요약
주사위 n개로 합 s를 만드는 오름차순 조합을 사전 순으로 모두 출력합니다.
난이도

쉬움10점 중 3점

유형
백트래킹, 재귀
정답자
아직 제출이 없습니다

문제

칼라일 카지노에 새 주사위 게임이 생겼다. 참가자는 각 면에 11부터 mm까지 적힌 주사위 nn개를 굴려서 딜러가 무작위로 고른 합 ss를 정확히 맞춰야 한다. 딜러가 부르는 합마다 그 합이 나오는 주사위 눈의 조합을 모두 구하라.

입력

첫째 줄에 테스트 케이스의 수 cc가 주어진다. 이어지는 cc개의 줄에 각각 세 정수 nn, mm, ss가 공백으로 구분되어 주어진다. nn은 주사위의 개수, mm은 주사위 한 개의 면의 수, ss는 만들어야 하는 합이다.

출력

각 테스트 케이스마다 먼저 Case x:를 한 줄에 출력한다. xx는 11부터 시작하는 테스트 케이스 번호다.

그 다음 줄부터 합이 ss가 되는 주사위 눈의 조합을 한 줄에 하나씩 출력한다. 주사위 nn개를 모두 사용해야 한다. 한 조합은 눈을 쉼표로 구분하고 괄호로 감싸서 적으며, 왼쪽에서 오른쪽으로 읽을 때 작은 값부터 큰 값 순서가 되도록 배열한다. 순서만 다른 조합은 하나만 출력한다. 예를 들어 n=3n = 3일 때 (1,2,3)은 올바르고 (2,3,1), (2,1,3), (3,1,2), (3,2,1), (1,3,2)는 올바르지 않다.

조합이 둘 이상이면 사전순으로 오름차순 정렬해 출력한다. 첫 번째 눈이 작은 조합을 먼저 출력하고, 첫 번째 눈이 같으면 두 번째 눈을 비교하며, 그다음도 같은 방식이다. 합 ss를 만들 수 없으면 Case x: 줄만 출력한다.

제한

  • 2≤n≤62 \le n \le 6
  • 3≤m≤123 \le m \le 12
  • 2≤s≤802 \le s \le 80

예제1

  1. 예제 1

    입력
    1
3 8 12
    예상 출력
    Case 1:
(1,3,8)
(1,4,7)
(1,5,6)
(2,2,8)
(2,3,7)
(2,4,6)
(2,5,5)
(3,3,6)
(3,4,5)
(4,4,4)