OJ Board

thanks,I've already try that way before but with misstyping.
i use '\' instead of '/' .

thanx.

I've searched all of the articles related to prob 102,
but there were no one who got TLE.

My idea is :
1. Build tree from string
2. Find all of the possible combinations to make I (integer)
through "INORDER" tree traverse.

but I got TLE.
It works fine in negative inputs.

I think that if we want to find integer 'I', we must search all of the tree nodes.
Right? If it is, my problem isn't at step 2.

Somebody have tricky inputs which make my code fool?

I tested with Hisoka's, but it works fine except following one :

0 (1()
(-2 () (1()())))
)

Hey, it has one more extra right parenthesis, isn't it?
I must consider such a wrong input?

This is my code:
[cpp]
// Problem 112. Tree Summing at http://acm.uva.es/p/v1/112.html

#include <cstdio>
#include <cctype>
#include <string>

using namespace std;

struct NodeType {
int Value;
NodeType* Left;
NodeType* Right;

NodeType():Value(0),Left(NULL),Right(NULL) {}
~NodeType()
{
if (Left != NULL)
delete Left;

if (Right != NULL)
delete Right;
}
};

int getNodeString(string T, string& N, int Start);
void getTreeString(string& T);
bool treeTraverse(NodeType* Root, int I);
NodeType* buildTree(string T);

int main()
{
int I;
string T;
NodeType* Root = NULL;

while (scanf("%d", &I) != EOF) {
getTreeString(T);

Root = buildTree(T);

if (Root != NULL && treeTraverse(Root, I))
printf("yes\n");
else
printf("no\n");

delete Root;
}
}

bool treeTraverse(NodeType* Root, int I)
{
if (Root == NULL)
return false;
else if (I - Root->Value == 0 && Root->Left == NULL && Root->Right == NULL)
return true;
else
return treeTraverse(Root->Left, I - Root->Value)
|| treeTraverse(Root->Right, I - Root->Value);
}

int getNodeString(string T, string& N, int Start)
{
int Parentheses = 1, End;

N = "(";
for (int i = Start + 1; i <= T.size() && Parentheses != 0; i++) {
N = N + T;
if (T == '(')
Parentheses++;
else if (T == ')') {
End = i;
Parentheses--;
}
}

return End;
}

NodeType* buildTree(string T)
{
NodeType* Root;

int Value, Parentheses = 1, Start, End;
char Dummy;
string LeftNode, RightNode;

if (T == "()") {
return NULL;
} else {
Root = new NodeType;

sscanf(T.c_str(), "%c%d", &Dummy, &Value);

Root->Value = Value;

for (int i = 1; i <= T.size(); i++) {
if (T == '(') {
Start = i;
break;
}
}

getNodeString(T, RightNode, getNodeString(T, LeftNode, Start) + 1);

Root->Left = buildTree(LeftNode);
Root->Right = buildTree(RightNode);

return Root;
}
}

void getTreeString(string& T)
{
int Parentheses = 1;
char C;

while (scanf("%c", &C) != EOF) {
if (C == '(')
break;
}

T = "(";
while (Parentheses != 0) {
scanf("%c", &C);

if (C == '(') {
Parentheses++;
T = T + C;
} else if (C == ')') {
Parentheses--;
T = T + C;
} else if (isdigit(C) || C == '-') {
T = T + C;
}
}

while (C != '\n')
scanf("%c", &C);
}
[/cpp]

Thanks.[/quote]

Thanks for correction, for this problem, judge should not gave you a wrong input. this is my mistake.

bye.......

I didn't want to hurt you, Hisoka

Sorry for my rudeness

hello, I think you not understand about my previous post. I only give you my thanks, because you correction my sample I/O, and this is good. You never hurt me...

bye....

i got WA after my program running about 1 second!!!
is there any trick in this problem??

[cpp]
#include <iostream.h>
#include <stack>
#include <stdlib.h>

using std::stack;

void main()
{
int br, W, SN;
char a, integer[15];
stack<int> weight;
stack<int> subnum;
int sum, I, q, i;
bool yes, frbr;

while (cin >> I) {
br = 0;
frbr = true;
q = 0;
sum = 0;
yes = false;
while (1) {
cin >> a;
if (a == '(') {
if (q == 0)
q = 1;
if (q == 2)
q = 3;
br++;
if (!frbr) {
SN = subnum.top();
subnum.pop();
SN++;
subnum.push(SN);
}
if (frbr)
frbr = false;
}
if (a == ')') {
br--;
if (br == 0)
break;
if (q == 1)
q = 2;
if (q == 3) {
if (sum == I)
yes = true;
q = 0;
}
W = weight.top();
SN = subnum.top();
weight.pop();
subnum.pop();
if (SN == 1) {
weight.push(W);
subnum.push(SN);
}
else
sum = sum - W;
}
if ((a >= '0' && a <= '9') || a == '-' || a == '+') {
q = 0;
i = 0;
while ((a >= '0' && a <= '9') || a == '-' || a == '+') {
integer = a;
i++;
cin >> a;
}
integer = '\0';
cin.putback(a);
W = atoi(integer);
SN = 0;
weight.push(W);
subnum.push(SN);
sum = sum + W;
}
}
if (yes)
cout << "yes\n";
else
cout << "no\n";
cin.clear();
}
}
[/cpp]

