Problem A
Balance
Languages
da
en
Afgør, om en givet streng af to forskellige slags parenteser er balanceret, dvs. at hver startparentes lukkes af samme slags slutparentes under hensyntagen til indlejringen. For eksempel er »([])()[]« balanceret, hvorimod hverken »((« eller »)(« eller »(]« er balancerede.
Nøjagtigt gælder, at (i) den tomme streng er balanceret; (ii) hvis $w$ er balanceret, så er både $\texttt(w\texttt)$ og $\texttt[w\texttt]$ balancerede; og (iii) hvis $w$ og $x$ er balancerende, så er $wx$ balanceret.
Indlæsning
Indlæsningen består af en enkelt linje indeholdende en ikke-tom følge $w$ af symboler fra alfabetet $\{ \texttt[, \texttt], \texttt(, \texttt)\} $.
Udskrift
Skriv »1« hvis $w$ er balanceret, »0« ellers.
Testgrupper
Lad $|w|$ angive længden af $w$. I samtlige testgrupper gælder $1\leq |w|\leq 200\, 000$.
|
Gruppe |
Points |
Yderligere begrænsninger |
|
1 |
9 |
Der er ingen »[« eller »]« |
|
2 |
10 |
$|w|\leq 100$ |
|
3 |
81 |
Ingen |
| Sample Input 1 | Sample Output 1 |
|---|---|
([(())])[] |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
)( |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
[) |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
(( |
0 |
| Sample Input 5 | Sample Output 5 |
|---|---|
[(]) |
0 |
| Sample Input 6 | Sample Output 6 |
|---|---|
[])[]) |
0 |
| Sample Input 7 | Sample Output 7 |
|---|---|
( |
0 |
