oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bracket_ex Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

bracket_ex.html

Problem Description

Given a bracket sequence of length L, you are to determine if it is valid!

A valid bracket sequence is defined recursively as:

  • "" or
  • (x) where x is a valid bracket sequence, or
  • xy, where x and y are valid bracket sequences.

However, two other pairs of brackets can be found in the bracket sequence, '[' which is to be matched with ']' and '{' which is to be matched with '}'.

Limits

For all tests: each character will be one of the following: '(', ')', '[', ']', '{', '}'.

Subtask 1 (10%): 1 ≤ L ≤ 4.

Subtask 2 (30%): 1 ≤ L ≤ 1000.

Subtask 3 (20%): 1 ≤ L ≤ 100000. However, each character will be either '(' or ')'.

Subtask 4 (40%): 1 ≤ L ≤ 100000.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain one integer, L.

The second line of input will contain one string, the bracket sequence.

Output

The output should contain one string, either "Valid" or "Invalid".

Sample Testcase 1

Input

6
([]{})

Output

Valid

Sample Testcase 2

Input

8
(())((()

Output

Invalid

Sample Testcase 3

Input

6
([}{])

Output

Invalid

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110261s64MBMinimum
230511s64MBMinimum
320251s64MBMinimum
4401401s64MBMinimum
5031s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o bracket_ex -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.