BOI 2015 - Ngày 1

Byteasar yêu thích cả bowling lẫn thống kê. Anh đã ghi lại kết quả của một số ván bowling trước đây. Thật không may, một số ký tự trong các ghi chép đã bị nhòe và không thể đọc được. Byteasar nhờ bạn viết chương trình tính số ván đấu khác nhau phù hợp với các ghi chép của anh.

Luật bowling

Một ván bowling gồm \(n\) lượt: \(n-1\) lượt thường và một lượt cuối. Trong một ván đấu thông thường, \(n=10\). Khi bắt đầu mỗi lượt, \(10\) ki được dựng thẳng ở cuối đường băng; người chơi được ném bóng tối đa hai lần, hoặc ba lần đối với lượt cuối, để cố gắng làm đổ càng nhiều ki càng tốt. Mỗi lượt được biểu diễn bằng hai ký tự nếu là lượt thường, hoặc ba ký tự nếu là lượt cuối.

Với mỗi lần ném, người chơi nhận được số điểm cơ bản bằng số ki bị làm đổ trong lần ném đó. Điểm cơ bản của một lượt là tổng điểm cơ bản của các lần ném trong lượt. Nếu làm đổ cả \(10\) ki trong một lượt thường, tức là đạt \(10\) điểm cơ bản, người chơi còn được nhận điểm thưởng.

Các quy tắc cho một lượt thường như sau:

• Nếu làm đổ cả \(10\) ki ngay trong lần ném đầu tiên, người chơi đạt một strike và lượt đó kết thúc. Điểm thưởng là tổng điểm cơ bản của hai lần ném tiếp theo. Một strike được ký hiệu là x-.
• Nếu cần cả hai lần ném để làm đổ hết \(10\) ki, người chơi đạt một spare. Điểm thưởng là điểm cơ bản của lần ném tiếp theo. Một spare được ký hiệu là A/, trong đó A là chữ số chỉ số ki bị làm đổ ở lần ném đầu tiên của lượt.
• Nếu sau cả hai lần ném chỉ có nhiều nhất \(9\) ki bị làm đổ, người chơi chỉ nhận điểm cơ bản. Lượt này được ký hiệu là AB, trong đó A và B lần lượt là các chữ số chỉ số ki bị làm đổ trong lần ném thứ nhất và thứ hai, với \(A+B<10\).

Điểm thưởng được cộng vào điểm của lượt đạt strike hoặc spare, mặc dù số điểm thưởng cụ thể phụ thuộc vào những lần ném trong các lượt sau.

Đối với lượt cuối, ban đầu người chơi được ném hai lần. Nếu sau hai lần ném chỉ có nhiều nhất \(9\) ki bị làm đổ, lượt đó kết thúc. Ngược lại, nếu hai lần ném đầu tạo thành một spare hoặc lần ném đầu là một strike, người chơi được ném lần thứ ba. Mỗi khi làm đổ hết số ki đang đứng trong bất kỳ lần ném nào, các ki được dựng lại như ban đầu cho lần ném tiếp theo. Điểm của lượt cuối là tổng số ki bị làm đổ; các strike và spare trong lượt này không mang lại điểm thưởng.

Có bảy dạng biểu diễn lượt cuối, trong đó A và B là các chữ số:

• xxx: ba strike liên tiếp; được \(30\) điểm.
• xxA: hai strike liên tiếp, sau đó làm đổ \(A\) ki; được \(20+A\) điểm.
• xA/: một strike, sau đó là một spare với \(A\) ki bị làm đổ ở lần ném đầu của spare; được \(20\) điểm.
• xAB: một strike, sau đó là hai lần ném làm đổ lần lượt \(A\) và \(B\) ki, với \(A+B<10\); được \(10+A+B\) điểm.
• A/x: một spare với \(A\) ki bị làm đổ ở lần ném đầu, sau đó là một strike; được \(20\) điểm.
• A/B: một spare với \(A\) ki bị làm đổ ở lần ném đầu, sau đó làm đổ \(B\) ki ở lần ném cuối; được \(10+B\) điểm.
• AB-: hai lần ném làm đổ lần lượt \(A\) và \(B\) ki, với \(A+B<10\); được \(A+B\) điểm.

Mỗi ván đấu được mô tả bằng một xâu gồm \(2n+1\) ký tự. Khi ván đấu kết thúc, có thể tính tổng điểm tích lũy sau từng lượt.

Dữ liệu vào

Dòng đầu chứa số nguyên \(q\) (\(1\le q\le25\)), là số trường hợp cần xét. Tiếp theo là \(3q\) dòng; mỗi trường hợp được mô tả bằng ba dòng:

• Dòng thứ nhất chứa số nguyên \(n\) (\(2\le n\le10\)), là số lượt.
• Dòng thứ hai chứa xâu gồm \(2n+1\) ký tự mô tả ván đấu trong ghi chép của Byteasar. Mỗi ký tự bị nhòe được thay bằng ?.
• Dòng thứ ba chứa \(n\) số nguyên cách nhau bởi dấu cách, là tổng điểm tích lũy sau từng lượt. Với mỗi số, hoặc tất cả các chữ số đều đọc được, hoặc tất cả đều bị nhòe. Số bị nhòe hoàn toàn được thay bằng -1.

