Dessert

면접 대비

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

요약

1부터 N까지의 수 사이에 '+', '-', '.'(이어붙이기)을 넣어 식의 값이 0이 되도록 만든 뒤, 사전순으로 앞선 최대 20개의 식과 전체 개수를 출력한다.

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

문제

FJ has a new rule about the cows lining up for dinner. Not only must the N (3 ≤ N ≤ 15) cows line up for dinner in order, but they must place a napkin between each pair of cows with a "+", "-", or "." on it. In order to earn their dessert, the cow numbers and the napkins must form a numerical expression that evaluates to 0. The napkin with a "." enables the cows to build bigger numbers. Consider this equation for seven cows:

1 - 2 . 3 - 4 . 5 + 6 . 7

This means 1-23-45+67, which evaluates to 0. You job is to assist the cows in getting dessert. (Note: "... 10 . 11 ...") will use the number 1011 in its calculation.)

입력

One line with a single integer, N

출력

One line of output for each of the first 20 possible expressions -- then a line with a single integer that is the total number of possible answers. Each expression line has the general format of number, space, napkin, space, number, space, napkin, etc. etc. The output order is lexicographic, with "+" coming before "-" coming before ".". If fewer than 20 expressions can be formed, print all of the expressions.

예제1

예제 1

입력

예상 출력

1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 - 3 - 4 + 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7
1 - 2 . 3 + 4 + 5 + 6 + 7
1 - 2 . 3 - 4 . 5 + 6 . 7
6