Adjacent and Consecutive

Đề bài

Hai người chơi A và B đang chơi một trò chơi. Trò chơi sử dụng N quân cờ được đánh số từ 1 đến N, cùng một bàn cờ gồm một hàng ngang duy nhất có N ô trống.

Hai người chơi luân phiên, người chơi A đi trước. Trong mỗi lượt, người chơi chọn một quân cờ chưa dùng và một ô trống, rồi đặt quân cờ vào ô đó. Khi trò chơi kết thúc, người chơi A thắng nếu có hai quân cờ mang hai số liên tiếp nằm trong hai ô kề nhau (không quan trọng ai đã đặt chúng). Nếu không, người chơi B thắng. Chẳng hạn, các bàn cờ cuối cùng 1 2 3 4 và 4 1 3 2 là những ví dụ mà người chơi A thắng, còn bàn cờ cuối cùng 3 1 4 2 là một ví dụ mà người chơi B thắng. (Lưu ý rằng hai số liên tiếp có thể xuất hiện theo bất kỳ thứ tự nào.)

Bạn vừa xem hai người chơi hoàn thành một ván, nhưng không hiểu chiến thuật của họ. Có thể họ đã không chơi hợp lý! Bạn quyết định so sánh các nước đi của họ với một chiến thuật tối ưu.

Một trạng thái thắng là trạng thái của trò chơi mà từ đó người đang đến lượt có thể đảm bảo chiến thắng nếu chơi tối ưu, bất kể đối thủ làm gì. Một sai lầm là một nước đi được thực hiện khi đang ở trạng thái thắng nhưng lại khiến đối thủ có một trạng thái thắng trong lượt kế tiếp. (Lưu ý rằng không thể mắc sai lầm ở lượt cuối của trò chơi: nếu lượt cuối bắt đầu bằng một trạng thái thắng cho người chơi đó, thì nguyên nhân bắt buộc là nước đi duy nhất của họ dẫn đến chiến thắng.)

Cho N nước đi, hãy đếm số sai lầm của mỗi người chơi.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. Sau đó là T bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên N: số quân cờ trong trò chơi (đồng thời cũng là số lượt và số ô trên bàn cờ).

Tiếp theo là N dòng. Dòng thứ i trong số này (đánh số từ 1) chứa hai số nguyên M_i và C_i. Chúng lần lượt biểu diễn quân cờ được chọn ở lượt thứ i và chỉ số ô mà quân cờ đó được đặt vào (đánh số từ 1 ở đầu bên trái đến N ở đầu bên phải).

Lưu ý rằng khi i lẻ thì đó là lượt của người chơi A, còn khi i chẵn thì đó là lượt của người chơi B.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: a b, trong đó x là số thứ tự bộ test (bắt đầu từ 1), a là tổng số sai lầm của người chơi A và b là tổng số sai lầm của người chơi B.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le M_i \le N\) với mọi i.
• \(M_i \ne M_j\) với mọi \(i \ne j\).
• \(1 \le C_i \le N\) với mọi i.
• \(C_i \ne C_j\) với mọi \(i \ne j\).

Phân nhóm

Test Set 1 (Visible Verdict)

\(4 \le N \le 10\).

Test Set 2 (Hidden Verdict)

\(4 \le N \le 50\).

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

3
6
2 2
3 5
4 3
6 6
1 4
5 1
4
4 1
1 3
3 4
2 2
4
3 1
2 2
4 3
1 4

Case #1: 2 1
Case #2: 0 0
Case #3: 0 0

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Adjacent and Consecutive.

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

Hexacoin Jam

Đề bài

Đồng tiền mã hóa đầu tiên của đội Code Jam, jamcoin, chưa bao giờ trở nên phổ biến. Năm nay, chúng tôi thử lại với hexacoin, được đặt tên theo việc sử dụng hệ cơ số 16. Để "đào" một hexacoin có \(D\) chữ số, ta phải làm việc với các số nguyên được biểu diễn bằng đúng \(D\) chữ số hệ 16, kể cả các chữ số 0 ở đầu nếu cần. Mỗi giá trị biểu diễn một số nguyên từ 0 đến \(16^D-1\), tính cả hai đầu. Theo quy ước thông thường, các chữ số hệ 16 được biểu diễn bởi các chữ số từ 0 đến 9 và các chữ cái in hoa từ A đến F. Ví dụ, F2B, 0C8 và 000 là các giá trị hợp lệ khi \(D=3\), tương ứng với các giá trị hệ 10 là 3883, 200 và 0. Ngược lại, 1234, DF, C0DE và JAM không phải là các giá trị hợp lệ khi \(D=3\).

