식 만들기

시간 제한1초메모리 제한128 MB

요약

각 자릿수 범위와 목표값에 대해 자릿수를 순서대로 사용한 완전 괄호 수식 중 목표값이 되는 모든 식을 정해진 순서로 출력한다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 재귀, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

어린이들이 암산을 연습하도록 돕는 새로운 카드 게임을 설계하려고 합니다. 각 카드에는 한 자리 숫자들이 이루는 연속된 범위와 목표 정수 하나가 적혀 있습니다. 플레이어는 카드에 적힌 순서 그대로 이 한 자리 숫자들을 사용하여, 그 값이 목표 정수와 같아지는 식을 만들어야 합니다.

사용할 수 있는 이항 연산자는 덧셈 +, 뺄셈 -, 곱셈 *, 그리고 나머지 연산 %의 네 가지입니다. 게임 설계자는 컴퓨터 과학자여서, 네 번째 연산으로 흔히 예상하는 나눗셈 대신 나머지(모듈로) 연산을 일부러 선택했습니다. 괄호는 계산 순서를 정하기 위해 자유롭게 쓸 수 있습니다.

1, 2, 3, 4, 5, 6, 7, 8 중에서 고른 연속된 숫자 범위(숫자 9는 절대 포함되지 않습니다)와 목표 정수가 주어질 때, 그 숫자들을 순서대로 사용하여 목표 정수를 만드는 모든 식을 찾으세요.

예를 들어 범위가 1..4이고 목표가 10이면 (((1+2)+3)+4) = 10이 하나의 답입니다. 이 외에도 10이 되는 식이 여럿 더 있습니다.

입력

입력은 여러 개의 문제로 이루어집니다. 각 문제는 한 줄에 세 정수 A B C로 주어집니다.

A와 B는 숫자 범위를 나타내며 $1 \le A \le B \le 8$ 을 만족합니다. 사용하는 숫자는 순서대로 A, A+1, …, B입니다.
C는 목표 값입니다.

입력의 끝은 세 개의 0으로 이루어진 줄(0 0 0)이며, 이 줄은 처리하지 않습니다.

출력

각 문제마다 먼저 다음 형식의 줄을 출력합니다.

Problem #n: A..B => C

여기서 n은 1부터 시작하는 문제 번호입니다. 그다음, 목표 값 C와 같아지는 모든 식을 한 줄에 하나씩 출력합니다.

모든 식은 완전히 괄호로 묶여 있습니다. 즉, 각 연산자와 그 두 피연산자를 한 쌍의 괄호가 감쌉니다(한 자리 숫자 하나만으로 이루어진 식은 괄호 없이 씁니다). 유효한 식만 출력하며, 0으로 나머지 연산을 하는 식은 유효하지 않습니다.

계산은 일반적인 정수 규칙을 따릅니다. 나머지 연산 a % b의 결과는 왼쪽 피연산자 a의 부호를 따릅니다(C/C++와 동일). 예를 들어 (1-2)%3은 -1입니다.

식은 다음 순서로 출력합니다.

괄호 모양 기준. 왼쪽에서 오른쪽으로 읽을 때 숫자가 여는 괄호보다 먼저 오므로, (1+(…가 ((1+…보다 앞섭니다.
같은 괄호 모양 안에서는 연산자 기준. 왼쪽에서 오른쪽으로 읽을 때 +가 *보다, *가 -보다, -가 %보다 앞섭니다. 예를 들어 (1+(2+…가 (1+(2*…보다, 그것이 (1*(2+…보다, 그것이 (1*(2*…보다 앞섭니다.

예제1

예제 1

입력

1 4 10
2 2 2
0 0 0

예상 출력

Problem #1: 1..4 => 10
(1+(2+(3+4)))
(1+((2+3)+4))
(1*((2*3)+4))
((1+2)+(3+4))
((1+(2+3))+4)
((1*(2*3))+4)
(((1+2)+3)+4)
(((1*2)*3)+4)
Problem #2: 2..2 => 2
2