586 - Instant Complexity

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

586 - Instant Complexity

Post by Chow Wai Chung » Thu Mar 20, 2003 3:28 am

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]
Last edited by Chow Wai Chung on Sat Jun 19, 2004 5:17 pm, edited 1 time in total.

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

This is my test case and output

Post by Chow Wai Chung » Fri Apr 04, 2003 2:33 am

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? :o

User avatar
kiusap
New poster
Posts: 3
Joined: Thu May 20, 2004 2:11 pm
Location: barcelona

test my input/output

Post by kiusap » Wed Jun 09, 2004 4:58 pm

<kiusap> chmod 700 $me

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Sat Jun 19, 2004 5:17 pm

Thank you very much!!!

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Apr 23, 2006 10:51 pm

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.
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 586 WA

Post by x140l31 » Mon Aug 18, 2008 7:32 pm

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 586 - Instant Complexity

Post by metaphysis » Thu Aug 18, 2016 5:24 pm

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;
}

Post Reply

Return to “Volume 5 (500-599)”