Khi cộng các giá trị hệ 16 có \(D\) chữ số, mọi chữ số tràn đều bị bỏ đi. Nói cách khác, phép cộng được thực hiện theo modulo \(16^D\). Ví dụ, F2B + 0C8 = FF3 (4083 trong hệ 10), còn F2B + F2B = E56 (3670 trong hệ 10, vì kết quả phép cộng là 7766 và lấy modulo \(16^3\) thu được 3670).

Để "đào" một hexacoin có \(D\) chữ số, máy tính phải thực hiện các bước sau:

1. Chọn một danh sách \(L\) gồm \(N\) giá trị hệ 16 có \(D\) chữ số: \(L_1, L_2, …, L_N\).
2. Chọn một đoạn giá trị đích gồm các giá trị hệ 16 có \(D\) chữ số: các số từ \(S\) đến \(E\), tính cả hai đầu.
3. Chọn đều ngẫu nhiên một hoán vị \(P\) của 16 chữ số hệ 16 từ 0 đến F trong tất cả \(16!\) hoán vị.
4. Áp dụng \(P\) lên mọi chữ số của mọi số trong danh sách, tạo thành danh sách mới \(L'\) gồm \(N\) giá trị hệ 16 có \(D\) chữ số. Nói chính xác, chữ số thứ \(j\) của phần tử thứ \(i\) trong \(L'\) là kết quả áp dụng \(P\) lên chữ số thứ \(j\) của phần tử thứ \(i\) trong \(L\).
5. Chọn một cặp phần tử từ \(L'\) không hoàn lại, đều ngẫu nhiên trong tất cả các cách chọn có thể và độc lập với việc chọn hoán vị.
6. Tính tổng của hai phần tử được chọn (bỏ các chữ số tràn).

Nếu tổng tính được ở bước cuối nằm trong đoạn từ \(S\) đến \(E\), tính cả hai đầu, thì ta đã tìm được một hexacoin! Ví dụ, giả sử:

• \(L\) = [134, 000, FFB, 000, AA9].
• \(S\) = 85C và \(E\) = EDF.
• Máy tính tình cờ chọn \(P\) = (0 → 4, 1 → A, 2 → 2, 3 → 8, 4 → 9, 5 → B, 6 → C, 7 → 7, 8 → F, 9 → 1, A → 0, B → 3, C → 5, D → 6, E → E, F → D).

Khi áp dụng \(P\) lên \(L\), danh sách \(L'\) thu được là [A89, 444, DD3, 444, 001]. Lưu ý rằng \(P\) không được áp dụng lên \(S\) và \(E\).

Có \((5 × 4)/2=10\) cặp giá trị để chọn và mỗi cặp có xác suất \(1/10\) được chọn. Các tổng duy nhất nằm trong đoạn là A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4 và A89 + 444 = ECD (xuất hiện hai lần).

Hai bước đầu tiên đã được thực hiện và bạn biết danh sách \(L\) cùng đoạn \([S,E]\) đã được chọn. Xác suất tìm thấy một hexacoin sau khi thực hiện phần còn lại của quy trình là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm ba dòng. Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\), lần lượt là kích thước danh sách đã cho và số chữ số được sử dụng. Dòng thứ hai chứa hai số hệ 16 có \(D\) chữ số là \(S\) và \(E\), lần lượt là cận dưới và cận trên (đều được tính) của đoạn đích. Dòng cuối cùng chứa \(N\) số hệ 16 có \(D\) chữ số \(L_1,L_2,…,L_N\), biểu diễn các giá trị trong danh sách.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y và z là các số nguyên không âm sao cho phân số y/z biểu diễn xác suất tìm thấy một hexacoin trong các điều kiện đã mô tả ở trên. Tất cả x, y và z phải được viết trong hệ 10. Nếu có nhiều giá trị y và z được chấp nhận, hãy chọn các giá trị làm cho z nhỏ nhất.

Ràng buộc

• \(2 ≤ N ≤ 450\).
• \(S\) chứa đúng \(D\) ký tự.
• Mỗi ký tự của \(S\) là một chữ số hệ 16.
• \(E\) chứa đúng \(D\) ký tự.
• Mỗi ký tự của \(E\) là một chữ số hệ 16.
• \(S ≤ E\).
• \(L_i\) chứa đúng \(D\) ký tự với mọi \(i\).
• Mỗi ký tự của \(L_i\) là một chữ số hệ 16 với mọi \(i\).

Phân nhóm

Test Set 1 (phán quyết hiển thị)

• \(1 ≤ T ≤ 100\).
• \(2 ≤ D ≤ 3\).

Test Set 2 (phán quyết ẩn)

• \(1 ≤ T ≤ 100\).
• \(2 ≤ D ≤ 4\).

Test Set 3 (phán quyết ẩn)

• \(1 ≤ T ≤ 10\).
• \(2 ≤ D ≤ 5\).

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

2 2
10 10
00 FF
2 2
10 11
00 FF
4 3
FFF FFF
230 A10 010 F70
4 3
AFF FFF
230 A10 010 F70
???+ success "Output"sample
Case #1: 7 120
Case #2: 1 15
Case #3: 0 1
Case #4: 2731 8736
```

??? "Giải thích"
    ## Giải thích ví dụ

    Trong Test mẫu #1, đoạn đích chỉ gồm một giá trị duy nhất là 10. Vì kết quả kết thúc bằng 0 nên tổng các giá trị được gán cho hai chữ số cuối 0 và F cũng phải kết thúc bằng 0. Do $P[0]$ và $P[F]$ là hai giá trị khác nhau, tổng của chúng không thể bằng đúng 0. Vì vậy, $P[0]+P[F]$ phải bằng 10 (trong hệ 16). Có 7 cặp chữ số khác nhau thỏa mãn điều đó; $P[0]$ và $P[F]$ không thể đều bằng 8. Cả 7 cặp đều tạo ra tổng chung là 10 (sau khi bỏ chữ số tràn 1). Do đó, có 14 cách gán hai chữ số khác nhau cho 0 và F dẫn tới một hexacoin. Có $16 × 15$ cách gán có thể cho hai chữ số ấy, nên kết quả là $14/240=7/120$.

    Trong Test mẫu #2, ta cần cộng xác suất để kết quả bằng đúng 11 vào kết quả của Test mẫu #1. Cách duy nhất để điều đó xảy ra là 0 và F được gán lần lượt thành 0 và 1 theo một trong hai thứ tự. Xác suất của trường hợp này là $2/240=1/120$, dẫn tới tổng là $7/120+1/120=8/120=1/15$.

    Trong Test mẫu #3, hãy lưu ý rằng bất kể máy tính chọn hoán vị nào và cặp số nào trong danh sách, ta luôn cộng hai số có cùng chữ số cuối. Điều đó tạo ra một kết quả chẵn, kể cả sau khi lấy modulo $16^3$. Vì giá trị duy nhất trong đoạn là số lẻ nên trong trường hợp này không có hy vọng đào được hexacoin. Lưu ý rằng `0 2` là một cách biểu diễn đáp án không hợp lệ vì `z` chưa nhỏ nhất.

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Hexacoin Jam.

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

Lauren đang cố gắng chơi những nốt nhạc hay nhất có thể bằng một cây đàn hạc. Cây đàn hạc là một đường tròn có bán kính \(R\) xăng-ti-mét. Để chơi một nốt nhạc, một sợi dây phải được gắn vào đàn sao cho nối hai điểm gắn khác nhau trên chu vi đường tròn. Sau đó, Lauren gảy sợi dây này để chơi một nốt nhạc.

Trên chu vi cây đàn hạc có \(N\) điểm gắn dây. Điểm gắn thứ \(i\) nằm tại vị trí cách điểm ngoài cùng bên phải của chu vi \(D_i\) nanođộ theo chiều kim đồng hồ (một nanođộ bằng \(10^{-9}\) độ).

Không phải mọi điểm gắn đều dùng cùng một công nghệ để cố định dây. Điểm thứ \(i\) cần \(L_i\) xăng-ti-mét dây cho phần gắn. Một sợi dây cố định giữa hai điểm khác nhau \(i\) và \(j\) phải dài chính xác \(L_i+L_j+\operatorname{distance}(i,j)\) xăng-ti-mét. Ở đây, \(\operatorname{distance}(i,j)\) là độ dài dây cung hình học nối hai điểm, tức khoảng cách Euclid giữa chúng.

Lauren cho rằng dây càng dài thì nốt nhạc càng hay. Hỏi \(K\) sợi dây dài nhất có thể dùng với cây đàn hạc của Lauren là những sợi nào?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu mỗi bộ test chứa ba số nguyên \(N\), \(R\), \(K\): số điểm gắn, bán kính đàn tính bằng xăng-ti-mét và số độ dài dây Lauren muốn biết.

\(N\) dòng tiếp theo mô tả các điểm gắn. Dòng thứ \(i\) chứa hai số nguyên \(D_i\), \(L_i\), lần lượt là vị trí (số nanođộ theo chiều kim đồng hồ kể từ điểm ngoài cùng bên phải) và lượng dây tính bằng xăng-ti-mét cần tại điểm thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y1 y2 ... yK, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn yn là giá trị thứ \(n\) trong danh sách độ dài của tất cả \(N\times(N-1)/2\) sợi dây có thể dùng, sắp xếp theo thứ tự không tăng.

Mỗi yn được xem là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-9}\).

Ràng buộc

• \(1\le T\le100\).
• \(N=150000\) trong nhiều nhất \(10\) bộ test.
• \(5\le N\le10^4\) trong mọi bộ test có \(N\ne150000\).
• \(1\le R\le10^9\).
• \(0\le D_1\).
• \(D_i<D_{i+1}\) với mọi \(i\).
• \(D_N<360\times10^9\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• Với mỗi \(i\), \(L_i\) được chọn độc lập và ngẫu nhiên đều từ \(1\) đến \(10^9\), kể cả hai đầu.
• \(K=1\).

Test Set 2 (Phán quyết ẩn)

• \(1\le L_i\le10^9\) với mọi \(i\).
• Không có bảo đảm nào về cách sinh từng \(L_i\).
• \(K=10\).

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

5 2 1
0 3
1234567890 3
3154510113 3
180000000000 3
359999999999 3
5 10 1
90000000000 8
180000000000 7
260000000000 9
260000000001 1
260000000002 1
???+ success "Output"sample
Case #1: 10.0000000000
Case #2: 36.9238939618
```

??? "Giải thích"
    Các bộ test trên thỏa mãn ràng buộc Test Set 1. Một bộ test mẫu không thỏa mãn các ràng buộc đó nằm ở cuối phần này.

    Lưu ý: các giá trị $L_i$ trong những mẫu Test Set 1 được chọn cho dễ hiểu chứ không được sinh ngẫu nhiên. Lời giải vẫn được chạy với các mẫu này và phải cho kết quả đúng.

    Trong mẫu số 1, mọi điểm gắn có cùng giá trị, nên ta chọn cặp nối bởi dây cung dài nhất: đường kính nằm ngang dài $4$ xăng-ti-mét. Tổng độ dài cần là $4+3+3=10$ xăng-ti-mét.

    Trong mẫu số 2, điểm thứ tư và thứ năm cực kỳ gần điểm thứ ba nhưng có giá trị $L$ nhỏ hơn nhiều. Ta có thể loại chúng và tập trung vào các cách nối giữa ba điểm đầu:


    - Điểm thứ nhất và thứ hai: $10\sqrt2+8+7\approx29.142136$.
    - Điểm thứ nhất và thứ ba: $\approx19.923894+8+9\approx36.923894$.
    - Điểm thứ hai và thứ ba: $\approx12.855726+7+9\approx28.855726$.

    Nối điểm thứ nhất và thứ ba cho tổng độ dài lớn nhất.

    Bộ test bổ sung sau không thể xuất hiện trong Test Set 1 nhưng có thể xuất hiện trong Test Set 2.

    ```sample
    1
    6 1 10
    0 10
    15000000000 1
    30000000000 1
    45000000000 1
    60000000000 1
    75000000000 1
    ```

    Kết quả đúng là:

    ```sample
    Case #1: 12.2175228580 12.0000000000 11.7653668647 11.5176380902 11.2610523844 3.0000000000 2.7653668647 2.7653668647 2.5176380902 2.5176380902
    ```

    Có ba cặp điểm cùng tạo ra sợi dây dài thứ chín. Ngoài ra, các đoạn nối những cặp khác nhau có thể cắt nhau, vì Lauren mỗi lần chỉ chơi một nốt.

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Musical Cords.

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

Bạn đang cố gắng tổ chức một nhóm người trượt tuyết. Họ sẽ đến một ngọn núi lớn đã được thuê trọn ngày.

Trên núi có \(N\) điểm nghỉ được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(N-1\) dốc trượt tuyết. Mỗi dốc bắt đầu tại một điểm nghỉ và đi thẳng đến một điểm nghỉ khác, không có dốc hay điểm nghỉ trung gian. Mỗi dốc chỉ có thể được đi theo một chiều.

Mỗi người trượt tuyết bắt đầu tại điểm nghỉ trên đỉnh núi, rồi đi qua một dốc để tới một điểm nghỉ khác. Từ đó, họ có thể tiếp tục đi qua một dốc khác để tới điểm nghỉ tiếp theo, và cứ như vậy. Khi tới điểm nghỉ đích, họ ngừng trượt tuyết trong ngày và đến nhà nghỉ uống ca cao nóng. Điểm nghỉ đích không được là điểm nghỉ trên đỉnh núi. Tuy nhiên, điểm nghỉ đích có thể là đầu của không, một hoặc nhiều dốc; nói cách khác, người trượt tuyết không nhất thiết phải tiếp tục dùng các dốc còn đi được cho tới khi không còn dốc nào. Họ luôn có thể cẩn thận đi bộ xuống phần còn lại của ngọn núi! Với mỗi điểm nghỉ, có đúng một dãy các dốc mà một người có thể dùng để đi từ điểm nghỉ trên đỉnh núi tới đó.

Mỗi dốc chỉ phục vụ được một tổng số người trượt tuyết nhất định trong một ngày; sau đó, tuyết trở nên quá gồ ghề để trượt. Ngoài ra, khu nghỉ dưỡng có thể thu phí hoặc trả thưởng cho mỗi người trên từng dốc họ đi qua. Mỗi dốc có thể có một mức giá khác nhau, và mỗi người phải trả giá của từng dốc mà mình đi. Giá của một dốc có thể dương, bằng không hoặc thậm chí âm; giá âm biểu thị khoản thưởng dành cho việc thử nghiệm dốc đó. Với vai trò người tổ chức, bạn trả mọi khoản phí và nhận mọi khoản thưởng thay cho cả nhóm. Nếu nhiều người dùng cùng một dốc, bạn phải trả phí hoặc nhận thưởng của dốc đó nhiều lần.

Tổng các khoản phí bạn trả trừ đi tổng các khoản thưởng bạn nhận là tổng chi phí của chuyến đi. Chi phí này có thể dương, bằng không hoặc âm. Chi phí âm nghĩa là bạn thực sự kiếm được tiền từ chuyến đi!

Với vai trò người tổ chức, bạn muốn xác định số người trượt tuyết lớn nhất có thể đưa lên núi. Đồng thời, trong số các chuyến đi có số người lớn nhất đó, bạn muốn tìm tổng chi phí nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\): số điểm nghỉ trên núi.

