Đề bài

Tóm tắt: Cho một chuỗi chữ số S, hãy chèn vào đó số lượng dấu ngoặc mở và dấu ngoặc đóng ít nhất sao cho chuỗi thu được cân bằng và mỗi chữ số \(d\) nằm bên trong đúng \(d\) cặp ngoặc khớp nhau.

Ta gọi phần lồng nhau của hai dấu ngoặc trong một chuỗi là chuỗi con nằm hoàn toàn giữa chúng. Một dấu ngoặc mở và một dấu ngoặc đóng nằm bên phải nó được gọi là khớp nhau nếu phần lồng nhau của chúng rỗng, hoặc nếu mọi dấu ngoặc trong phần lồng nhau ấy đều khớp với một dấu ngoặc khác cũng nằm trong phần đó. Độ sâu lồng nhau của một vị trí \(p\) là số cặp ngoặc khớp nhau \(m\) sao cho \(p\) nằm trong phần lồng nhau của \(m\).

Ví dụ, trong các chuỗi sau, mọi chữ số đều bằng độ sâu lồng nhau tại vị trí của nó: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). Ba chuỗi đầu có độ dài nhỏ nhất trong số các chuỗi chứa cùng các chữ số theo cùng thứ tự, nhưng chuỗi cuối thì không, vì ((22)1) cũng chứa các chữ số 221 và ngắn hơn.

Cho một chuỗi chữ số S, hãy tìm một chuỗi khác \(S'\), gồm các dấu ngoặc và chữ số, thỏa mãn tất cả các điều kiện sau:

• Mỗi dấu ngoặc trong \(S'\) đều khớp với một dấu ngoặc khác.
• Xóa bất kỳ và toàn bộ dấu ngoặc khỏi \(S'\) sẽ thu được S.
• Mỗi chữ số trong \(S'\) bằng độ sâu lồng nhau tại vị trí của nó.
• \(S'\) có độ dài nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. T dòng tiếp theo, mỗi dòng biểu diễn một bộ test và chỉ chứa chuỗi S.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là chuỗi \(S'\) được định nghĩa ở trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le \lvert S \rvert \le 100\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): Mỗi ký tự trong S là 0 hoặc 1.
• Test Set 2 (phán quyết hiển thị): Mỗi ký tự trong S là một chữ số thập phân từ 0 đến 9, kể cả hai đầu mút.

Đ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ụ

4
0000
101
111000
1

Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

Nguồn

Google Code Jam 2020, Vòng loại, bài Nesting Depth.

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