Dữ liệu ra

In \(q\) dòng, mỗi dòng ứng với một trường hợp theo đúng thứ tự đầu vào. Trên mỗi dòng, in một số nguyên là số ván đấu khác nhau phù hợp với trường hợp đó.

Hai ván đấu được coi là khác nhau khi và chỉ khi chúng khác nhau ở ít nhất một lần ném, tức là hai xâu mô tả gồm \(2n+1\) ký tự của chúng khác nhau. Dữ liệu bảo đảm mỗi trường hợp có ít nhất một ván đấu phù hợp và kết quả biểu diễn được bằng số nguyên có dấu \(64\) bit.

Phân nhóm

Các điều kiện dưới đây áp dụng cho từng trường hợp trong một bộ dữ liệu.

1. 16 điểm: xâu đầu vào có nhiều nhất sáu ký tự ?.
2. 17 điểm: kết quả không vượt quá \(10^9\).
3. 26 điểm: không có ván đấu nào phù hợp với dữ liệu vào mà xâu mô tả chứa ký tự x hoặc /.
4. 23 điểm: xâu đầu vào kết thúc bằng 00-, tức là người chơi được \(0\) điểm ở lượt cuối; đồng thời \(\min(3,n)\) số cuối cùng trên dòng thứ ba của trường hợp đó đều bằng -1.
5. 18 điểm: không có ràng buộc bổ sung.

Ví dụ

2
10
08x-7/2/x?x-23??1/???
8 -1 40 60 82 97 102 110 120 140
5
x-x-23?/00-
22 37 42 52 52

9
10

25
2
0000-
0 0
2
0000?
-1 -1
2
?0?0?
-1 -1
2
??12?
-1 -1
2
????/
-1 25
2
????x
-1 25
2
????-
-1 21
2
????0
-1 -1
2
??0?0
-1 -1
2
12?x?
-1 -1
2
34?/2
-1 -1
2
11?9?
-1 -1
2
x-?0-
-1 14
2
x-???
10 -1
2
x-???
-1 60
2
x-?0-
-1 -1
2
3/?/?
15 -1
2
00???
0 -1
2
?????
-1 -1
2
??x??
2 -1
2
x-??-
-1 26
2
?????
1 -1
2
?/???
10 -1
2
0???0
-1 -1
2
0???0
11 -1

1
1
210
66
60
60
40
1386
66
11
10
3
1
1
1
10
11
241
15906
228
9
482
210
231
1

Byteasar là một lập trình viên đang phát triển một trình soạn thảo văn bản mang tính cách mạng. Trình soạn thảo có hai loại thao tác: chỉnh sửa văn bản và hoàn tác các thao tác đã thực hiện. Một tính năng mới của nó là hoàn tác nhiều cấp.

Thao tác chỉnh sửa văn bản được coi là thao tác cấp \(0\). Thao tác hoàn tác cấp \(i\), với \(i=1,2,\ldots\), hoàn tác thao tác gần nhất chưa bị hoàn tác và có cấp không vượt quá \(i-1\). Chẳng hạn, hoàn tác cấp \(1\) chỉ có thể hoàn tác thao tác chỉnh sửa; còn hoàn tác cấp \(2\) có thể hoàn tác thao tác chỉnh sửa hoặc thao tác hoàn tác cấp \(1\), nhưng không thể hoàn tác các thao tác có cấp lớn hơn.

Cụ thể hơn, mỗi thao tác đã thực hiện có một trong hai trạng thái: đang có hiệu lực hoặc đã bị hoàn tác. Ngay sau khi thực hiện một thao tác \(X\), nó ở trạng thái đang có hiệu lực. Nếu \(X\) là thao tác hoàn tác cấp \(i\), ta tìm thao tác gần nhất đang có hiệu lực và có cấp không vượt quá \(i-1\), gọi là \(X_1\), rồi đổi trạng thái của \(X_1\) thành đã bị hoàn tác. Nếu \(X_1\) cũng là một thao tác hoàn tác, ta phải khôi phục hiệu lực của thao tác mà \(X_1\) từng hoàn tác, gọi là \(X_2\). Tiếp tục theo cách đó: mỗi khi trạng thái của một thao tác hoàn tác \(X_j\) thay đổi, trạng thái của thao tác \(X_{j+1}\) mà nó từng hoàn tác cũng phải đổi theo. Điều này có thể tiếp tục làm thay đổi trạng thái của các thao tác khác. Chuỗi thay đổi kết thúc khi gặp một thao tác chỉnh sửa.

Để đơn giản, nội dung hiện tại của trình soạn thảo được biểu diễn bằng một số nguyên \(s\), gọi là trạng thái trình soạn thảo. Ban đầu \(s=0\). Mỗi thao tác chỉnh sửa chỉ định trạng thái mà nó tạo ra. Trạng thái trình soạn thảo được xác định bởi thao tác chỉnh sửa gần nhất đang có hiệu lực; nếu không có thao tác chỉnh sửa nào đang có hiệu lực thì trạng thái là \(0\).

