Trong bài này, một biểu thức chính quy hợp lệ thuộc một trong các dạng sau. Trong các mô tả dưới đây, \(E_1,E_2,\ldots\) biểu thị các biểu thức chính quy hợp lệ (không nhất thiết khác nhau).

• Một chữ số thập phân, tức một trong 0 1 2 3 4 5 6 7 8 9.
• Phép nối: \(E_1E_2\).
• Phép tuyển: (E1|E2|...|EN) với ít nhất hai biểu thức. Cặp ngoặc ngoài là bắt buộc.
• Phép lặp: (E1)*. Cặp ngoặc ngoài là bắt buộc.

Ví dụ, 7, 23, (7)*, (45)*, (1|2|3), ((2)*|3), (1|2|3) và ((0|1))* là các biểu thức hợp lệ. Các biểu thức (7), 4|5, 4*, (1|) và (0|1)* không hợp lệ.

Ta nói biểu thức \(E\) khớp với chuỗi chữ số \(D\) khi và chỉ khi ít nhất một điều sau đúng:

• \(E=D\).
• \(E=E_1E_2\) và tồn tại \(D_1,D_2\) sao cho \(D=D_1D_2\), đồng thời \(E_i\) khớp với \(D_i\).
• \(E=(E_1|E_2|\ldots|E_N)\) và ít nhất một \(E_i\) khớp với \(D\).
• \(E=(E_1)*\) và tồn tại \(D_1,D_2,\ldots,D_N\) với một số nguyên không âm \(N\), sao cho \(D=D_1D_2\ldots D_N\) và \(E_1\) khớp với từng \(D_i\). Đặc biệt, (E1)* khớp với chuỗi rỗng.

Ví dụ, biểu thức ((1|2))*3 khớp với 3, 13, 123, 2221123 cùng nhiều chuỗi khác. Tuy nhiên, nó không khớp với 1234, 3123, 12, 33 cùng nhiều chuỗi khác.

Cho một biểu thức chính quy hợp lệ \(R\), có bao nhiêu số nguyên trong đoạn từ \(A\) đến \(B\), kể cả hai đầu, mà biểu diễn thập phân không có số 0 ở đầu của chúng khớp với \(R\)?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên dương \(A,B\), là hai đầu mút kể cả hai đầu của đoạn số nguyên cần xét. Dòng thứ hai chứa chuỗi \(R\) chỉ gồm các ký tự trong tập 0123456789()|*; \(R\) được bảo đảm là một biểu thức chính quy hợp lệ theo định nghĩa trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số số nguyên trong đoạn \([A,B]\) được biểu thức chính quy \(R\) khớp.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A\le B\le10^{18}\).
• \(1\le\operatorname{length}(R)\le30\).

Phân nhóm

• Test Set 1 (Hiển thị): \(R\) không chứa ký tự |.
• Test Set 2 (Ẩn): Không có ràng buộc bổ sung.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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)*)

Case #1: 4
Case #2: 1
Case #3: 5
Case #4: 0
Case #5: 4
Case #6: 2
Case #7: 1000000000000000000
Case #8: 6

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Integeregex.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.