Cod sursa(job #2359294)

Utilizator iustin948Homoranu Iustin iustin948 Data 28 februarie 2019 19:28:37
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("evaluare2.in");
ofstream fout("evaluare2.out");

char s[105];
long long st[105];
long long mem[105];
int top;

long long putere(long long  x,long long p)
{
    long long  nr=1;
    while(p>=1)
    {
        if(p%2)
        {
            nr=(nr*x);
            p--;
        }
        else
        {
            x=(x*x);
            p/=2;
        }
    }
    return nr;
}

long long Oglinda(long long a)
{
    long long x = 0;
    while(a)
    {
        x = x * 10 + a % 10;
        a /= 10;
    }
    return x;
}

void Add(int &i)
{
    int k = 0;;
    mem[++k] = st[top];

        while(s[i] == '^')
            {
                bool p = 0;
                i++;
                long long x = 0;
                while(s[i] >='0' && s[i] <='9')
                x = x * 10 + (s[i] - '0'), i++, p = 1;
                if(p) mem[++k] = x;
            }
    while(k)
    {
        mem[k-1] = putere(mem[k-1],mem[k]);
        k--;
    }
    st[top] = mem[1];
}

void Solve()
{
    fin >> s;

    int i, j;
    for(i=0; s[i]; i++)
    {

        if(s[i] == '(') st[++top] = -1;
        else if(s[i] >='0' && s[i] <='9')
        {
            long long x = 0;
            while(s[i] >='0' && s[i] <='9')
                x = x * 10 + (s[i] - '0'), i++;

            st[++top] = x;
            i--;
        }
        else if(s[i] == ')')
        {
            long long sum = 0;
            while(st[top] != -1)
            {

                sum += st[top];
                top--;
            }
            st[top] = sum;
        }
        else if(s[i] == '!')
        {
            int cnt = 0;
            while(s[i] == '!') cnt++, i++;
            long long x = 0;
            while(s[i] >='0' && s[i] <='9')
                x = x * 10 + (s[i] - '0'), i++;
            for(j=1; j<=cnt; j++)
                x = Oglinda(x);
            st[++top] = x;
            i--;
        }
        else if(s[i] == '^')
        {
            Add(i);
            i--;
        }
        else if(s[i] == '/')
        {
            i++;
            long long x = 0;
            while(s[i] >='0' && s[i] <='9')
                x = x * 10 + (s[i] - '0'), i++;
                st[top] /= x;
                i--;
        }
    }
    long long sum = 0;
    for(j=1; j<=top; j++)
        sum +=  st[j];
    fout << sum << "\n";
}

int main()
{
    Solve();

    return 0;
}