posts - 74,  comments - 33,  trackbacks - 0
 
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 1651 Accepted: 585

Description

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.)

Input

One line with a single integer, N

Output

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.

Sample Input

7

Sample Output

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
一个超恶心的题目:
啥也不说了,就是恶心。
void DFS(int now,int sign,int sum){
    
if(sum>10000000)return ;
    
if(now==n){
        
if(sum1[n]!=0)return ;
        all
++;
        
if(all>20)return ;
        
for(int i=1;i<n;i++)
            printf(
"%d %c ",i,flag[i]);
        printf(
"%d\n",n);
        
return ;    
    }

    
int i,j,t;
    flag[sign]
='+';
    sum1[sign
+1]=sum+now+1;
    DFS(now
+1,sign+1,sum1[sign+1]);
    flag[sign]
='-';
    sum1[sign
+1]=sum-now-1;
    DFS(now
+1,sign+1,sum1[sign+1]);
    flag[sign]
='.';
    
for(i=sign-1;i>=1;i--)
        
if(flag[i]!='.')break;
    
if(now>8)t=100*(sum1[sign]-sum1[i])+sum1[i];
    
else t=10*(sum1[sign]-sum1[i])+sum1[i];
    
if(flag[i]=='+')sum1[sign+1]=t+now+1;
    
else sum1[sign+1]=t-now-1;
    DFS(now
+1,sign+1,sum1[sign+1]);
    
return ;
}
posted on 2009-02-23 21:20 KNIGHT 阅读(104) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年1月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