Page 6 of 10

112 WA WHY

Posted: Mon Mar 29, 2004 1:46 pm
by komunist
Help me please.
Where is my error?

var i,j,k,n,m,s,s1,s2:longint;
ch:char;
a :array [1..200000] of char;
b,c:array [1..200000] of longint;
f:boolean;

procedure push(a:longint);begin inc(s1);c[s1]:=a;s2:=s2+c[s1];end;
procedure pop; begin s2:=s2-c[s1];c[s1]:=0;dec(s1);end;

begin
while not eof do
begin
read(n);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
m:=0;k:=0;s:=0;s1:=0;s2:=1;
while true do
begin
read(ch);
if ch='-' then s2:=-1;
if ch='(' then begin inc(k);inc(s1);s2:=1;inc(m);a[m]:=ch;end;
if ch=')' then
begin
if a[m]='(' then begin a[m]:='#';dec(s1); end
else begin inc(m);a[m]:=')'; end;
dec(k);
end;
if ch in ['0'..'9'] then b[s1]:=b[s1]*10+s2*(ord(ch)-ord('0'));
if (m>0) and (k=0) then break;
end;
s1:=0;
s2:=0;
f:=false;
j:=0;
for i:=1 to m do
begin
if a='(' then begin inc(j);push(b[j]); end;
if a=')' then pop;
if a='#' then if s2=n then begin f:=true; break; end;
end;
if f=true then writeln('yes') else writeln('no');
end;
end.

