## 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

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

### 586 - Instant Complexity

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

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
New poster
Posts: 3
Joined: Thu May 20, 2004 2:11 pm
Location: barcelona

### test my input/output

<kiusap> chmod 700 \$me

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong
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
Contact:
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

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

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