586 - Instant Complexity

[Chow Wai Chung]

I had test my program many times, but i still get a WA, can anyone test my program and tell me what mistake i have??
Thank you!!
[c]
AC now...thanks
[/c]

[Chow Wai Chung]

This is my input

Code: Select all

9



    BEGIN
LOOP 
OP 50
END
OP 9
END
BEGIN
LOOP n LOOP n LOOP 4 LOOP 9 END END END END END 
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
BEGIN
END
BEGIN
LOOP 110
OP 4
END
END

output

Code: Select all

Program #1
Runtime = 9

Program #2
Runtime = 0

Program #3
Runtime = 3*n^2+11*n+17

Program #4
Runtime = n^2+1997

Program #5
Runtime = 0

Program #6
Runtime = 440

Program #7
Runtime = 100*n^10+2*n^9+3*n^8+4*n^7+5*n^6+6*n^5+7*n^4+8*n^3+9*n^2+10*n+11

Program #8
Runtime = 3000

Program #9
Runtime = 3*n+6

It seems no problem, but i got a WA, can anyone point out what is my mistake?

[kiusap]

input:
http://revistes.upc.es/~kiusap/rp/586/proves.in

output:
http://revistes.upc.es/~kiusap/rp/586/proves.out

[Chow Wai Chung]

Thank you very much!!!

I got AC now....made a small mistake b4...thx...

[Jan]

The input set posted is not correct. Because a 'LOOP' statement has a 'LOOP-header'. 'LOOP-header' can be either in 'LOOP n' or 'LOOP p' form, where p is a non-negative integer.

[x140l31]

always WA can anyone help me please???

Code: Select all

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef vector<int> VI;

int convert(string num)
{
    int res = 0;
    for (int i = 0; i < num.size(); i++) res = res*10 + (num[i] - '0');
    return res;
}

VI evalue()
{
    VI complexity(11, 0);
    string prog;
    int x;
    cin >> prog;
    while (prog != "END")
    {
        if (prog == "LOOP")
        {
            VI aux;
            string num;
            cin >> num;
            if (num != "n")
            {
                int x = convert(num);       
                aux = evalue();
                for (int j = 0; j < 11; j++) complexity[j] += x*aux[j];
            }
            else
            {
                aux = evalue();
                for (int j = 0; j < 10; j++) complexity[j + 1] += aux[j];
            }
        }
        else if (prog == "OP")
        {
            cin >> x;
            complexity[0] += x;
        }
        cin >> prog;
    }
    return complexity;
}

int main()
{
    int n;
    cin >> n;
    string op; cin >> op;
    for (int cas = 1; cas <= n; cas++)
    {
        VI complexity = evalue();

        cout << "Program #" << cas << endl;
        cout << "Runtime = ";
        int j = 11;
        while (not complexity[--j]);
        if (j <= 1) cout << complexity[0];
        else
        {
            if (complexity[j] > 1) cout << complexity[j] << "*n";
            else cout << 'n';
            if (j > 1) cout << '^' << j;
            for (--j ; j > 1; j--)
            {
                if (complexity[j] > 1) cout << '+' << complexity[j] << "*n^" << j;
                else if (complexity[j] == 1) cout << '+' << "n^" << j;
            }
            if (complexity[1] > 1) cout << '+' << complexity[1] << "*n";
            else if (complexity[1] == 1) cout << '+' << 'n';
            if (complexity[0] > 1) cout << '+' << complexity[0];
        }
        cout << endl << endl;
    }
}

[metaphysis]

There is test data generator wrote in C++ below.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAX_CASES = 100, MAX_OP = 60, MAX_STACK = 10, BASE = 10;

int main(int argc, char *argv[])
{
    cout << MAX_CASES << "\n\n";
    
    srand(time(NULL));
    
    for (int c = 1; c <= MAX_CASES; c++)
    {
        if (c > 1)
            cout << '\n';
            
        int ops = 1, stack = 0;
        
        cout << "BEGIN\n";
        while (ops < MAX_OP)
        {
            if (rand() % 2 + 1 > 1 && stack < MAX_STACK)
            {
                stack++;
                cout << "LOOP ";
                if (rand() % 10 > 3)
                    cout << 'n';
                else
                    cout << rand() % BASE;
            }
            else
            {
                cout << "OP ";
                cout << rand() % BASE;
            }
            
            cout << '\n';
            
            if (stack > 0)
            {
                if (rand() % 10 > 7)
                {
                    cout << "END\n";
                    stack--;
                }
            }
            
            ops++;
        }
        
        while (stack > 0)
        {
            cout << "END\n";
            stack--;
        }
        
        cout << "END\n";
    }
    
    return 0;
}