Mỗi dòng trong \(N-1\) dòng cuối của một bộ test mô tả một dốc bằng bốn số nguyên \(U_i\), \(V_i\), \(S_i\) và \(C_i\). Chúng lần lượt là điểm nghỉ bắt đầu của dốc, điểm nghỉ kết thúc của dốc, số người trượt tuyết tối đa mà dốc có thể phục vụ và giá của dốc cho mỗi người.

Điểm nghỉ trên đỉnh núi, nơi mọi người bắt đầu, luôn mang số \(1\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), y là số người trượt tuyết lớn nhất và z là chi phí nhỏ nhất để y người, mỗi người trượt qua ít nhất một dốc.

Ràng buộc

• \(1 \le U_i \le N\) với mọi \(i\).
• \(2 \le V_i \le N\) với mọi \(i\). Không dốc nào có thể kết thúc tại điểm nghỉ trên đỉnh núi.
• \(U_i \ne V_i\) với mọi \(i\).
• \(1 \le S_i \le 10^5\) với mọi \(i\).
• \(-10^5 \le C_i \le 10^5\) với mọi \(i\).
• Với mọi điểm nghỉ \(r\), có đúng một dãy các dốc mà một người có thể dùng để đi từ điểm nghỉ trên đỉnh núi tới \(r\).