Posted: Wed Mar 31, 2004 2:26 pm
by komunist
:(
HELP Please.

112 Tree Summing( WA)

Posted: Mon May 31, 2004 9:54 am
by shamim
I get WA, my code passes all the input in the board. Please Help

[cpp]


CUT
[/cpp]

I found my mistake.

my program fails for cases like

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

The answer should be "no".

Posted: Tue Jun 01, 2004 2:22 pm
by chunyi81
Hi, try the following input:

input:
-3 (-1(-1()())(-2()()))

output:
yes

Hope this helps.

Posted: Fri Jul 30, 2004 9:42 am
by Chocobo
all above cases are OK but i still got WA... :cry:

WA

Posted: Thu Aug 19, 2004 6:59 am
by Skeeter
Hi!
I`ve got some trouble with this problem. It looks to me like the Input isn`t described precisely in the target setting.
First of all, the integers might be positive, negativa and take 0 values, yes?
Then, is each test case terminaed with a '\n' symbol?
And two more questions: are the elements of the pare: integer , S-expression always devided by a space; Can a test case contain ' ' or '\n' symbols after the S-expression.
I use the cin.eof() function in my C++, I`m not sure it works on the tests.
Thaks a lot.

112 Why W.A

Posted: Wed Sep 22, 2004 9:24 am
by efr_shovo
112 Gives W.A. Why? Please Some Body Help Me.

please give me some Critican Input & Output

problem with 112

Posted: Mon Dec 13, 2004 8:01 am
by emotional blind
i think my program is ok.
but wa.
so i need some critical input and output.
can any body help me.
thanks.

112 gets wa

Posted: Wed Dec 29, 2004 10:52 am
by emotional blind
my solution gets wa
can anyone help me ?

Code: Select all

#include<stdio.h>
#include<string.h>

char str[200000];
int summing (int num);
int main(void)
{
	int num, i, left, right;
	
	char c;
	while(scanf("%d",&num)==1){
		while((c=getchar())!='(');
		left=1;
		right=0;
		i=0;
		str[i++]=c;
		while(left!=right){
			c=getchar();
			if(isdigit(c) || c=='(' || c==')' || c=='-')str[i++]=c;
			if(c=='(')left++;
			else if(c==')')right++;
		}
		str[i]='\0';
		if(summing(num))printf("yes\n");
		else printf("no\n");
		
		
	}
	return 0;
}

int summing (int num)
{
	int stack[2000], top, left, right, i, j, sum, m=1;
	int leftC=1;
	top=0;
	i=1;
	left=1;
	right=0;
	
	while(right!=left){
		if(str[i]=='('){
			left++;
		}
		else if(str[i]==')'){
			right++;
			if(str[i-1]=='('){
				if(leftC)leftC=0;
				else{
					sum=0;
					for(j=0;j<top;j++)
						sum+=stack[j];
					if(sum==num)return 1;
					leftC=1;
				}
			}
			else if(str[i-1]==')'){
				top--;
				leftC=1;
			}
		}
		else if(str[i]=='-')m=-1;
		else{
			sum=0;
			sum+= str[i]-'0';
			while(isdigit(str[i+1])){
				i++;
				sum=sum*10+str[i]-'0';
			}
			stack[top++] = m*sum;
			m=1;
		}
		i++;
	}
	
	return 0;
}
it is my simple code
i used stack operation.

...

Posted: Wed Jan 12, 2005 10:09 am
by ImLazy
I think I'm in the same situation with Emotional Blind. My program works all right by the sample input while still gets WA by the on-line judge. I just need some special input to help me to debug. Anyone can help us?
This is my code:

Code: Select all

#include<stdio.h>
#define MAX 100
int main()
{
  int i,j,k,
      get,
      node[MAX],/*记录一条路径上的每个节点的值*/
      tree[MAX][2],/*每个结点上已经连上的结点数,每个结节点上有几个枝是空的*/
      sum,
      treesum,
      cntleft,cntright;
  char c;
  while(scanf("%d",&sum)==1)
  {
    for(i=0;i<MAX;i++)
    {
      node[i]=0;
      tree[i][0]=0;
      tree[i][1]=0;
    }
    i=0;
    j=-1;
    get=0;
    cntleft=0;
    cntright=0;
    do
    {
      while(1)
      {
        c=getchar();
        if(c==')')
          cntright++;
        if(c=='(')
        {
          cntleft++;
          break;
        }
      }
      j++;/*找到左括号了,树就向下走一层*/
      if(scanf("%d",&node[i])==1)
      {
        i++;
        continue;/*回到do,再开始找括号*/
      }
      else
      {
        j--;/*读不到数就回到上一层*/
        if(j>=0)/*如果是-1,说明根结点都没有,自然就结束了*/
        {
          tree[j][0]++;/*读不到数说明上一层的一枝已经到头了*/
          tree[j][1]++;/*且有一枝是空*/
        }
        if(j>=0 && tree[j][1]==2)/*两枝都空则找到一条路径*/
        {
          tree[j][0]=0;/*把这一层的枝数归零,以便自己另外一个兄第枝的计算*/
          tree[j][1]=0;
          j--;
          tree[j][0]++;
          treesum=0;
          for(k=0;k<i;k++)
            treesum+=node[k];
          if(treesum==sum)
          {
            get=1;
            break;
          }
          i--;/*回到上一层读另一枝读数*/
        }
        while(j>=0 && tree[j][0]==2)/*一直回溯到还没有两枝都满的那一层,重新找路径*/
        {
          tree[j][0]=0;
          tree[j][1]=0;
          j--;
          tree[j][0]++;
          i--;
        }
      }
    }while(tree[0][0]<2 && j>=0);/*根结点的两枝都满了,或都根结点为空,就结束了,*/
    while(cntleft!=cntright && cntleft!=0)/*把这一次输入剩下的那些东西都吃光*/
    {
      c=getchar();
      if(c==')')
        cntright++;
      if(c=='(')
        cntleft++;
    }
    if(get==1)
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}

...

Posted: Thu Jan 13, 2005 5:25 am
by ImLazy
Dear Mistr,
My program works all right by the inupts you have given above, but still WA!!! I'm getting crazy!

112 WA Please help me.....Wrked for all the test cases given

Posted: Sat Feb 12, 2005 6:34 pm
by masumasu
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>

using namespace std;

class linkedlist
{
public:
int value;
char *path;
linkedlist *next;
};
class linkhead
{
public :
int level;
linkedlist *next;

linkhead()
{
next = NULL;
}
};
linkhead **tree;

void displaytree(int treeheight)
{
for (int i=0;i<=treeheight;i++)
{
linkedlist *p = tree[i]->next;
while (p!=NULL)
{
cout << p->value << " " << p->path << " ";
p = p->next;
}
cout << endl;
}
}

void putnodevalue(int nodevalue,char* path,int level)
{
if (tree[level]->next==NULL)
{
//cout << " Null here ...\n";
tree[level]->next = new linkedlist();
tree[level]->next->next = NULL;
tree[level]->next->value = nodevalue;
tree[level]->next->path = new char[strlen(path)+1];
strncpy(tree[level]->next->path,path,level);
//tree[level]->next->path[level+1] = 0;
tree[level]->next->path[level+1] = 0;
return ;
}

//cout << " not Null here ...\n";
linkedlist *p = tree[level]->next;
while (p->next!=NULL)
p = p->next;

p->next = new linkedlist();
p->next->value = nodevalue;
p->next->next = NULL;
p->next->path = new char[strlen(path)+1];
strncpy(p->next->path,path,level);
p->next->path[level+1] = 0;

p = tree[level]->next;
/*while (p!=NULL)
{
cout << p->value << " "<< p->path <<" ";
p=p->next;
}
cout << endl;*/
return ;
}

bool presentstring(char *s1,char *s2,int number)
{
if (number==0)
return true;
for (int i=0;i<number-1;i++)
if (s1[i]!=s2[i])
return false;
return true;
}
bool presentsum(int reqdsum,int treeheight,int currlevel,char *path)
{

if (tree[currlevel]->next==NULL)
{
//cout << "Here...\n";
if (( currlevel==0) || (reqdsum!=0))
return false;
else
return true;
}
linkedlist *p = tree[currlevel]->next;
while (p!=NULL)
{
//cout << "Came here...\n";
if (presentstring(p->path,path,currlevel))
{
//cout << "True";
if (presentsum(reqdsum - p->value,treeheight,currlevel+1,p->path))
{
return true;
}
}
p = p->next;
}

return false;

}
int main()
{
char c;
char path[105];
int reqdsum,treelevel = 0,valuesign,treeheight=-1;
bool lefttree;

//strcpy(path,"222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");

//strcpy(path,"22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");

while (cin >> reqdsum)
{
tree = new linkhead*[105];
for (int i=0;i<105;i++)
tree[i] = new linkhead();
while ((c=getchar())!='(')
{
}
//getchar();
//getchar();

lefttree = true;
treelevel = 0;
int nodevalue = 0;
valuesign = 1;
treeheight = -2;
//strcpy(path,"22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222");
for (int i=0;i<105;i++)
path[i]='2';

while ( (treelevel>=0) and ( (c=getchar())!=EOF ) )
{
if ((c==' ') || (c=='\n'))
{
continue;
}
if (c=='-')
{
valuesign = -1;
}

if ((c>='0') and (c<='9'))
{
do
{
nodevalue = nodevalue * 10 + (c-'0')* valuesign;
c=getchar();
}while ((c>='0') and (c<='9'));

putnodevalue(nodevalue,path,treelevel);
//cout << nodevalue << " " << treelevel << endl;
//cout << path << endl;
ungetc(c,stdin);
nodevalue=0;
valuesign = 1;
if (treeheight<treelevel)
treeheight = treelevel;
continue;
}
if ( c=='(')
{
//treelevel++;
//if (treelevel==-1)
// treelevel++;
if (path[treelevel]=='2')
{
path[treelevel]='0';
}
else if (path[treelevel]=='0')
path[treelevel]='1';
treelevel++;

}
else if (c==')')
{
if (treelevel>=0)
{
path[treelevel]='2';
treelevel--;
}
}

}
//if (tree[0]->next==NULL)
/// cout << "Tree Null no\n";
// else
if (presentsum(reqdsum,treeheight,0,""))
cout << "yes\n";
else
cout << "no\n";
//displaytree(treeheight);
/*while ((c=getchar())!=EOF)
if (( (c>='0') and (c<='9') ) or (c=='-') )
break;
ungetc(c,stdin); */
//cout << endl;
//for (int i=0;i<1000;i++)
// delete []tree;

//delete tree;
}
}

Posted: Sun Feb 13, 2005 7:34 am
by teni_teni
Though I don't look into your code, try this input:

Code: Select all

3
(1
  (1 (1 ()()) ())
  (2 ()       ())
)

3
(1
  (1 (2 ()()) ())
  (2 ()       ())
)

Posted: Tue Feb 15, 2005 8:33 am
by masumasu
hi thans to u
even though i cant figure out how u got that input for which my prog didnt work ......... i corrected it and its accepted now.........
again thans

Posted: Tue Feb 15, 2005 12:59 pm
by ImLazy
I think the output should be:

Code: Select all

yes
yes
My code works all right for the input above, but still WA.

Code: Select all

#include<stdio.h>
#define MAX 100
int main()
{
  struct node
  {
    int value;
    int visit;
    struct node *parent,*left,*right;
  }tree[MAX],*p,*temp;
    int n,
        get,
        sum,
        treesum,
        cnt_left,cnt_right,
        cnt_node,
        i;
  char c;
  while(scanf("%d",&sum)==1)
  {
    for(i=0;i<MAX;i++)
    {
      tree[i].visit=0;
      tree[i].parent=NULL;
      tree[i].left=NULL;
      tree[i].right=NULL;
    }
    get=0;
    cnt_left=0;
    cnt_right=0;
    cnt_node=0;
    p=&tree[0];
    p->parent=NULL;
    do
    {
      while(1)
      {
        c=getchar();
        if(c==')')
          cnt_right++;
        if(c=='(')
        {
          cnt_left++;
          break;
        }
      }
      if(scanf("%d",&n)==1)
      {
        p->value=n;
        cnt_node++;
        p->left=&tree[cnt_node];
        p->left->parent=p;
        cnt_node++;
        p->right=&tree[cnt_node];
        p->right->parent=p;
        p=p->left;
        continue;/*回到do,再开始找括号*/
      }
      else if(p->parent!=NULL)
      {
        p=p->parent;
        p->visit++;
        if(p->visit==1)
        {
          p->left=NULL;
          p=p->right;
        }
        else if(p->visit==2)
        {
          p->right=NULL;
          if(p->visit==2 && p->left==NULL)
          {
            treesum=p->value;
            temp=p;
            while(temp->parent!=NULL)
            {
              temp=temp->parent;
              treesum+=temp->value;
            }
            if(treesum==sum)
            {
              get=1;
              break;
            }
          }
          while(p->parent!=NULL && p->visit==2)/*一直回溯到两枝还没有走完的那一层*/
          {
            p=p->parent;
            p->visit++;
          }
          if(p->visit==1)
            p=p->right;
        }
      }
    }while(tree[0].visit<2 && (tree[0].left!=NULL || tree[0].right!=NULL));
    /*最顶层的两枝都满了,或两枝都空就结束了*/
    while(cnt_left!=cnt_right && cnt_left!=0)/*把这一次输入剩下的那些东西都吃光*/
    {
      c=getchar();
      if(c==')')
        cnt_right++;
      if(c=='(')
        cnt_left++;
    }
    if(get==1)
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}