Hãy giúp Byteasar viết chương trình theo dõi trạng thái trình soạn thảo.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n\), là số thao tác Byteasar thực hiện.

\(n\) dòng tiếp theo mô tả các thao tác theo thứ tự thực hiện. Dòng thứ \(i\) trong số đó chứa một số nguyên \(a_i\) (\(-n\le a_i\le n\), \(a_i\ne0\)):

• Nếu \(a_i>0\), đây là thao tác chỉnh sửa đặt trạng thái trình soạn thảo thành \(a_i\).
• Nếu \(a_i<0\), đây là thao tác hoàn tác cấp \(-a_i\).

Dữ liệu bảo đảm với mỗi thao tác hoàn tác, luôn tồn tại một thao tác đang có hiệu lực ở cấp nhỏ hơn để hoàn tác.

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) chứa một số nguyên là trạng thái trình soạn thảo sau khi thực hiện \(i\) thao tác đầu tiên trong dữ liệu vào.

Ràng buộc

• \(1\le n\le300\,000\).
• \(-n\le a_i\le n\) và \(a_i\ne0\) với mọi \(1\le i\le n\).

Phân nhóm

Ký hiệu \(E_s\) là thao tác chỉnh sửa đặt trạng thái thành \(s\), còn \(U_i\) là thao tác hoàn tác cấp \(i\).

1. 20 điểm: \(n\le5000\).
2. 15 điểm: \(n\le300\,000\) và chỉ có các thao tác chỉnh sửa \(E_i\) cùng thao tác hoàn tác cấp \(1\), \(U_1\).
3. 28 điểm: \(n\le300\,000\); chỉ giá trị cuối cùng trong dãy kết quả được chấm đúng sai. Tuy nhiên, vẫn phải in đủ \(n\) số và \(n-1\) số đầu phải là các số nguyên trong đoạn từ \(0\) đến \(n\).
4. 37 điểm: \(n\le300\,000\).

Ví dụ

11
1
2
5
-1
-1
-3
4
-2
-1
-1
1

1
2
5
2
1
2
4
2
1
0
1

Chính phủ Byteland quyết định đã đến lúc kết nối đất nước nhỏ bé của mình với Internet, để mọi người dân có thể tham gia các cuộc thi lập trình và xem video mèo dễ thương. Công ty Internet Optimists Inc. được giao xây dựng mạng trục nối tất cả \(n\) máy tính của Byteland. Các kết nối trực tiếp được đặt giữa từng cặp máy tính sao cho giữa hai máy tính bất kỳ đều có một dãy kết nối nối chúng với nhau.

Byteland không phải một đất nước giàu có, nên để giảm chi phí, mạng được xây dựng dưới dạng một cây, tức là có đúng \(n-1\) kết nối trực tiếp. Mãi về sau người ta mới nhận ra một nhược điểm nghiêm trọng: chỉ cần một kết nối bị đứt, mạng sẽ bị chia cắt, khiến một số máy tính không thể liên lạc với nhau!

Để tăng độ tin cậy, chính phủ quyết định mạng phải chịu được sự cố đứt một kết nối bất kỳ. Hãy giúp Internet Optimists Inc. cải thiện mạng với chi phí thấp nhất. Biết \(n-1\) cặp máy tính đang được nối trực tiếp, hãy tìm số kết nối ít nhất cần thêm để mạng vẫn liên thông khi bất kỳ một kết nối nào bị đứt, đồng thời chỉ ra các kết nối cần thêm.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(n\ge3\)), là số máy tính của Byteland. Các máy tính được đánh số từ \(1\) đến \(n\).

Mỗi dòng trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(a,b\) (\(1\le a,b\le n\), \(a\ne b\)), mô tả một kết nối trực tiếp giữa máy tính \(a\) và máy tính \(b\). Các kết nối này tạo thành một cây.

Dữ liệu ra

Dòng đầu chứa số nguyên \(k\), là số kết nối ít nhất cần thêm vào mạng.

Mỗi dòng trong \(k\) dòng tiếp theo chứa hai số nguyên \(a,b\) (\(1\le a,b\le n\), \(a\ne b\)), là hai máy tính cần nối bằng một kết nối mới. Có thể in các kết nối theo thứ tự bất kỳ. Nếu có nhiều phương án, hãy in một phương án bất kỳ.

Sau khi thêm các kết nối đã in, mạng phải vẫn liên thông nếu bất kỳ một kết nối nào bị đứt.

Ràng buộc

• \(3\le n\le500\,000\).
• \(1\le a,b\le n\) và \(a\ne b\) với mỗi kết nối.

Phân nhóm

1. 18 điểm: \(n\le10\).
2. 45 điểm: \(n\le2000\).
3. 37 điểm: \(n\le500\,000\).

Ví dụ

6
1 2
2 3
2 4
5 4
6 4

2
1 5
3 6

8
1 2
2 3
3 4
4 5
3 6
3 7
3 8

3
1 6
5 7
8 4