USACO/Zero Sum.c at master · sunheehnus/USACO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
ID: sunheco1
LANG: C
TASK: zerosum
*/
#include<stdio.h>

char step[100]={'1'};

char out[20][100];

int target,cur,tot;

int Yes()
{
	char compute[100],*tem=compute;
	int i,j,result,temp;
	for(i=0,j=0;step[i]!='\0';i++)
	{
		if(step[i]==' ')
			continue;
		compute[j]=step[i];
		j++;
	}
	compute[j]='\0';
	result=0;
	while(*tem>='1'&&*tem<='9')
	{
		result=result*10+*tem-'0';
		tem++;
	}
	if(*tem=='\0')
		return 0;
	while(*tem!='\0')
	{
		if(*tem=='+')
		{
			tem++;
			temp=0;
			while(*tem>='1'&&*tem<='9')
			{
				temp=10*temp+*tem-'0';
				tem++;
			}
			result+=temp;
		}
		else if(*tem=='-')
		{
			tem++;
			temp=0;
			while(*tem>='1'&&*tem<='9')
			{
				temp=10*temp+*tem-'0';
				tem++;
			}
			result-=temp;
		}
	}
	return !result;
}

void Find(int now)
{
	int i;
	if(now>target)
	{
		step[cur+1]='\0';
		if(Yes())
		{
			for(i=0;step[i]!='\0';i++)
				out[tot][i]=step[i];
			out[tot++][i]='\0';
		}
		return;
	}
	cur+=2;
	step[cur]=now+'0';
	step[cur-1]=' ';
	Find(now+1);
	step[cur-1]='+';
	Find(now+1);
	step[cur-1]='-';
	Find(now+1);
	cur-=2;
	return;
}

int main()
{
	int i;
	FILE *fin  = fopen ("zerosum.in", "r");
    FILE *fout = fopen ("zerosum.out", "w");
	fscanf(fin,"%d",&target);
	Find(2);
	for(i=0;i<tot;i++)
	{
		fprintf(fout,"%s\n",&out[i][0]);
	}
	return 0;
}