DMPG '18 S1 - Mimi and Types

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mimi was writing code in C++. She was utilizing a std::tuple for some purpose. Because her definition of the data structure was very complicated, she did not want to type it every single time. So therefore she decided to use numbers to represent the type instead.

A type is valid if and only if it consists of

  • a single 0 only.
  • a single digit n\ (1\leq n\leq9) followed by exactly n valid types.

But soon, things got out of hand. Mimi wasn't sure whether some of her types were valid. Could you help her validate her types?


For all subtasks, S will be non-empty and will be at most 10^5 characters in length. All characters in S will be digits.

Subtask 1 [5%]

S will only contain 0.

Subtask 2 [15%]

S will only contain 0 and 1.

Subtask 3 [80%]

No additional constraints.

Input Specification

The first and only line of input will contain a non-empty string S consisting only of digits, representing the type.

Output Specification

The output should contain Valid if the type is valid, and Invalid if the type is invalid.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3



There are no comments at the moment.