POJ 1416 Shredding Company

 1 #include <stdio.h>

 2 #include <string.h>

 3 

 4 int n, ans;

 5 bool rejected;

 6 char path[100], tmp[10], ans_path[100];

 7 

 8 void dfs(int sum, char s[])

 9 {

10     if(sum > n)return;

11     if(s[0] == '\0')

12     {

13         if(sum == ans)rejected = 1;

14         else if(sum > ans && sum <= n)

15         {

16             rejected = 0;

17             ans = sum;

18             strcpy(ans_path, path);

19         }

20         return;

21     }

22     int len = strlen(s);

23     for(int i = 1; i <= len; i++)

24     {

25         int x = s[0] - '0';

26         for(int j = 1; j < i; j++)

27             x = x * 10 + s[j] - '0';

28         int pathlen = strlen(path);

29 

30         sprintf(path, "%s %d", path, x);

31         //               。             ，      。

32         //sprintf(tmp, " %d", x);

33         //strcat(path, tmp);

34 

35         dfs(x+sum, &s[i]);

36         path[pathlen] = '\0';

37     }

38 }

39 

40 int main()

41 {

42     char s[10];

43     while(scanf("%d %s", &n, s) != EOF)

44     {

45         if(n == 0 && s[0] == '0')break;

46         ans = -1;

47         rejected = 0;

48         int len = strlen(s);

49         for(int i = 1; i <= len; i++)

50         {

51             int x = s[0] - '0';

52             for(int j = 1; j < i; j++)

53                 x = x * 10 + s[j] - '0';

54             sprintf(path, "%d", x);

55             dfs(x, &s[i]);

56         }

57         if(ans == -1)

58             printf("error
");

59         else if(rejected)

60             printf("rejected
");

61         else

62             printf("%d %s
", ans, ans_path);

63     }

64     return 0;

65 }