<PREV Problem:
NEXT>
Solved by 630 users: ...
UserDateAttemptTimeCMSC
sb3ar17 mar 2008Ruby1300.0248 
sb3ar17 mar 2008Ruby1400.0248 
sb3ar11 dec 2007Ruby1100.0250 
lodin25 sep 2006Perl400.0750 
pshen13 jun 2012C++400.0152 
V.A.KeRneL19 feb 2007Ruby900.0252 
sb3ar11 dec 2007Ruby900.0253 
V.A.KeRneL19 feb 2007Ruby1000.0253 
lodin24 sep 2006Perl200.0654 
V.A.KeRneL19 feb 2007Ruby800.0255 
Council22 sep 2006Perl800.0555 
Philip_PV09 jul 2008C200.0156 
sb3ar11 dec 2007Ruby700.0256 
pshen13 jun 2012C++300.0157 
fetetriste22 nov 2007C++500.0158 
Philip_PV09 jul 2008C100.0159 
david_it2116 apr 2008Ruby100.0259 
Council22 sep 2006Perl700.0559 
V.A.KeRneL19 feb 2007Ruby600.0262 
pshen13 jun 2012C++200.0164 
V.A.KeRneL19 feb 2007Ruby500.0264 
kornakovBSU25 sep 2009C++200.0167 
Council22 sep 2006Perl600.0567 
fetetriste27 mar 2007C++300.0170 
scholl23 jul 2007C++1100.0170 
scholl23 jul 2007C++1200.0170 
Languages
C++
288
FPC
146
C
106
Java
44
Kylix
33
Ruby
8
Python
7
Perl
6
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Bracket structure correction

Time limit = 2 second(s)

Given the string of '(' and ')' you are to find the minimal number of corrections that is nessesary to do in it to make this string to be a correct bracket structure. Correction = changement the bracket to the different one.

Right bracket structure can be defined as follows:

expr ::= expr expr | (expr) | "()"

Here are correct bracket structures:

    ()()()
	(())()
	((((()))))
Here are INcorrect bracket structures

	)(
	))((
	())(
	))))
	(((()(

Input. One or more lines, containing symbols '(' and ')' of total length lesser than 1000.

Output. Minimal number of corrections. If there is no way to correct the input string, you are to output "NO".

Input#1
((((
Output#1
2

Input#2
((()

Output#2
1

Input#3
(((

Output#3
NO

Author:
Folklore
3 March 2005

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.232.133.231