Dessert

문제

---

농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다. N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다. 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.) 1-2.3-4.5+6.7 이와 같은 배치는 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다.

 

입력

---

첫 째 줄에는 소들의 수 N(1 ≤ N ≤ 15)이 입력된다.

 

출력

---

처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다. 순서는 +가 가장 앞서고 -와 . 이 순서대로 뒤따른다. 답이 20개 이하라면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다. 모두 출력한다. 20개를 초과하는 경우 21번째 답부터는 출력하지 않는다. 마지막 줄에는 가능한 답의 총 가지수를 출력한다.

 

예제 입력

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 1 - 2 . 3 - 4 . 5 + 6 . 7 6

 

#include <iostream>
#include <string>

using namespace std;

int num;
char result[200];
char sign[3] ={'+','-','.'};
int tempNumber[200];
char calcu[200];
int count2=0;
bool flag =false;

void makeCa(int dp){

        if(dp == num-1){
                int temp=1;
                int inx =0;
                int sum=0;

                for(int i =2;i<=num;i++) // 2~7까지 돈다. 6개 돈다. 
                {
                        if(result[i-2] =='.'){
                                if(i <10){
                                        temp = temp*10 + i;
                                }else{ //i>10
                                        temp = temp*100 +i;
                                }
                                //temp+=to_string(i);

                                if(i==num){
                                        tempNumber[inx] =temp;
                                        break;
                                }
                                
                        }else{
                                tempNumber[inx] = temp;
                                calcu[inx++] = result[i-2]; 
                                temp=i;                                
                        }

                        if(i==num)
                                tempNumber[inx] = num;
                }

                sum = tempNumber[0];
                for(int i=0;i<inx;i++)
                {
                        if(calcu[i]=='+'){
                                sum +=tempNumber[i+1];
                        }else{
                                sum-=tempNumber[i+1];
                        }
                }
                
                if(sum ==0){
                        
                        if(flag){
                                count2++;
                                return ;
                        }

                        for(int i =0;i<num-1;i++)
                        {       
                                if(i==0)
                                {
                                        cout<<i+1<<" "<<result[i];
                                        continue;
                                }
                                cout<<" "<<i+1<<" "<<result[i];
                                if(i== num-2)
                                        cout<<" "<<i+2;
                        }
                        count2++;
                       
                        if(count2 ==20)
                        {
                                flag =true;
                                cout<<endl;
                                return ;
                        }
                       
                        cout<<endl;
                        return;
                }else return ;
              

        }

    // +,- 6 num=7 
    for(int i =0;i<3;i++)
    {
        result[dp] = sign[i];
        makeCa(dp+1);
   
    }

}

int main(){
    cin>>num;

    makeCa(0);

    cout<<count2<<endl;

}