Phân nhóm

Test Set 1 (phản hồi kết quả đầy đủ)

• \(1 \le T \le 100\).
• \(2 \le N \le 1000\).

Test Set 2 (phản hồi kết quả ẩn)

• \(T = 17\).
• \(2 \le N \le 10^5\).

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

2
4
1 2 2 5
1 3 2 5
3 4 1 -2
7
4 7 2 2
1 3 5 5
1 4 2 -1
3 2 3 -2
3 5 2 -1
3 6 2 2

Case #1: 4 18
Case #2: 7 15

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Pack the Slopes.

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

Đề bài

Công ty Banana Rocks Inc đang phát triển một công nghệ mang tính cách mạng để thực hiện thao tác chỉnh sửa phổ biến "thay thế tất cả". Cách cài đặt của họ thay mọi lần xuất hiện của một ký tự trong một văn bản cho trước bằng một ký tự khác. (Nếu ký tự đó không xuất hiện trong văn bản thì thao tác vẫn được thực hiện, nhưng không gây ra thay đổi nào.)

Ví dụ, nếu văn bản ban đầu là CODEJAMWORLDFINALS và ta thay A bằng O, văn bản mới là CODEJOMWORLDFINOLS. Nếu tiếp tục thay O bằng Y, văn bản cuối cùng là CYDEJYMWYRLDFINYLS.

