Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- char num[81];
- int len, halflen;
- void process(void);
- int myinc(int pos) {
- int i;
- if(pos>=0) {
- if(num[pos]!='9')
- num[pos]++;
- else {
- num[pos] = '0';
- myinc(pos-1);
- }
- return 0;
- } else {
- for(i=len; i>0;i--) num[i] = num[i-1];
- num[0] = '1';
- len++;
- num[len] = 0;
- halflen = len >> 1;
- return 1;
- }
- }
- void decrease(int a) {
- int can = 0, i, p;
- for(p=halflen; p<len; p++) if(num[p] != '9') break;
- for(i=p+1; i<len; i++) can += num[i] - '0';
- if(can) can--;
- if(can>=a) {
- for(i=len-1; i>=halflen; i--) {
- if(num[i]-'0' > a) {
- num[len-1] = num[i]-a-1;
- if(i != len-1) num[i] = '0';
- myinc(i-1);
- return;
- } else {
- a -= num[i]-'0';
- num[i] = '0';
- }
- }
- } else {
- if(myinc(p-1)) p++;
- for(i=p; i<len; i++) num[i] = '0';
- process();
- }
- }
- void increase(int a) {
- int can = 0, i;
- for(i=halflen; i<len; i++) can += '9' - num[i];
- if(can>=a) {
- for(i=len-1; i>=halflen; i--)
- if('9'-num[i] > a) {
- num[i] += a;
- break;
- } else {
- a -= '9'-num[i];
- num[i] = '9';
- }
- } else {
- myinc(halflen-1);
- for(i=halflen; i<len; i++) num[i] = '0';
- process();
- }
- }
- void process(void) {
- int left = 0, right = 0, i;
- for(i=0; i<halflen; i++) left += num[i]-'0';
- for(i=halflen; i<len; i++) right += num[i]-'0';
- if(left==right) return;
- if(left>right)
- increase(left-right);
- else
- decrease(right-left);
- }
- int main(void) {
- int i;
- char c = '0';
- while(c=='0') scanf("%c", &c);
- for(i=0; c!='\n'; i++) {
- num[i] = c;
- scanf("%c", &c);
- }
- if(i) {
- num[i] = 0;
- len = i;
- halflen = len>>1;
- process();
- printf("%s\n", num);
- } else
- printf("0\n");
- return 0;
- }
Add Comment
Please, Sign In to add comment