2016年5月31日 星期二

Timus 1165 Subnumber

/*
    題目連結

    黑書的一道苦工題...
    雖然以黑書來說 可能也不是那麼苦功就是

    運用到了不少大數的操作
    不過我不講實作細節了 就講大略的做法

    枚舉 第一個數字的後綴
    把它+1 可以得到類似第二個數字的後綴之類的東西
    拿去匹配 可以得到所有可能是 第二個數字的數字
    接著驗證說 第三 第四...第N個數 是否有接連著出現
    有的話就可以更新答案

    另外 這裡 有大部分的測資 可以用來看看
    到底是有哪些case自己漏掉了
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

struct BigNumber
{
    int num[1000];

    BigNumber(){ memset(num, 0, sizeof(num)); }

    BigNumber(char *c, int cn = -1)
    {
        memset(num, 0, sizeof(num));

        if( cn == -1 ) cn = strlen(c);

        for(int ci = 0; ci < cn; ci++)
            num[ci] = c[cn-1-ci]-'0';
    }

    int len()
    {
        for(int i = 999; i >= 0; i--)
            if( num[i] ) return i;

        return -1;
    }

    void fit(int x)
    {
        for(int i = 999; i > x; i--)
            num[i] = 0;
    }

    void fix()
    {
        for(int i = 0; i < 1000; i++)
        {
            if( num[i] < 0 )
            {
                num[i+1] += num[i]/10-1;
                num[i] = num[i]%10+10;
            }

            if( num[i] >= 10 )
            {
                num[i+1] += num[i]/10;
                num[i] %= 10;
            }
        }
    }

    BigNumber operator+(const int &P)const
    {
        BigNumber R(*this);
        R.num[0] += P;
        R.fix();
        return R;
    }

    bool operator<(const BigNumber &P)const
    {
        for(int i = 999; i >= 0; i--)
            if( num[i] != P.num[i] )
                return num[i] < P.num[i];

        return false;
    }

    void c_str(char *c, int n = -1)
    {
        if( n == -1 ) n = this->len();

        for(int ni = 0; ni <= n; ni++)
            c[ni] = num[n-ni]+'0';

        c[n+1] = '\0';
    }

    BigNumber operator*(const int &p)const
    {
        BigNumber r(*this);

        for(int i = 0; i < 1000; i++) r.num[i] *= p;
        r.fix();

        return r;
    }

    void operator+=(const BigNumber &P)
    {
        for(int i = 0; i < 1000; i++)
            num[i] += P.num[i];

        fix();
    }
};

BigNumber INF;

char A[3000]; int An;

int main()
{
    fill(INF.num, INF.num+1000, 9);
    BigNumber Ans(INF);

    scanf("%s", A);
    An = strlen(A);

    bool flag = false;

    for(int Ai = 0; Ai < An; Ai++)
        if( A[Ai] != '0' ) flag = true;

    if( !flag ) A[0] = '1', A[An] = '0', A[++An] = '\0';

    for(int Ai = 0; Ai < An; Ai++)
    {
        if( A[Ai+1] == '0' ) continue;

        BigNumber X = BigNumber(A, Ai+1);
        BigNumber Y = X+1;
        Y.fit(Ai );

        char c[3000]; int cn;
        Y.c_str(c, Ai); cn = strlen(c);

        for(int Aj = Ai+1; Aj <= An; Aj++)
            if( !strncmp(A+Aj, c, min(An-Aj,cn) ) )
            {
                for(int i = 0; i < cn; i++)
                    A[Aj+i] = c[i];

                BigNumber Z = BigNumber(A+Ai+1, Aj+cn-Ai-1);
                BigNumber P(Z);

                char d[3000];
                Z.c_str(d);

                int Ak = Aj+cn;
                BigNumber val;

                BigNumber N; int cnt = 1;
                if( Z.len() == -1 ) Z = X;
                else Z = Z+(-1);
                int Zn = Z.len();

                if( Z.len() < Ai ) continue;

                while( Ak < An )
                {
                    P = P+1;
                    P.c_str(d);

                    if( strncmp(A+Ak, d, min((int)strlen(d), An-Ak) ) ) goto flag;
                    Ak += strlen(d);
                }

                N.num[0] = 9;

                while( cnt <= Zn )
                {
                    val += N*cnt;

                    swap(N.num[cnt-1], N.num[cnt]);
                    cnt++;
                }

                Z.num[Zn]--;
                Z = Z+1;
                val += Z*cnt;
                val = val+(-Ai);

                if( !flag ) val = val+1;
                if( val < Ans ) Ans = val;

                flag:;

                A[An] = '\0';
            }
    }

    char p[3000];
    Ans.c_str(p);
    puts(p);
}

沒有留言:

張貼留言