Cod sursa(job #1435860)

Utilizator EpictetStamatin Cristian Epictet Data 14 mai 2015 18:28:43
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <string>
#include <cstring>
#define LL long long
#define BASE 100000000
using namespace std;
ifstream fin ("sarpe.in");
ofstream fout ("sarpe.out");
LL N, V[10000], S_1[10000], S_2[10000];
string S;

void Read_Data()
{
    fin >> S;
    for (LL i = S.size() - 1; i >= 0;)
    {
        LL nr = 0, p = 1;
        while (p < BASE && i >= 0)
        {
            nr = nr + (p * (S[i] - '0'));
            p *= 10;
            i--;
        }
        V[++V[0]] = nr;
    }
}

void Scade(LL A[], LL B)
{
    LL i, t = 0;
    A[1] -= B;
    for (i = 1; i <= A[0]; i++)
    {
        A[i] -= t;
        A[i] += (t = (A[i] < 0)) * BASE;
    }
    while (A[0] >= 1 && !A[A[0]]) A[0]--;
}

void Mul_Nr_Mare_Nr_Mic(LL A[], LL B)
{
    LL i, t = 0;
    for (i = 1; i <= A[0] || t; i++, t /= BASE)
    {
        A[i] = (t += A[i] * B) % BASE;
    }
    A[0] = i - 1;
}

void Mul_Nr_Mare_Nr_Mare(LL A[], LL B[])
{
    LL i, j, t, C[1000];
    memset(C, 0, sizeof(C));
    for (i = 1; i <= A[0]; i++)
    {
        for (j = 1, t = 0; j <= B[0] || t; j++, t /= BASE)
        {
            C[i + j - 1] = (t += C[i + j - 1] + A[i] * B[j]) % BASE;
        }
        if (i + j - 2 > C[0]) C[0] = i + j - 2;
    }
    memcpy(A, C, sizeof(C));
}

void Add_Nr_Mare_Nr_Mare(LL A[], LL B[])
{
    LL i, t = 0;
    for (i = 1; i <= A[0] || i <= B[0] || t; i++, t /= BASE)
    {
        A[i] = (t += A[i] + B[i]) % BASE;
    }
    A[0] = i - 1;
}

void Solve()
{
    for (LL i = 0; i <= V[0]; i++)
    {
        S_1[i] = V[i];
        S_2[i] = V[i];
    }
    Scade(S_1, 1);
    Scade(S_2, 2);
    Mul_Nr_Mare_Nr_Mic(V, 4);
    Mul_Nr_Mare_Nr_Mare(S_1, S_2);
    Mul_Nr_Mare_Nr_Mic(S_1, 2);
    Add_Nr_Mare_Nr_Mare(V, S_1);
}

void Write_Data()
{
    if (S[S.size() - 1] == '1' && S.size() == 1)
    {
        fout << 2;
        fout.close();
        return;
    }
    fout << V[V[0]];
    for (LL i = V[0] - 1; i >= 1; i--)
    {
        LL aux = max(V[i], 1LL);
        while (aux < BASE / 10) aux *= 10, fout << 0;
        fout << V[i];
    }
    fout.close();
}

int main()
{
    Read_Data();
    Solve();
    Write_Data();
    return 0;
}