• 博客访问： 1140168
• 博文数量： 196
• 博客积分： 4141
• 博客等级： 中将
• 技术积分： 2253
• 用 户 组： 普通用户
• 注册时间： 2009-03-21 20:04

2019年（31）

2016年（1）

2014年（16）

2011年（8）

2010年（25）

2009年（115）

2009-06-24 16:15:11

Increasing Sequences

 Time Limit:1s Memory limit:32M Accepted Submit:26 Total Submit:62

Given a string of digits, insert commas to create a sequence of strictly increasing numbers so as to minimize the magnitude of the last number. For this problem, leading zeros are allowed in front of a number.

Input

Input will consist of multiple test cases. Each case will consist of one line, containing a string of digits of maximum length 80. A line consisting of a single 0 terminates input.

Output

For each instance, output the comma separated strictly increasing sequence, with no spaces between commas or numbers. If there are several such sequences, pick the one which has the largest first value; if there’s a tie, the largest second number, etc.

Sample Input

`34563546352600011000001010`

Sample Output

`3,4,5,635,463,5,260001100,000101`
 ```#include #include struct Node {     int be;     int en; }; int length; char str[100]; int rlen; struct Node node[100]; struct Node stack[100]; struct Node result[100]; int compare(int l1,int e1,int l2,int e2) {     while ((str[l1] == '0' && l1 <= e1) || (str[l2] == '0' && l2 <= e2))     {         if (l1 > e1 && l2 > e2)             return 0;         if ((str[l1] == '0') && (l1 <= e1))             ++l1;         if ((str[l2] == '0') && (l2 <= e2))             ++l2;     }     if ((e1 - l1) != (e2 - l2))         return (e1 - l1) - (e2 - l2);     return strncmp(&str[l1], &str[l2], (e2 - l2 + 1)); } int backtrack(int en, int top) {     int i, j;     int flag;     if (en == -1)     {         flag = 0;         if (rlen == 0)             flag = 1;         else         {             i = rlen;             j = top;             while (i >= 0 && j >= 0)             {                 --j, --i;                 flag = compare(stack[j].be, stack[j].en, result[i].be, result[i].en);                 if (flag == 0)                     continue;                 else                     break;             }         }         if (flag > 0)         {             rlen = top;             for (i = 0; i < rlen; ++i)                 result[i].be = stack[i].be, result[i].en = stack[i].en;         }         return 0;     }     i = en;     while (i >= 0)     {         flag = compare(i, en, stack[top - 1].be, stack[top - 1].en);         if (flag >= 0)             break;         stack[top].be = i;         stack[top].en = en;         backtrack(i - 1, top + 1);         --i;     }     return 0; } int imp() {     int i, j;     node[0].be = 0;     node[0].en = 0;     for (i = 1; i < length; ++i)     {         for (j = i; j >= 0; --j)         {             if (compare(j, i, node[j - 1].be, node[j - 1].en) > 0)             {                 node[i].be = j;                 node[i].en = i;                 break;             }         }     }     rlen = 0;     stack[0].be = node[length - 1].be;     stack[0].en = node[length - 1].en;     backtrack(stack[0].be - 1, 1);     while (str[stack[0].be - 1] == '0' && stack[0].be >= 0)     {         --stack[0].be;         backtrack(stack[0].be - 1, 1);     }          return 0; } int main() {     int i, j;     while(scanf("%s",str))     {         length = strlen(str);         if(length == 1 && str[0] == '0')             break;         imp();         for (i = rlen - 1; i >= 0; --i)         {             for (j = result[i].be; j <= result[i].en; ++j)                 printf("%c", str[j]);             printf("%c", (i == 0 ? '\n' : ','));         }     }     return 0; }```

0