Google Code Jam 2011 - Round 1A

Tôi đã chơi \(D\) (\(D > 0\)) ván FreeCell hôm nay. Mỗi ván FreeCell kết thúc theo một trong hai cách -- hoặc tôi thắng, hoặc tôi thua. Tôi đã chơi trong nhiều năm và cho đến nay đã chơi tổng cộng \(G\) ván (rõ ràng là \(G \ge D\)).

Vào cuối ngày, tôi xem các số liệu thống kê để xem mình đã chơi tốt như thế nào. Hóa ra tôi đã thắng chính xác \(P_D\) phần trăm trong số \(D\) ván ngày hôm nay, và chính xác \(P_G\) phần trăm trong tổng số \(G\) ván tôi từng chơi. Thật kỳ diệu, không cần phải làm tròn -- cả hai tỷ lệ phần trăm đều là con số chính xác! Thật không may, tôi không nhớ chính xác số ván tôi đã chơi hôm nay (\(D\)), hay chính xác tổng số ván tôi đã chơi (\(G\)). Tôi chỉ biết rằng tôi không thể chơi quá \(N\) ván hôm nay (\(D \le N\)).

Liệu các tỷ lệ phần trăm hiển thị có khả thi không, hay máy tính thống kê trò chơi đã bị hỏng?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo. Mỗi dòng chứa 3 số nguyên -- \(N\), \(P_D\) và \(P_G\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là "Possible" hoặc "Broken".

Ràng buộc

• \(0 \le P_D \le 100\);
• \(0 \le P_G \le 100\).

Phân nhóm

• Phân nhóm 1 (Dữ liệu nhỏ - Visible):
• \(1 \le T \le 100\);

• \(1 \le N \le 10\).

• Phân nhóm 2 (Dữ liệu lớn - Hidden):

• \(1 \le T \le 2000\);
• \(1 \le N \le 10^{15}\).

Đ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
1 100 50
10 10 100
9 80 56

Case #1: Possible
Case #2: Broken
Case #3: Possible

Nguồn

Google Code Jam 2011, Vòng 1A, bài FreeCell Statistics.

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 chơi một trò chơi với một bộ bài đặc biệt. Mỗi lá bài có ba chỉ số thưởng: thưởng rút bài c, thưởng điểm s, và thưởng lượt đi t. Một số lá bài bắt đầu trong tay bạn, trong khi những lá còn lại nằm trong một chồng bài trên bàn. Bạn bắt đầu với một lượt đi.

Trong mỗi lượt, bạn có thể chọn bất kỳ lá bài nào từ tay mình và đánh nó. Nếu lá bài đó có các chỉ số thưởng c, s, t, các điều sau sẽ xảy ra:

• Lá bài đó bị loại khỏi tay bạn và không bao giờ có thể sử dụng lại.
• Bạn rút c lá bài đầu tiên từ chồng bài vào tay mình. Nếu chồng bài có ít hơn c lá, bạn rút tất cả số bài còn lại.
• Tổng điểm của bạn tăng thêm s.
• Số lượt đi còn lại của bạn tăng thêm t.

Nếu bạn không còn lá bài nào trong tay khi bắt đầu một lượt, thì không có gì xảy ra trong lượt đó. Mục tiêu của bạn là đạt được số điểm cao nhất có thể trước khi hết lượt đi.

Ví dụ, giả sử tay và chồng bài của bạn chứa các lá bài sau:

         +---+---+---+            +---+---+---+
   HAND: | c | s | t |      DECK: | c | s | t |
         +---+---+---+            +---+---+---+
Card #1: | 0 | 0 | 2 |   Card #4: | 1 | 1 | 0 |
Card #2: | 0 | 5 | 0 |   Card #5: | 0 | 1 | 1 |
Card #3: | 2 | 1 | 1 |   Card #6: | 2 | 2 | 0 |
         +---+---+---+            +---+---+---+

Bảng dưới đây cho thấy cách bạn có thể đạt được số điểm là 8 từ những lá bài này. Ba cột đầu tiên hiển thị bài trên tay, số lượt còn lại và số điểm của bạn trước khi đánh mỗi lá bài, và cột cuối cùng hiển thị lá bài được chọn để đánh.

+---------+------------+-------+------+
| Hand    | Turns left | Score | Play |
+---------+------------+-------+------+
| 1, 2, 3 |      1     |   0   |   1  |
| 2, 3    |      2     |   0   |   3  |
| 2, 4, 5 |      2     |   1   |   2  |
| 4, 5    |      1     |   6   |   5  |
| 4       |      1     |   7   |   4  |
| 6       |      0     |   8   |   -  |
+---------+------------+-------+------+

Như bạn có thể thấy, các phần thưởng rút bài và phần thưởng lượt đi cho phép bạn tạo ra một chuỗi các lá bài liên tiếp trước khi phải dừng lại.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo.

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa N, số lượng lá bài trong tay bạn. N dòng tiếp theo, mỗi dòng chứa ba số nguyên c, s, và t, đại diện cho các chỉ số thưởng của một lá bài trong tay bạn.

Tiếp theo là một dòng chứa M, số lượng lá bài trong chồng bài. M dòng tiếp theo, mỗi dòng chứa ba số nguyên c, s, và t, đại diện cho các chỉ số thưởng của một lá bài trong chồng bài. Các lá bài này được liệt kê theo đúng thứ tự mà bạn sẽ rút chúng.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: S", trong đó S là số điểm lớn nhất bạn có thể đạt được trước khi hết lượt đi.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N\).
• \(0 \le M\).
• \(N + M \le 80\).

Phân nhóm

• Test set 1 (Visible):

  • \(0 \le c \le 1\).
  • \(0 \le s \le 20\).
  • \(0 \le t \le 20\).

• Test set 2 (Hidden):

  • \(0 \le c \le 2\).
  • \(0 \le s \le 50\).
  • \(0 \le t \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ụ

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

Case #1: 6
Case #2: 8

Nguồn

Google Code Jam 2011, Vòng 1A, bài Pseudominion.

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 chơi Hangman với người bạn Sean. Mặc dù bạn từng nghe rằng Sean rất giỏi lấy kẹo của trẻ con, cậu ấy lại không giỏi trò chơi này. Liệu bạn có thể tận dụng chiến thuật chưa hoàn hảo của Sean để khiến cậu ấy thua đậm nhất có thể không?

Hangman được chơi như sau:

 +--+
 |  O
 | /|\       Mystery word: _ a _ a _ a _
 | / \
 |
+-+---+

• Có một từ điển \(D\) gồm tất cả các từ hợp lệ mà cả bạn và Sean đều biết. Mỗi từ chỉ gồm các ký tự a–z; đặc biệt, từ không chứa dấu cách.
• Bạn bắt đầu bằng cách chọn một từ bất kỳ trong \(D\) rồi viết nó lên bảng, thay mỗi chữ cái bằng một ô trống _.
• Trong lượt của mình, Sean có thể chọn một chữ cái và hỏi chữ đó có nằm trong từ hay không. Nếu có, bạn phải mở tất cả các vị trí chứa chữ cái ấy. Nếu không, Sean mất một điểm.
• Vòng chơi kết thúc khi tất cả các chữ cái trong từ đã được mở.
• Vòng chơi không bao giờ kết thúc sớm, bất kể Sean đã mất bao nhiêu điểm.

Sean dùng một chiến thuật rất đơn giản. Cậu lập một danh sách \(L\) chứa 26 chữ cái theo một thứ tự nào đó và lần lượt xét từng chữ cái. Nếu tồn tại ít nhất một từ trong \(D\) vừa (a) chứa chữ cái đang xét, vừa (b) phù hợp với những gì bạn đã viết trên bảng cho đến lúc đó và với kết quả của tất cả các lần đoán trước của Sean, thì Sean sẽ đoán chữ cái ấy. Nếu không, cậu bỏ qua nó. Dù trường hợp nào xảy ra, Sean cũng chuyển sang chữ cái tiếp theo trong danh sách.

Với danh sách của Sean, bạn nên chọn từ nào để khiến Sean mất nhiều điểm nhất có thể? Nếu có nhiều lựa chọn tốt như nhau, hãy chọn từ xuất hiện sớm nhất trong \(D\).

Ví dụ minh họa

Giả sử Sean quyết định đoán các chữ cái theo thứ tự bảng chữ cái, tức \(L =\) abcdefghijklmnopqrstuvwxyz, và \(D\) chứa các từ banana, caravan, pajamas. Nếu bạn chọn pajamas, ván chơi diễn ra như sau:

• Bạn bắt đầu bằng cách viết 7 ô trống _ _ _ _ _ _ _ lên bảng. Dựa vào số ô trống, Sean biết ngay từ cần đoán chỉ có thể là caravan hoặc pajamas.
• Sean bắt đầu bằng việc đoán a vì đây là chữ cái đầu tiên trong \(L\), và bạn mở tất cả vị trí của a trên bảng: _ a _ a _ a _.
• Sean bỏ qua b dù chữ này xuất hiện trong banana, vì cậu đã biết đó không phải từ của bạn.
• Sau đó cậu đoán c vì chữ này xuất hiện trong caravan. Tuy nhiên, nó không xuất hiện trong từ bạn thực sự chọn, nên Sean mất một điểm và không có chữ nào được mở thêm.
• Bằng phương pháp loại trừ, lúc này Sean biết từ của bạn buộc phải là pajamas, nên cậu lần lượt đoán j, m, p, s mà không mất thêm điểm nào.

Vì vậy, Sean mất một điểm nếu bạn chọn pajamas. Nếu chọn một trong hai từ còn lại, cậu sẽ đoán được mà không mất điểm nào.

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 bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(M\), lần lượt là số từ trong từ điển và số danh sách cần xét.

\(N\) dòng tiếp theo chứa các từ trong từ điển, mỗi dòng một từ: \(D_1, D_2, \ldots, D_N\). Mỗi từ là một chuỗi tùy ý gồm các ký tự a–z.

\(M\) dòng cuối chứa tất cả các danh sách Sean sẽ sử dụng, mỗi dòng một danh sách: \(L_1, L_2, \ldots, L_M\). Mỗi danh sách dài đúng 26 chữ cái và chứa mỗi chữ cái đúng một lần. Sean sẽ dùng các danh sách này để đoán chữ theo cách đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: w1 w2 ... wM, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), và \(w_i\) là từ bạn nên chọn nếu Sean đoán các chữ cái theo thứ tự \(L_i\). Nếu nhiều từ khiến Sean mất cùng số điểm, hãy chọn từ xuất hiện sớm nhất trong từ điển.

Ràng buộc

• \(1 \le T \le 10\).
• Mỗi từ trong \(D\) có độ dài từ 1 đến 10, kể cả hai đầu mút.
• Trong cùng một bộ test, không có hai từ nào giống nhau.

Phân nhóm

• Test Set 1 (Nhìn thấy): \(1 \le N \le 100\), \(1 \le M \le 10\).
• Test Set 2 (Ẩn): \(1 \le N \le 10000\), \(1 \le M \le 100\).

Đ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
3 2
banana
caravan
pajamas
abcdefghijklmnopqrstuvwxyz
etaoisnhrdlcumwfgypbvkjxqz
4 1
potato
tomato
garlic
pepper
zyxwvutsrqponmlkjihgfedcba

Case #1: pajamas caravan
Case #2: garlic

Nguồn

Google Code Jam 2011, Vòng 1A, bài The Killer Word.

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