Google Code Jam '16 World Finals Problem A - Integeregex

View as PDF

Submit solution


Points: 35
Time limit: 1.0s
Memory limit: 64M

Problem types

In this problem, a valid regular expression is one of the following. In the following descriptions, E_1, E_2, etc. denote (not necessarily different) valid regular expressions.

  • A decimal digit: that is, one of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  • Concatenation: E_1 E_2.
  • Disjunction: (E_1 | E_2 | \dots | E_N), for at least two expressions. Note that the outer parentheses are required.
  • Repetition: (E_1)*. Note that the outer parentheses are required.

For example, 7, 23, (7)*, (45)*, (1|2|3), ((2)*|3), (1|2|3), and ((0|1))* are valid expressions. (7), 4|5, 4*, (1|), and (0|1)* are not.

We say that an expression E matches a string of digits D if and only if at least one of the following is true:

  • E = D.
  • E = E_1 E_2 and there exist D_1 and D_2 such that D = D_1 D_2 and E_i matches D_i.
  • E = (E_1 | E_2 | \dots | E_N) and at least one of the E_i matches D.
  • E = (E_1)* and there exist D_1, D_2, \dots, D_N for some non-negative integer N such that D = D_1 D_2 \dots D_N and E_1 matches each of the D_i.

In particular, note that (E_1)* matches the empty string. For example, the expression ((1|2))*3 matches 3, 13, 123, and 2221123, among other strings. However, it does not match 1234, 3123, 12, or 33, among other strings.

Given a valid regular expression R, for how many integers between A and B, inclusive, does R match the integer's base 10 representation (with no leading zeroes)?

Input Specification

The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line has two positive integers A and B: the inclusive limits of the integer range we are interested in. The second has a string R consisting only of characters in the set 0123456789()|*, which is guaranteed to be a valid regular expression as described in the statement above.

Output Specification

For each test case, output one line containing the number of integers in the inclusive range [A, B] that the regular expression R matches.

Limits

1 \le T \le 100

1 \le A \le B \le 10^{18}

1 \le |R| \le 30

Sample Input

8
1 1000
(0)*1(0)*
379009 379009
379009
1 10000
(12)*(34)*
4 5
45
1 100
((0|1))*
1 50
(01|23|45|67|23)
1 1000000000000000000
((0|1|2|3|4|5|6|7|8|9))*
1 1000
1(56|(((7|8))*9)*)

Sample Output

4
1
5
0
4
2
1000000000000000000
6
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.