| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | Google Code Jam 2015 - Brattleship | 33 | 1.0s | 1G |
| 2 | Google Code Jam 2015 - Less Money, More Problems | 34 | 1.0s | 1G |
| 3 | Google Code Jam 2015 - Typewriter Monkey | 33 | 1.0s | 1G |
Bạn sắp chơi một phiên bản đơn giản của trò "bắn tàu" với cậu em trai. Bàn chơi là lưới chữ nhật có \(R\) hàng và \(C\) cột. Khi bắt đầu, bạn nhắm mắt và giữ nguyên như vậy tới cuối trò chơi. Em trai lấy một con tàu chữ nhật kích thước \(1\times W\) và đặt nằm ngang ở đâu đó trên bàn. Tàu phải luôn nằm hoàn toàn trong bàn, mỗi ô của tàu chiếm đúng một ô lưới, và không bao giờ được xoay.
Mỗi lượt, bạn gọi tên một ô trên bàn; em trai cho biết đó là trúng (ô có một phần tàu) hay trượt. (Em trai không nói bạn đã trúng phần nào của tàu, chỉ nói ô được gọi có phần tàu trong đó.) Bạn có trí nhớ hoàn hảo và theo dõi được mọi thông tin đã nhận. Khi đã gọi tên tất cả ô mà tàu chiếm, trò chơi kết thúc (tàu chìm), và điểm của bạn là số lượt đã dùng. Mục tiêu là giảm điểm này.
Dù tàu lẽ ra không được di chuyển sau khi đặt, bạn biết cậu em nghịch ngợm định gian lận: cậu có thể đổi vị trí tàu bất cứ lúc nào, miễn tàu vẫn nằm ngang, hoàn toàn trong bàn, và vị trí mới phù hợp với toàn bộ thông tin đã đưa ra trước đó.
Ví dụ, với bàn \(1\times4\) và tàu \(1\times2\), ban đầu em có thể đặt tàu phủ hai cột ngoài cùng bên trái. Nếu lượt đầu bạn đoán hàng 1, cột 2, em có thể bí mật chuyển tàu sang hai cột ngoài cùng bên phải và nói \((1,2)\) là trượt. Nhưng nếu lượt kế tiếp bạn đoán \((1,3)\), em không thể vừa nói đó cũng là trượt vừa chuyển tàu về vị trí ban đầu, vì như vậy mâu thuẫn với câu trả lời trước về \((1,2)\).
Không chỉ bạn biết em trai sẽ gian lận, em trai cũng biết rằng bạn biết. Nếu cả hai đều chơi tối ưu (bạn giảm điểm, em tăng điểm), điểm thấp nhất mà bạn có thể bảo đảm đạt được bất kể em trai làm gì là bao nhiêu?
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test là một dòng có ba số nguyên \(R\), \(C\), \(W\): số hàng, số cột của bàn và chiều rộng tàu.
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) và \(y\) là số lượt nhỏ nhất bạn có thể bảo đả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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 11/33 | 33,33% |
| Test Set 2 | 22/33 | 66,67% |
Ví dụ 1
```sample
3
1 4 2
1 7 7
2 5 1
???+ success "Output"
```sample
Case #1: 3
Case #2: 7
Case #3: 10
??? "Giải thích"
Trong Case #1, bàn có một hàng, bốn cột và tàu chiếm một hàng, hai cột. Một chiến lược tối ưu là bắt đầu bằng ô $(1,2)$.
Nếu em trai nói trúng, ô còn lại của tàu phải là $(1,1)$ hoặc $(1,3)$, và bạn chỉ cần gọi cả hai. Nếu bạn tình cờ gọi đúng ô đang chứa phần còn lại, em trai sẽ chuyển tàu sao cho $(1,2)$ vẫn trúng nhưng lần đoán mới là trượt. Lưu ý em vẫn có thể chuyển tàu sau khi đã bị bắn trúng, miễn vị trí mới không mâu thuẫn với thông tin đã cho.
Nếu em trai nói trượt, kịch bản phù hợp duy nhất còn lại là tàu ở $(1,3)$ và $(1,4)$; từ đó em không thể đổi vị trí nữa, và bạn chỉ cần gọi hai ô đó.
Vì thế, bất kể em làm gì sau khi bạn gọi $(1,2)$, bạn đều kết thúc sau nhiều nhất hai lượt nữa, tổng cộng ba lượt.
Hơn nữa, ba lượt là tối ưu vì không thể bảo đảm kết thúc trong hai lượt. Không mất tính tổng quát, xét một lượt đầu bất kỳ. Dù chọn ô nào, vẫn còn một đoạn $1\times2$ trống để em trai chuyển tàu tới và tuyên bố bạn trượt. Không thể đánh chìm con tàu chưa trúng lần nào chỉ với một lượt còn lại.
Trong Case #2, tàu lấp kín bàn nên em trai chỉ có một vị trí đặt. Bạn chỉ cần gọi mọi ô.
Trong Case #3, em trai luôn có thể chuyển tàu $1\times1$ tới một ô bạn chưa thử, nên bạn phải gọi cả 10 ô và chỉ trúng (đồng thời đánh chìm tàu) ở ô cuối cùng.
Google Code Jam 2015, Vòng 1C, bài Brattleship.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Cho tới hôm nay, quốc gia của bạn dùng \(D\) mệnh giá tiền xu nguyên dương khác nhau cho mọi giao dịch. Hôm nay, nữ hoàng nổi giận khi một thần dân nộp thuế bằng một bao tiền xu mệnh giá thấp khổng lồ, và vừa ra sắc lệnh rằng trong một lần mua không được dùng quá \(C\) đồng của bất kỳ một mệnh giá nào.
Chẳng hạn, nếu \(C=2\) và các mệnh giá hiện có là 1 và 5, ta có thể mua món hàng giá trị 11 bằng hai đồng 5 và một đồng 1, hoặc giá trị 12 bằng hai đồng 5 và hai đồng 1, nhưng không thể mua món hàng giá trị 9 hay 17.
Bạn không thể trực tiếp phản đối sắc lệnh, nhưng tình cờ lại phụ trách xưởng đúc tiền và có thể phát hành các mệnh giá mới. Bạn muốn có thể mua mọi món hàng có giá trị nguyên dương không quá \(V\) theo quy định mới. (Điều này không nhất thiết đã khả thi trước sắc lệnh.) Đồng thời, bạn muốn đưa vào ít mệnh giá mới nhất có thể, và tập hợp cuối cùng gồm cả mệnh giá cũ lẫn mới không được có phần tử trùng nhau.
Cần ít nhất bao nhiêu mệnh giá mới?
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa ba giá trị \(C\), \(D\), \(V\), sau đó là một dòng chứa \(D\) mệnh giá hiện có đôi một khác nhau, cách nhau bởi dấu cách và được sắp tăng dần.
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) và \(y\) là số mệnh giá mới ít nhất cần thê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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 11/34 | 32,35% |
| Test Set 2 | 23/34 | 67,65% |
Ví dụ 1
```sample
4
1 2 3
1 2
1 3 6
1 2 5
2 1 3
3
1 6 100
1 5 10 25 50 100
???+ success "Output"
```sample
Case #1: 0
Case #2: 1
Case #3: 1
Case #4: 3
??? "Giải thích"
Lưu ý Case #3 và #4 không nằm trong giới hạn của bộ Nhỏ.
Trong Case #1, với tối đa một đồng mỗi mệnh giá hiện có, ta đã tạo được mọi giá trị cần thiết 1, 2 và 3.
Trong Case #2, chỉ cần thêm mệnh giá 3 hoặc 4; chọn mệnh giá nào cũng chỉ cần đúng một mệnh giá mới.
Trong Case #3, lời giải tối ưu là thêm mệnh giá 1.
Google Code Jam 2015, Vòng 1C, bài Less Money, More Problems.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Nhà xuất bản của bạn quyết định dùng những con khỉ gõ bàn phím ngẫu nhiên để viết nên các tác phẩm văn học vĩ đại. Bạn giám sát một con khỉ có bàn phím gồm \(K\) phím, mỗi phím mang một chữ cái tiếng Anh viết hoa. (Nhiều phím có thể mang cùng một chữ.)
Con khỉ bắt đầu với chuỗi rỗng và lặp thao tác sau \(S\) lần: chọn đều ngẫu nhiên một phím rồi nhấn nó, thêm một bản sao chữ trên phím vào cuối chuỗi bên phải. Chuỗi cuối cùng dài \(S\).
Bạn có một từ mục tiêu dài \(L\) mà mình hy vọng con khỉ sẽ gõ. (Từ này không nhất thiết là một từ tiếng Anh thật.) Từ mục tiêu có thể xuất hiện nhiều lần trong chuỗi con khỉ gõ. Các lần xuất hiện chồng lấn cũng được tính; chẳng hạn, nếu từ mục tiêu là ABA và con khỉ gõ ABABA, chuỗi đó chứa hai lần xuất hiện.
Bạn định trả cho khỉ một quả chuối cho mỗi lần xuất hiện của từ mục tiêu. Khi đến kiểm tra, bạn mang theo số chuối ít nhất cần thiết để bảo đảm luôn đủ trả, bất kể nó đã gõ gì. Sau đó, bạn trả một quả cho mỗi lần từ mục tiêu thực sự xuất hiện và giữ lại số chuối còn thừa.
Kỳ vọng số chuối bạn giữ lại là bao nhiêu?
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa ba số nguyên dương \(K\), \(L\), \(S\). Dòng thứ hai chứa chuỗi \(K\) chữ cái tiếng Anh viết hoa mô tả bàn phím. Dòng thứ ba chứa chuỗi \(L\) chữ cái tiếng Anh viết hoa là từ mục tiêu.
Với mỗi bộ test, in một dòng Case #x: y, trong đó \(y\) là kỳ vọng số chuối bạn giữ lại sau khi trả cho khỉ.
Kết quả được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án không vượt quá \(10^{-6}\).
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.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 11/33 | 33,33% |
| Test Set 2 | 22/33 | 66,67% |
Ví dụ 1
```sample
5
7 6 6
BANANAS
MONKEY
2 3 4
AA
AAA
2 1 2
AB
B
6 2 2
GOOGLE
GO
26 11 100
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ROSENCRANTZ
???+ success "Output"
```sample
Case #1: 0.0
Case #2: 0.0
Case #3: 1.0
Case #4: 0.8888889
Case #5: 9.0
??? "Giải thích"
Lưu ý Case #5 không nằm trong giới hạn của bộ Nhỏ.
Trong Case #1, con khỉ không có cơ hội gõ từ `MONKEY` dù chỉ một lần vì bàn phím thiếu phần lớn chữ trong từ đó. Bạn không mang quả chuối nào và dĩ nhiên cũng không trả quả nào. Tội nghiệp chú khỉ!
Trong Case #2, con khỉ chắc chắn gõ `AAAA`, chứa hai lần xuất hiện chồng lấn của `AAA`. Bạn mang hai quả rồi trả cả hai.
Trong Case #3, bốn kết quả `AA`, `AB`, `BA`, `BB` có xác suất bằng nhau, mỗi kết quả là $1/4$. Chúng lần lượt chứa 0, 1, 1, 2 lần xuất hiện của từ mục tiêu. Bạn phải mang 2 quả để sẵn sàng cho trường hợp `BB`, nhưng trung bình trả $(0+1+1+2)/4=1$ quả.
Trong Case #4, xác suất ký tự đầu là `G` bằng $1/3$, và xác suất ký tự thứ hai là `O` bằng $1/3$, nên xác suất gõ `GO` là $1/9$. Bạn mang một quả và phải trao nó trong $1/9$ số lần.
Trong Case #5, về lý thuyết con khỉ có thể gõ `ROSENCRANTZ` tới chín lần, nhưng xác suất nó xuất hiện dù chỉ một lần nhỏ đến mức không đáng kể so với biên sai số được chấp nhận.
Google Code Jam 2015, Vòng 1C, bài Typewriter Monkey.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.