551 - Nesting a Bunch of Brackets
Moderator: Board moderators
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:
This contradicts almost all ACC outputs I've found in threads
here, apparently the Judge's tests do not follow this logic.
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
here, apparently the Judge's tests do not follow this logic.
I only refer to the examples that you have posted."you must print the number of chars+1" ?!
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 + 1If 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
if you want can send me your code.
Good luck!
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh
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.
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.

Last edited by CodeMaker on Tue Jun 07, 2005 2:00 pm, edited 1 time in total.
Jalal : AIUB SPARKS
-
- Learning poster
- Posts: 70
- Joined: Sat Feb 05, 2005 9:38 am
- Location: Gurukul
!!!!!
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.
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.
Some Love Stories Live Forever ....
-
- Experienced poster
- Posts: 183
- Joined: Thu Nov 11, 2004 12:35 pm
- Location: AIUB, Bangladesh

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
Jalal : AIUB SPARKS
-
- Learning poster
- Posts: 70
- Joined: Sat Feb 05, 2005 9:38 am
- Location: Gurukul
Hi
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 !!!

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



Some Love Stories Live Forever ....
-
- New poster
- Posts: 5
- Joined: Wed Nov 16, 2005 7:35 pm
- Location: Campinas - SP - Brazil
- Contact:
Some help
My AC code gives, for this input:
(note: the last line is an actual blank line. It was processed)
this output
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)(
[**
((((())
(*(*(*(**)*)
(
(
(
(
(*)
**()**(**)
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
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!!!
Input:
My WA output
[/code]
Below is the code, an input and output.
Please, I need some help!!!
Code: Select all
Source removed, ACCEPTED
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
(*)(*)*()*(**)
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
Some Help
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!!!
Input:
My WA output
Below is the code, an input and output.
Please, I need some help!!!
Code: Select all
code removed, ACCEPTED
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
(*)(*)*()*(**)
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
-
- New poster
- Posts: 21
- Joined: Sat Sep 25, 2004 3:35 am
- Location: Oaxaca de Ju
- Contact:
Hint
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.
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?
"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
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;
}
-
- New poster
- Posts: 42
- Joined: Fri Jun 13, 2003 3:47 pm
- Location: Dhaka , Bangladesh
- Contact:
Please someone give me the output of the test cases below
Can anyone AC'er give me the output for the following test cases:
Thanks in advance.
Code: Select all
()(***)(**)
()(***)(*)
({{}{}}[{(){}[]}
([))
()(**)
()*
aaaaaaa
aaa(aaaa
*******
a*a*a*a
()a
a()
()*()
(*a{+}*)
**)
*(*
(*a++(*)
Thanks in advance.