Đáng tiếc là phần cài đặt chưa hoàn chỉnh, nên nó chỉ thực hiện được các phép thay thuộc một danh sách cụ thể gồm N cặp ký tự. Ngay cả khi phép thay \(c_1\) bằng \(c_2\) đã được cài đặt, phép thay ngược từ \(c_2\) thành \(c_1\) có thể có hoặc không.

Bạn muốn thử tất cả các phép thay đã được cài đặt. Bạn được cho chuỗi S làm văn bản ban đầu và có thể thực hiện số lượng tùy ý các phép thay theo thứ tự liên tiếp: phép thứ nhất áp dụng lên S, phép thứ \((i+1)\) áp dụng lên kết quả của phép thứ \(i\). Yêu cầu duy nhất là mỗi phép thay đã cài đặt phải được thực hiện ít nhất một lần. Không có giới hạn trên cho số lần thực hiện mỗi phép.

Các ký tự được phép là chữ số thập phân, chữ cái tiếng Anh viết hoa và viết thường. Dạng viết hoa và viết thường của cùng một chữ cái được xem là hai ký tự khác nhau.

Hỏi số ký tự phân biệt lớn nhất có thể xuất hiện trong văn bản sau phép thay cuối cùng là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu T. Mỗi bộ dữ liệu gồm hai dòng. Dòng đầu chứa chuỗi S và số nguyên N: văn bản ban đầu và số phép thay đã cài đặt.

