Ideone.com

download

#include <cstdio>
#include <cstring>
 
char X[1005], Y[1005], Z[505], A[505];
 
int main() {
    int cases;
    scanf("%d", &cases);
    while(cases-- > 0) {
        scanf("%s", X);
        int X_right_end = strlen(X);
        int X_pivot_left = 0;
        int X_pivot_right = 2;
        if(X_right_end % 2 != 0) {
            X_pivot_right = 1;
        }
        int Z_pivot_right = 2;
        int Z_pivot_left = 1;
        int Y_pivot_left = -1;
        int Y_pivot_right = -1;
        int A_right_end = 1;
 
        for(int i = 0; i < X_right_end; ++i) {
            X[i] -= '0';
        }
        for(int i = 0; i < 505; ++i) {
            Z[i] = 0;
        }
 
        do {
            for(int k = 9; k >= 0; --k) {
                Z[Z_pivot_right - 1] = k;
                int carry_num = 0, i, j;
                Y_pivot_right = X_pivot_right;
                for(i = Z_pivot_right - 1, j = Y_pivot_right - 1; i >= Z_pivot_left; --i, --j) {
                    int mul = Z[i] * k + carry_num;
                    carry_num = mul / 10;
                    Y[j] = mul % 10;
                }
                if(carry_num != 0) {
                    if(j < 0 || j < X_pivot_left) {
                        continue;
                    } else if(j >= X_pivot_left) {
                        Y[j] = carry_num;
                        Y_pivot_left = j;
                        for(int zero = X_pivot_left; zero < Y_pivot_left; ++zero) {
                            Y[zero] = 0;
                        }
                    }
                } else if(carry_num == 0) {
                    if(j < X_pivot_left - 1) {
                        continue;
                    } else if(j >= X_pivot_left - 1) {
                        Y_pivot_left = j + 1;
                        for(int zero = X_pivot_left; zero < Y_pivot_left; ++zero) {
                            Y[zero] = 0;
                        }
                    }
                }
                bool X_bigger_than_Y = true;
                for(int i = X_pivot_left, j = X_pivot_left; i < X_pivot_right; ++i, ++j) {
                    if(X[i] < Y[j]) {
                        X_bigger_than_Y = false;
                        break;
                    } else if(X[i] > Y[j]) {
                        break;
                    }
                }
                if(X_bigger_than_Y) {
                    for(int i = X_pivot_right - 1; i >= X_pivot_left; --i) {
                        X[i] -= Y[i];
                        if(X[i] < 0) {
                            X[i] += 10;
                            X[i - 1] -= 1;
                        }
                    }
                    X_pivot_right += 2;
                    Z[Z_pivot_right - 1] += k;
                    int i, carry_num = 0;
                    for(i = Z_pivot_right - 1; i >= Z_pivot_left; --i) {
                        if(Z[i] >= 10) {
                            Z[i] -= 10;
                            Z[i - 1] += 1;
                            carry_num = 1;
                        } else {
                            carry_num = 0;
                        }
                    }
                    if(carry_num != 0) {
                        Z_pivot_left -= 1;
                    }
                    Z[Z_pivot_right] = 0;
                    Z_pivot_right += 1;
                    while(X_pivot_left < X_pivot_right && 
                        (X_pivot_right - X_pivot_left) > (Z_pivot_right - Z_pivot_left)) {
                        if(X[X_pivot_left] == 0) {
                            ++X_pivot_left;
                        } else {
                            break;
                        }
                    }
                    A[A_right_end - 1] = (char)(k + '0');
                    A_right_end += 1;
                    break;
                } else {
                    if(k == 0) {
                        X_pivot_right += 2;
                        Z[Z_pivot_right - 1] += k;
                        int i, carry_num = 0;
                        for(i = Z_pivot_right - 1; i >= Z_pivot_left; --i) {
                            if(Z[i] >= 10) {
                                Z[i] -= 10;
                                Z[i - 1] += 1;
                                carry_num = 1;
                            } else {
                                carry_num = 0;
                            }
                        }
                        if(carry_num != 0) {
                            Z_pivot_left -= 1;
                        }
                        Z[Z_pivot_right] = 0;
                        Z_pivot_right += 1;
                        while(X_pivot_left < X_pivot_right && 
                            (X_pivot_right - X_pivot_left) > (Z_pivot_right - Z_pivot_left)) {
                            if(X[X_pivot_left] == 0) {
                                ++X_pivot_left;
                            } else {
                                break;
                            }
                        }
                        A[A_right_end - 1] = (char)(k + '0');
                        A_right_end += 1;
                        break;
                    }
                }
            }
        } while(X_pivot_right <= X_right_end);
 
        A[A_right_end - 1] = 0;
        puts(A);
 
        if(cases > 0) {
            puts("");
        }
    }
}

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CgpjaGFyIFhbMTAwNV0sIFlbMTAwNV0sIFpbNTA1XSwgQVs1MDVdOwoKaW50IG1haW4oKSB7CiAgICBpbnQgY2FzZXM7CiAgICBzY2FuZigiJWQiLCAmY2FzZXMpOwogICAgd2hpbGUoY2FzZXMtLSA+IDApIHsKICAgICAgICBzY2FuZigiJXMiLCBYKTsKICAgICAgICBpbnQgWF9yaWdodF9lbmQgPSBzdHJsZW4oWCk7CiAgICAgICAgaW50IFhfcGl2b3RfbGVmdCA9IDA7CiAgICAgICAgaW50IFhfcGl2b3RfcmlnaHQgPSAyOwogICAgICAgIGlmKFhfcmlnaHRfZW5kICUgMiAhPSAwKSB7CiAgICAgICAgICAgIFhfcGl2b3RfcmlnaHQgPSAxOwogICAgICAgIH0KICAgICAgICBpbnQgWl9waXZvdF9yaWdodCA9IDI7CiAgICAgICAgaW50IFpfcGl2b3RfbGVmdCA9IDE7CiAgICAgICAgaW50IFlfcGl2b3RfbGVmdCA9IC0xOwogICAgICAgIGludCBZX3Bpdm90X3JpZ2h0ID0gLTE7CiAgICAgICAgaW50IEFfcmlnaHRfZW5kID0gMTsKCiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IFhfcmlnaHRfZW5kOyArK2kpIHsKICAgICAgICAgICAgWFtpXSAtPSAnMCc7CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCA1MDU7ICsraSkgewogICAgICAgICAgICBaW2ldID0gMDsKICAgICAgICB9CgogICAgICAgIGRvIHsKICAgICAgICAgICAgZm9yKGludCBrID0gOTsgayA+PSAwOyAtLWspIHsKICAgICAgICAgICAgICAgIFpbWl9waXZvdF9yaWdodCAtIDFdID0gazsKICAgICAgICAgICAgICAgIGludCBjYXJyeV9udW0gPSAwLCBpLCBqOwogICAgICAgICAgICAgICAgWV9waXZvdF9yaWdodCA9IFhfcGl2b3RfcmlnaHQ7CiAgICAgICAgICAgICAgICBmb3IoaSA9IFpfcGl2b3RfcmlnaHQgLSAxLCBqID0gWV9waXZvdF9yaWdodCAtIDE7IGkgPj0gWl9waXZvdF9sZWZ0OyAtLWksIC0taikgewogICAgICAgICAgICAgICAgICAgIGludCBtdWwgPSBaW2ldICogayArIGNhcnJ5X251bTsKICAgICAgICAgICAgICAgICAgICBjYXJyeV9udW0gPSBtdWwgLyAxMDsKICAgICAgICAgICAgICAgICAgICBZW2pdID0gbXVsICUgMTA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZihjYXJyeV9udW0gIT0gMCkgewogICAgICAgICAgICAgICAgICAgIGlmKGogPCAwIHx8IGogPCBYX3Bpdm90X2xlZnQpIHsKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgfSBlbHNlIGlmKGogPj0gWF9waXZvdF9sZWZ0KSB7CiAgICAgICAgICAgICAgICAgICAgICAgIFlbal0gPSBjYXJyeV9udW07CiAgICAgICAgICAgICAgICAgICAgICAgIFlfcGl2b3RfbGVmdCA9IGo7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvcihpbnQgemVybyA9IFhfcGl2b3RfbGVmdDsgemVybyA8IFlfcGl2b3RfbGVmdDsgKyt6ZXJvKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBZW3plcm9dID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0gZWxzZSBpZihjYXJyeV9udW0gPT0gMCkgewogICAgICAgICAgICAgICAgICAgIGlmKGogPCBYX3Bpdm90X2xlZnQgLSAxKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIH0gZWxzZSBpZihqID49IFhfcGl2b3RfbGVmdCAtIDEpIHsKICAgICAgICAgICAgICAgICAgICAgICAgWV9waXZvdF9sZWZ0ID0gaiArIDE7CiAgICAgICAgICAgICAgICAgICAgICAgIGZvcihpbnQgemVybyA9IFhfcGl2b3RfbGVmdDsgemVybyA8IFlfcGl2b3RfbGVmdDsgKyt6ZXJvKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBZW3plcm9dID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGJvb2wgWF9iaWdnZXJfdGhhbl9ZID0gdHJ1ZTsKICAgICAgICAgICAgICAgIGZvcihpbnQgaSA9IFhfcGl2b3RfbGVmdCwgaiA9IFhfcGl2b3RfbGVmdDsgaSA8IFhfcGl2b3RfcmlnaHQ7ICsraSwgKytqKSB7CiAgICAgICAgICAgICAgICAgICAgaWYoWFtpXSA8IFlbal0pIHsKICAgICAgICAgICAgICAgICAgICAgICAgWF9iaWdnZXJfdGhhbl9ZID0gZmFsc2U7CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIH0gZWxzZSBpZihYW2ldID4gWVtqXSkgewogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZihYX2JpZ2dlcl90aGFuX1kpIHsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IGkgPSBYX3Bpdm90X3JpZ2h0IC0gMTsgaSA+PSBYX3Bpdm90X2xlZnQ7IC0taSkgewogICAgICAgICAgICAgICAgICAgICAgICBYW2ldIC09IFlbaV07CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKFhbaV0gPCAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBYW2ldICs9IDEwOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgWFtpIC0gMV0gLT0gMTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBYX3Bpdm90X3JpZ2h0ICs9IDI7CiAgICAgICAgICAgICAgICAgICAgWltaX3Bpdm90X3JpZ2h0IC0gMV0gKz0gazsKICAgICAgICAgICAgICAgICAgICBpbnQgaSwgY2FycnlfbnVtID0gMDsKICAgICAgICAgICAgICAgICAgICBmb3IoaSA9IFpfcGl2b3RfcmlnaHQgLSAxOyBpID49IFpfcGl2b3RfbGVmdDsgLS1pKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKFpbaV0gPj0gMTApIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIFpbaV0gLT0gMTA7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBaW2kgLSAxXSArPSAxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgY2FycnlfbnVtID0gMTsKICAgICAgICAgICAgICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNhcnJ5X251bSA9IDA7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYoY2FycnlfbnVtICE9IDApIHsKICAgICAgICAgICAgICAgICAgICAgICAgWl9waXZvdF9sZWZ0IC09IDE7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIFpbWl9waXZvdF9yaWdodF0gPSAwOwogICAgICAgICAgICAgICAgICAgIFpfcGl2b3RfcmlnaHQgKz0gMTsKICAgICAgICAgICAgICAgICAgICB3aGlsZShYX3Bpdm90X2xlZnQgPCBYX3Bpdm90X3JpZ2h0ICYmIAogICAgICAgICAgICAgICAgICAgICAgICAoWF9waXZvdF9yaWdodCAtIFhfcGl2b3RfbGVmdCkgPiAoWl9waXZvdF9yaWdodCAtIFpfcGl2b3RfbGVmdCkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYoWFtYX3Bpdm90X2xlZnRdID09IDApIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICsrWF9waXZvdF9sZWZ0OwogICAgICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgQVtBX3JpZ2h0X2VuZCAtIDFdID0gKGNoYXIpKGsgKyAnMCcpOwogICAgICAgICAgICAgICAgICAgIEFfcmlnaHRfZW5kICs9IDE7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIGlmKGsgPT0gMCkgewogICAgICAgICAgICAgICAgICAgICAgICBYX3Bpdm90X3JpZ2h0ICs9IDI7CiAgICAgICAgICAgICAgICAgICAgICAgIFpbWl9waXZvdF9yaWdodCAtIDFdICs9IGs7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBpLCBjYXJyeV9udW0gPSAwOwogICAgICAgICAgICAgICAgICAgICAgICBmb3IoaSA9IFpfcGl2b3RfcmlnaHQgLSAxOyBpID49IFpfcGl2b3RfbGVmdDsgLS1pKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZihaW2ldID49IDEwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgWltpXSAtPSAxMDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBaW2kgLSAxXSArPSAxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNhcnJ5X251bSA9IDE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNhcnJ5X251bSA9IDA7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgaWYoY2FycnlfbnVtICE9IDApIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIFpfcGl2b3RfbGVmdCAtPSAxOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIFpbWl9waXZvdF9yaWdodF0gPSAwOwogICAgICAgICAgICAgICAgICAgICAgICBaX3Bpdm90X3JpZ2h0ICs9IDE7CiAgICAgICAgICAgICAgICAgICAgICAgIHdoaWxlKFhfcGl2b3RfbGVmdCA8IFhfcGl2b3RfcmlnaHQgJiYgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAoWF9waXZvdF9yaWdodCAtIFhfcGl2b3RfbGVmdCkgPiAoWl9waXZvdF9yaWdodCAtIFpfcGl2b3RfbGVmdCkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmKFhbWF9waXZvdF9sZWZ0XSA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKytYX3Bpdm90X2xlZnQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIEFbQV9yaWdodF9lbmQgLSAxXSA9IChjaGFyKShrICsgJzAnKTsKICAgICAgICAgICAgICAgICAgICAgICAgQV9yaWdodF9lbmQgKz0gMTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfSB3aGlsZShYX3Bpdm90X3JpZ2h0IDw9IFhfcmlnaHRfZW5kKTsKCiAgICAgICAgQVtBX3JpZ2h0X2VuZCAtIDFdID0gMDsKICAgICAgICBwdXRzKEEpOwoKICAgICAgICBpZihjYXNlcyA+IDApIHsKICAgICAgICAgICAgcHV0cygiIik7CiAgICAgICAgfQogICAgfQp9

Runtime error #stdin #stdout 0.02s 2856KB

stdin

4294967296

stdout

https://ideone.com/3aOhWJ

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language