Et Xndir@ Exela mer Olimpiadayi xndir@ ev mi txa lucela.Gna iranic harcru.

hi....
does anybody has any idea wat the judge input is like?
i keep getting time limit exceeded even though i dun use any recursion!

thanks!

I've got the WA!
Constantly...
I try with 0, i try with negative values..
It worked. (on my computer) But there...

The algorithm works for all test cases i can think about.

Do you know, a leading ora trailing space matters? Shouldn't i got an PE warning?

Anybody?

i took these tests from Hisoka, they helped me. maybe it will help u 2.

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
) ) )
() ) () )
yes

0 ( )
no

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))
yes

0 (1()
(-2 () (1()())))
yes

1 (1 () (0 ()()) )
yes

good luck

I've a trouble with it.

I can't find bug in my code.
It works well for any test case that I thought.

help me, please...
[cpp]
#include <cctype>
#include <iostream>
using namespace std;

#define STACK_MAX 10000

main()
{
char cByte;
bool bResult;
int i, iTmp;
int iLeaf, iStack, iValue;
int iaStack[STACK_MAX];

cin >> iValue;
while(cin)
{
bResult = false;
iLeaf = 0, iStack = 1;
while(cin && (cByte = cin.get()) != '(');
while(cin && iStack > 0 && (cByte = cin.peek()))
{
if(cByte == '(')
{
cin.ignore();
while(cin && isspace(cin.peek())) cin.ignore();
if(cin.peek() == ')') iLeaf++, cin.ignore();
else iStack++;
}
else if(cByte == ')')
{
cin.ignore();
iStack--;
}
else if(isdigit(cByte) || cByte == '-')
{
cin >> iaStack[iStack - 1];
iLeaf = 0;
}
else cin.ignore();

if(!bResult && iLeaf == 2)
{
iLeaf = iTmp = 0;
for(i = 0; i < iStack; i++)
iTmp += iaStack;
if(iTmp == iValue) bResult = true;
}
}
cout << (bResult ? "yes" : "no") << endl;
cin >> iValue;
}

return 0;
}
[/cpp]

why.. WA...?

give me some test case or hint...plz.

I'm very tired....help me

[cpp]
#include <cctype>
#include <iostream>
using namespace std;

#define STACK_MAX 10000

main()
{
char cByte;
bool bResult;
int i, iTmp;
int iLeaf, iStack, iValue;
int iaStack[STACK_MAX];

cin >> iValue;
while(cin)
{
bResult = false;
iLeaf = 0, iStack = 1;
while(cin && (cByte = cin.get()) != '(');
while(cin && iStack > 0 && (cByte = cin.peek()))
{
if(cByte == '(')
{
cin.ignore();
while(cin && isspace(cin.peek())) cin.ignore();
if(cin.peek() == ')') iLeaf++, cin.ignore();
else iStack++;
}
else if(cByte == ')')
{
cin.ignore();
iStack--;
}
else if(isdigit(cByte) || cByte == '-')
{
cin >> iaStack[iStack - 1];
iLeaf = 0;
}
else cin.ignore();

if(!bResult && iLeaf == 2)
{
iLeaf = iTmp = 0;
for(i = 0; i < iStack; i++)
iTmp += iaStack;
if(iTmp == iValue) bResult = true;
}
}
cout << (bResult ? "yes" : "no") << endl;
cin >> iValue;
}

return 0;
}
[/cpp]

I tested your program with random data; some tests for which your program produced wrong results are:

autotester wrote:8(8(2(1()())())())
8(8(3(7()())())())
4(4(2(4()())())())
5(5(4()(1(7(3()())(4()()))(4(3()())())))())
21(7()(5()(5()(4(1(7()())())()))))
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))())
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))())))
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())())))
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))()))))

I don't know what's wrong in my code><

I've considered the negative inputs and 0 () is "no"

[cpp]
#include <iostream.h>
#include <stdio.h>

int find;
int n;
int ans;
int ansc;

void DFS(int sum)
{
int s=0;
int temp=0;
char c;
int us=1;

while (scanf ("%c",&c)==1)
{
if (c=='-')
{
us=-1;
continue;
}

if (c==' ' || c=='\n')
continue;
else if (c>='0' && c<='9')
temp=temp*10+c-'0';
else
{
if (c==')')
{
if (temp==0)
{
if (ansc==0)
{
ans=sum;
ansc++;
}
else
{
if (sum==ans)
{
if (ans==n)
{
find=1;
return;
}
}
else
{
ansc=1;
ans=sum;
}
}
}
return;
}


DFS(sum+temp*us);
while (scanf ("%c",&c)==1 && c!='('){};
DFS(sum+temp*us);
}
}
}

int main()
{
char c;

//freopen ("112.txt","w",stdout);

while (scanf ("%d",&n)==1)
{
find=0;

while (scanf ("%c",&c)==1 && c!='('){};
ansc=0;
DFS(0);

if (find)
cout << "yes" << endl;
else
cout << "no" << endl;
}

return 0;
}
[/cpp]

I didn't debug your code, but maybe you should focus on this:
Perhaps you are not reading blank lines correctly?

Also --