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]
586 - Instant Complexity
Moderator: Board moderators
-
- New poster
- Posts: 21
- Joined: Sun Jan 19, 2003 4:01 pm
- Location: Hong Kong
586 - Instant Complexity
Last edited by Chow Wai Chung on Sat Jun 19, 2004 5:17 pm, edited 1 time in total.
-
- 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
output
It seems no problem, but i got a WA, can anyone point out what is my mistake?
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
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
test my input/output
input:
http://revistes.upc.es/~kiusap/rp/586/proves.in
output:
http://revistes.upc.es/~kiusap/rp/586/proves.out
http://revistes.upc.es/~kiusap/rp/586/proves.in
output:
http://revistes.upc.es/~kiusap/rp/586/proves.out
<kiusap> chmod 700 $me
-
- New poster
- Posts: 21
- Joined: Sun Jan 19, 2003 4:01 pm
- Location: Hong Kong
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
HomePage
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;
}
}
-
- 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;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.