Page 3 of 4

Posted: Mon May 30, 2005 9:58 pm
by Emilio
Hi!
When the answer is "No" you must print the number of chars+1, (remember that (* and *) is only a char), I think that one of yours faults is that you counter [* and *] as one char but only (* and *) are one char.

Hope it help!

Posted: Mon May 30, 2005 11:26 pm
by Sedefcho
No, I do not count [* and/or *] as one char.

I should have some other problem which I currently
can not exactly find out what could be.

Do you know some Java, I can send you my code
although I haven't done this so far.

What do you mean by "you must print the number of chars+1" ?!

Problem says this:

Code: Select all

If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression
This contradicts almost all ACC outputs I've found in threads
here, apparently the Judge's tests do not follow this logic.

Posted: Tue May 31, 2005 9:48 pm
by Emilio
"you must print the number of chars+1" ?!
I only refer to the examples that you have posted.
If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression
but if you reach the end of a test case and not find an expression not properly nested and some brackets are even opened you must print number_of_chars_of_the_case + 1

if you want can send me your code.

Good luck!

Posted: Sat Jun 04, 2005 5:10 pm
by CodeMaker
The outputs given by jagadish is very helpful.

The first output for : (*adf(y)(* given NO 9 by jagadish is ok.

for (* no missmatch count=1;
for a no missmatch count=2;
for d no missmatch count=3;
for f no missmatch count=4;
for ( no missmatch count=5;
for y no missmatch count=6;
for ) no missmatch count=7;
for (* no missmatch count=8;

string is complete but still all the brackets are not closed, so a missmatch occured and the error must go in the empty place, because till count=8 everything is ok, so no complain, thats why error is in the 8+1=9th place, so answer is "NO 9"

I hope it helps. :)

!!!!!

Posted: Sun Jun 05, 2005 6:52 pm
by Raj Ariyan
Hi CodeMaker,
I'm still little bit confuced, what u'r talking abt 11th and 13th Case ???
Jagadish has been sent his output by his ACC solution. I think there is no this type of input in the judge.
Say from u'r opinion <>< should be YES, but if so then why not
(*adf(y)( is Correct. It can also be valid by adding *)). And one think for blank line output should be YES, right ??? My code passed all output with Jagadish Output, but still wrong answer. Anyone plz help me.

Posted: Tue Jun 07, 2005 1:58 pm
by CodeMaker
:oops: Hi , sorry jagadish's output is ok, somehow I missed the angular brackets and still got acc thats because I/O data has no missmatch case for the angular brackets, i m really sorry about that. for blank line my code prints Yes.

I modified my code now, here is some I/O from my code, u can check.

Code: Select all

Input:

( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**)

output:

YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2



Hi

Posted: Wed Jun 08, 2005 7:23 pm
by Raj Ariyan
Hi CodeMaker,
Thanx for your reply. I solved it yesterday. I dont know if u ignore <> then how ur code got accept ? It seems that there is no judge data like that. Very Confusing !!! :roll: :roll: :roll:

Some help

Posted: Fri May 05, 2006 8:34 pm
by lpereira
My AC code gives, for this input:

Code: Select all

((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(
 (
  (
   (
(*)
**()**(**)

(note: the last line is an actual blank line. It was processed)

this output

Code: Select all

YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
NO 3
NO 4
NO 5
NO 2
YES
YES

Posted: Sat May 06, 2006 1:56 am
by rcrezende
I have submitted this code and was judged as WA. I dont know the problem, cause I tested a lot of inputs from eletronic board and the output is always the same.
Below is the code, an input and output.
Please, I need some help!!!

Code: Select all

Source removed, ACCEPTED
Input:

Code: Select all

(
)
(*
*)
{dummy}
*()*
(*)
(* < *) > *)
(* <> *) > *)
rodrigo
**(
()a
a()
()*
()*() 
((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(*adf(y)(*
(*adf(y)(
(a*)
)()
*)()
ads()asdf
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
{adfadf[adfadf(adfa(*adfadf*)adfaf)(*afdsf*)]adfadf}
(AADFASDFADSF)
(**
[**
((((())
(*(*(*(**)*)
(*adf(y)(*
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**) 
My WA output

Code: Select all

NO 2
NO 1
NO 2
NO 1
YES
YES
NO 2
NO 5
NO 8
YES
NO 4
YES
YES
YES
YES
YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
YES
NO 9
NO 9
NO 3
NO 1
NO 1
YES
YES
NO 3
NO 4
NO 6
NO 4
YES
NO 37
NO 37
NO 4
NO 8
NO 7
NO 12
NO 6
YES
NO 2
YES
YES
YES
NO 18
YES
NO 5
YES
NO 10
YES
YES
NO 3
NO 4
NO 8
NO 7
NO 9
YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2
[/code]

Some Help

Posted: Sat May 06, 2006 1:58 am
by rcrezende
I have submitted this code and was judged as WA. I dont know the problem, cause I tested a lot of inputs from eletronic board and the output is always the same.
Below is the code, an input and output.
Please, I need some help!!!

Code: Select all

code removed, ACCEPTED
Input:

Code: Select all

(
)
(*
*)
{dummy}
*()*
(*)
(* < *) > *)
(* <> *) > *)
rodrigo
**(
()a
a()
()*
()*() 
((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(*adf(y)(*
(*adf(y)(
(a*)
)()
*)()
ads()asdf
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
{adfadf[adfadf(adfa(*adfadf*)adfaf)(*afdsf*)]adfadf}
(AADFASDFADSF)
(**
[**
((((())
(*(*(*(**)*)
(*adf(y)(*
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**) 
My WA output

Code: Select all

NO 2
NO 1
NO 2
NO 1
YES
YES
NO 2
NO 5
NO 8
YES
NO 4
YES
YES
YES
YES
YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
YES
NO 9
NO 9
NO 3
NO 1
NO 1
YES
YES
NO 3
NO 4
NO 6
NO 4
YES
NO 37
NO 37
NO 4
NO 8
NO 7
NO 12
NO 6
YES
NO 2
YES
YES
YES
NO 18
YES
NO 5
YES
NO 10
YES
YES
NO 3
NO 4
NO 8
NO 7
NO 9
YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2

Hint

Posted: Sun Jun 11, 2006 4:35 am
by Ndiyaa ndako
If there is an unmatched closing bracket, output the position of the first one with this property. Otherwise, output the length of expression plus one.

Posted: Sun Jun 11, 2006 4:46 am
by rcrezende
My program had WA because it was used a char variable to manage the string's position. I changed to integer and got ACCEPT!!!
This output above is CORRECT!!!!

Posted: Thu Jun 29, 2006 9:49 am
by karu
The problem description is completely wrong.

"In this problem we consider expressions containing brackets that are properly nested. These expressions are obtained by juxtaposition of properly netsted expressions in a pair of matching brackets, the left one an opening and the right one a closing bracket."

There are many problems with this; I will describe one of them.

From "These [properly nested] expressions are obtained by juxtaposition of properly netsted expressions in a pair of matching brackets", we can see that every properly nested expression contains a juxtaposition of properly nested expressions. Therefore, a properly nested expression can never be empty (since this is not a juxtaposition). We can therefore conclude that every properly nested expression must be infinite in size.

Am I wrong?

551 Nesting a Bunch of Brackets WA

Posted: Sun Jul 09, 2006 11:02 pm
by koalahong
I have tried all of input data in all of relative threads. Problem is maybe that when the last line is a blank line , my program will terminate without print "YES". Can anyone tell me how to solve this situation? Thx a lot !

Code: Select all

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int main()
{
	stack<int> bracket[5];	//0 to 4 (), [], {}, <>, (**)
	char exp[3001];
	int offset, i;
	bool error;
	
	while(cin.getline(exp, 3000)!=NULL){
        
		offset=1;
		error = false;

               //initial stacks
		for(i=0 ; i<5 ; i++)
			while(!bracket[i].empty())
				bracket[i].pop();

		for(i=0 ; exp[i]!='\0' ; i++){
        	switch(exp[i]){
			case '(':
				if(exp[i+1]=='*'){
					bracket[4].push(offset);
					offset++;
					i++;
				}
				else{
					bracket[0].push(offset);
					offset++;
				}
				break;
			case ')':
				if(bracket[0].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[0].pop();
					offset++;
				}
				break;
			case '*':
				if(exp[i+1]==')'){
					if(bracket[4].empty()){
						cout << "NO " << offset << endl;
						error = true;
					}
					else{
						bracket[4].pop();
						offset++;
						i++;
					}
				}
				else{
					offset++;
				}
				break;
			case '[':
				bracket[1].push(offset);
				offset++;
				break;
			case ']':
				if(bracket[1].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[1].pop();
					offset++;
				}
				break;
			case '{':
				bracket[2].push(offset);
				offset++;
				break;
			case '}':
				if(bracket[2].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[2].pop();
					offset++;
				}
				break;
			case '<':
				bracket[3].push(offset);
				offset++;
				break;
			case '>':
				if(bracket[3].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[3].pop();
					offset++;
				}
				break;
			default:
				offset++;
				break;
			}// end switch
			
			if(error){
                break;
            }
		}// end for

	      //if no error check all stack are empty or not
               if(!error){
			for(i=0 ; i<5 ; i++){
				if(!bracket[i].empty()){
					cout << "NO " << offset << endl;
					break;
				}
			}
                        //all stacks are empty
			if(i==5)
			    cout << "YES" << endl;
		}
	}

	return 0;
}

Please someone give me the output of the test cases below

Posted: Sun Feb 25, 2007 11:12 pm
by arif_pasha
Can anyone AC'er give me the output for the following test cases:

Code: Select all

()(***)(**)
()(***)(*)
({{}{}}[{(){}[]}
([))
()(**)
()*
aaaaaaa
aaa(aaaa
*******
a*a*a*a
()a
a()
()*()
(*a{+}*)
**)
*(*
(*a++(*)

Thanks in advance.