Dòng thứ hai chứa N chuỗi hai ký tự \(R_1,R_2,\ldots,R_N\). Gọi \(A_i,B_i\) lần lượt là ký tự thứ nhất và thứ hai của \(R_i\). Phép thứ \(i\) thay mọi lần xuất hiện của \(A_i\) bằng \(B_i\).

Dữ liệu ra

Với mỗi bộ dữ liệu, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ dữ liệu (bắt đầu từ 1), và y là số ký tự phân biệt lớn nhất có thể có sau khi áp dụng lên S tất cả các phép thay đã cài đặt, mỗi phép ít nhất một lần, theo một thứ tự nào đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(2 \le |S| \le 1000\).
• Mỗi ký tự của S, mỗi \(A_i\) và mỗi \(B_i\) là chữ cái tiếng Anh viết hoa, viết thường hoặc chữ số thập phân.
• \(A_i \ne B_i\) với mọi \(i\).
• \((A_i,B_i) \ne (A_j,B_j)\) với mọi \(i \ne j\); mỗi phép thay là duy nhất.

Phân nhóm

Test Set 1 (phán quyết hiển thị)

• \(2 \le N \le 62\).
• \(B_i \ne B_j\) với mọi \(i \ne j\).

Test Set 2 (phán quyết ẩn)

• \(2 \le N \le 62 \times 61\).

Đ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
CODEJAMWORLDFINALS 2
AO OY
xyz 3
xy zx yz
CJ 4
20 2O HC KS
AB 2
Ab bA

Case #1: 14
Case #2: 2
Case #3: 2
Case #4: 2

1
1234 5
12 2X X3 31 X2

Nguồn

Google Code Jam 2020, Chung kết thế giới trực tuyến, bài Replace All.

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