Google Code Jam 2014 - Qualification Round

Giới thiệu

Cookie Clicker là một trò chơi Javascript của Orteil, nơi người chơi nhấp vào hình ảnh một chiếc bánh quy khổng lồ. Nhấp vào bánh quy sẽ giúp họ có thêm bánh quy. Họ có thể dùng số bánh quy đó để mua các tòa nhà. Những tòa nhà này giúp họ kiếm được nhiều bánh quy hơn nữa. Giống như bài toán này, trò chơi tập trung rất nhiều vào bánh quy. Bài toán này có ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi Cookie Clicker. Làm ơn đừng đi chơi nó bây giờ: có thể sẽ rất lâu sau bạn mới quay lại được đấy.

Đề bài

Trong bài toán này, bạn bắt đầu với 0 bánh quy. Bạn nhận được bánh quy với tốc độ 2 chiếc mỗi giây bằng cách nhấp vào một chiếc bánh quy khổng lồ. Bất cứ khi nào bạn có ít nhất \(C\) bánh quy, bạn có thể mua một trang trại bánh quy (cookie farm). Mỗi khi bạn mua một trang trại, bạn tốn \(C\) bánh quy và nó giúp bạn tăng thêm \(F\) bánh quy mỗi giây.

Khi bạn có \(X\) bánh quy mà bạn chưa dùng để mua trang trại, bạn thắng! Hãy tính toán xem sẽ mất bao lâu để bạn thắng nếu bạn sử dụng chiến thuật tối ưu nhất.

Ví dụ

Giả sử \(C=500.0\), \(F=4.0\) và \(X=2000.0\). Đây là cách chiến thuật tối ưu diễn ra:

1. Bạn bắt đầu với 0 bánh quy, sản xuất 2 bánh quy mỗi giây.
2. Sau 250 giây, bạn sẽ có \(C=500\) bánh quy và có thể mua một trang trại sản xuất \(F=4\) bánh quy mỗi giây.
3. Sau khi mua trang trại, bạn có 0 bánh quy, và tổng tốc độ sản xuất bánh quy của bạn là 6 chiếc mỗi giây.
4. Trang trại tiếp theo sẽ tốn 500 bánh quy, bạn có thể mua sau khoảng 83.3333333 giây.
5. Sau khi mua trang trại thứ hai, bạn có 0 bánh quy, và tổng tốc độ sản xuất là 10 chiếc mỗi giây.
6. Một trang trại khác sẽ tốn 500 bánh quy, bạn có thể mua sau 50 giây.
7. Sau khi mua trang trại thứ ba, bạn có 0 bánh quy, và tổng tốc độ sản xuất là 14 chiếc mỗi giây.
8. Một trang trại nữa sẽ tốn 500 bánh quy, nhưng thực tế việc không mua nó lại hợp lý hơn: thay vào đó bạn chỉ cần đợi cho đến khi có \(X=2000\) bánh quy, mất khoảng 142.8571429 giây.

Tổng thời gian: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 giây.

Lưu ý rằng bạn nhận được bánh quy liên tục: vì vậy 0.1 giây sau khi trò chơi bắt đầu, bạn sẽ có 0.2 bánh quy, và \(\pi\) giây sau khi bắt đầu, bạn sẽ có \(2\pi\) bánh quy.

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 ba số thực cách nhau bởi khoảng trắng: \(C\), \(F\) và \(X\), ý nghĩa của chúng đã được mô tả ở trên.

\(C\), \(F\) và \(X\) mỗi số sẽ bao gồm ít nhất 1 chữ số, theo sau là 1 dấu thập phân và từ 1 đến 5 chữ số sau dấu thập phân. Sẽ không có số 0 ở đầu.

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à số giây tối thiểu để bạn có thể có \(X\) chiếc bánh quy ngon lành.

Chúng tôi khuyên bạn nên xuất y đến 7 chữ số thập phân, nhưng không bắt buộc. y sẽ được coi là chính xác nếu nó đủ gần với con số chính xác: trong phạm vi sai số tuyệt đối hoặc tương đối là \(10^{-6}\).

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset: \(1 \le C \le 500\); \(1 \le F \le 4\); \(1 \le X \le 2000\).
• Large dataset: \(1 \le C \le 10000\); \(1 \le F \le 100\); \(1 \le X \le 100000\).

Đ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
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0

Case #1: 1.0000000
Case #2: 39.1666667
Case #3: 63.9680013
Case #4: 526.1904762

Nguồn

Google Code Jam 2014, Vòng loại, bài Cookie Clicker Alpha.

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

Đây là bài toán khó hiểu nhất trong vòng này. Nếu bạn là người mới tham gia Code Jam, bạn nên thử giải các bài toán khác trước.

Naomi và Ken thỉnh thoảng chơi trò chơi cùng nhau. Trước khi chơi, mỗi người nhận được \(N\) khối gỗ trông giống hệt nhau với khối lượng nằm trong khoảng từ \(0.0\)kg đến \(1.0\)kg (không bao gồm hai đầu mút). Tất cả các khối gỗ đều có trọng lượng khác nhau. Có rất nhiều trò chơi họ có thể chơi với những khối gỗ đó, nhưng họ thường chơi một trò gọi là War (Chiến tranh). Đây là cách trò War hoạt động:

1. Mỗi người chơi cân từng khối gỗ của mình, vì vậy mỗi người đều biết trọng lượng của tất cả các khối gỗ của mình, nhưng không biết trọng lượng các khối gỗ của người kia.
2. Họ lặp lại quy trình sau \(N\) lần:
   1. Naomi chọn một trong các khối gỗ của mình, có khối lượng Chosen_Naomi.
   2. Naomi nói cho Ken biết khối lượng của khối gỗ cô ấy đã chọn.
   3. Ken chọn một trong các khối gỗ của mình, có khối lượng Chosen_Ken.
   4. Mỗi người đặt khối gỗ của mình lên một bên của một chiếc cân bàn, và người có khối gỗ nặng hơn sẽ được một điểm.
   5. Cả hai khối gỗ đều bị tiêu hủy trong một đám cháy.

Naomi đã nhận ra ba điều về trò War. Thứ nhất, cô ấy nhận ra mình thua rất nhiều. Thứ hai, cô ấy nhận ra rằng có một chiến thuật duy nhất mà Ken có thể tuân theo để tối đa hóa điểm số của anh ấy mà không cần giả định bất cứ điều gì về chiến thuật của Naomi, và Ken luôn sử dụng nó. Thứ ba, cô ấy nhận ra rằng mình ghét thua cuộc. Naomi đã quyết định rằng thay vì chơi War, cô ấy sẽ chơi một trò chơi mà cô ấy gọi là Deceitful War (Chiến tranh Gian lận). Điều tuyệt vời về Deceitful War là Ken sẽ nghĩ rằng họ đang chơi War!

Dưới đây là cách Deceitful War hoạt động, với những điểm khác biệt giữa Deceitful War và War được in đậm:

1. Mỗi người chơi cân từng khối gỗ của mình. Naomi cũng cân các khối gỗ của Ken trong khi anh ấy không nhìn, vì vậy Naomi biết trọng lượng của tất cả các khối gỗ và Ken chỉ biết trọng lượng các khối gỗ của mình.
2. Họ lặp lại quy trình sau \(N\) lần:
   1. Naomi chọn một trong các khối gỗ của mình, có khối lượng Chosen_Naomi.
   2. Naomi nói với Ken một con số, Told_Naomi, nằm trong khoảng từ \(0.0\)kg đến \(1.0\)kg (không bao gồm hai đầu mút). Ken, người nghĩ rằng họ đang chơi War, nghĩ rằng con số Naomi vừa nói với anh ấy là Chosen_Naomi.
   3. Ken chọn một trong các khối gỗ của mình, có khối lượng Chosen_Ken.
   4. Mỗi người đặt khối gỗ của mình lên một bên của một chiếc cân bàn, và người có khối gỗ nặng hơn sẽ được một điểm.
   5. Cả hai khối gỗ đều bị tiêu hủy trong một đám cháy.

Naomi không muốn Ken biết rằng cô ấy không chơi War; vì vậy khi cô ấy chọn khối gỗ để chơi và khối lượng để nói với Ken, cô ấy phải đảm bảo rằng chiếc cân bàn sẽ không tiết lộ rằng Chosen_Naomi \(\neq\) Told_Naomi. Nói cách khác, cô ấy phải đưa ra quyết định sao cho:

• Chosen_Naomi > Chosen_Ken khi và chỉ khi Told_Naomi > Chosen_Ken, và
• Told_Naomi không bằng khối lượng của bất kỳ khối gỗ nào của Ken, vì anh ấy biết điều đó là không thể.

Có vẻ như Naomi sẽ không giành thêm được điểm nào bằng cách gian lận, vì Ken có thể phát hiện ra cô ấy không chơi War; nhưng Naomi biết Ken nghĩ cả hai người chơi đang chơi War, và cô ấy biết những gì anh ấy biết, và cô ấy biết Ken sẽ luôn tuân theo chiến thuật tối ưu duy nhất của anh ấy cho trò War, vì vậy cô ấy luôn có thể dự đoán anh ấy sẽ chơi gì.

Bạn sẽ được cung cấp khối lượng của các khối gỗ mà Naomi và Ken bắt đầu. Naomi sẽ chơi Deceitful War một cách tối ưu để giành được số điểm tối đa. Ken sẽ chơi War một cách tối ưu để giành được số điểm tối đa giả định rằng cả hai người chơi đang chơi War. Điểm của Naomi sẽ là bao nhiêu? Điểm của cô ấy sẽ là bao nhiêu nếu cô ấy chơi War một cách tối ưu?

Ví dụ

Nếu mỗi người chơi còn một khối gỗ duy nhất, trong đó Naomi có \(0.5\)kg và Ken có \(0.6\)kg, thì Ken chắc chắn sẽ ghi điểm. Naomi không thể nói số của mình \(\ge 0.6\)kg, nếu không Ken sẽ biết cô ấy không chơi War khi chiếc cân cho thấy khối gỗ của anh ấy nặng hơn.

Nếu mỗi người chơi còn hai khối gỗ, trong đó Naomi có \([0.7\text{kg}, 0.2\text{kg}]\) và Ken có \([0.8\text{kg}, 0.3\text{kg}]\), thì Naomi có thể chọn khối gỗ \(0.2\)kg của mình và lừa Ken bằng cách nói với anh ấy rằng cô ấy đã chọn một khối gỗ nặng \(0.6\)kg. Ken giả định Naomi đang nói thật (như trong cách trò chơi War hoạt động) và sẽ chơi khối gỗ \(0.8\)kg của mình để ghi điểm. Ken vừa bị lừa, nhưng anh ấy sẽ không bao giờ nhận ra vì chiếc cân cho thấy khối gỗ \(0.8\)kg của anh ấy, đúng như anh ấy mong đợi, nặng hơn khối gỗ Naomi đã chơi. Bây giờ Naomi có thể chơi khối gỗ \(0.7\)kg của mình, nói với Ken đó là \(0.7\)kg và ghi điểm. Nếu Naomi chơi War thay vì Deceitful War, Ken sẽ ghi được hai điểm và Naomi ghi được không điểm.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết 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 một số nguyên duy nhất \(N\), số lượng khối gỗ mỗi người chơi có. Tiếp theo là một dòng chứa \(N\) số thực cách nhau bởi dấu cách: khối lượng các khối gỗ của Naomi, tính bằng kg. Cuối cùng sẽ là một dòng chứa \(N\) số thực cách nhau bởi dấu cách: khối lượng các khối gỗ của Ken, tính bằng kg.

Mỗi khối lượng được đưa cho Ken và Naomi sẽ được biểu diễn dưới dạng số \(0\), tiếp theo là dấu thập phân, tiếp theo là \(1\)-\(5\) chữ số. Mặc dù tất cả các số trong dữ liệu vào có \(1\)-\(5\) chữ số sau dấu thập phân, Ken và Naomi không biết điều đó; vì vậy Naomi vẫn có thể nói với Ken rằng cô ấy đã chơi một khối gỗ có khối lượng \(0.5000001\)kg, và Ken không có lý do gì để không tin cô ấy.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): \(y\) \(z\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), \(y\) là số điểm Naomi sẽ ghi được nếu cô ấy chơi Deceitful War tối ưu, và \(z\) là số điểm Naomi sẽ ghi được nếu cô ấy chơi War tối ưu.

Ràng buộc

• \(1 \le T \le 50\).
• Tất cả các khối lượng đưa cho Ken và Naomi là phân biệt và nằm trong khoảng từ \(0.0\) đến \(1.0\) (không bao gồm hai đầu mút).

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 1000\).

Đ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
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458

Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4

Nguồn

Google Code Jam 2014, Vòng loại, bài Deceitful War.

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

Lưu ý: Để tiến vào các vòng tiếp theo, bạn cần đạt được 25 điểm. Chỉ giải quyết bài toán này sẽ không cung cấp cho bạn đủ điểm.

Bài toán

Gần đây bạn đã đi xem một buổi biểu diễn ảo thuật. Bạn rất ấn tượng bởi một trong những trò ảo thuật, vì vậy bạn quyết định cố gắng tìm ra bí mật đằng sau nó!

Đầu tiên, nhà ảo thuật sắp xếp 16 lá bài thành một lưới vuông: 4 hàng bài, mỗi hàng có 4 lá. Mỗi lá bài có một số khác nhau từ 1 đến 16 được viết trên mặt đang hiển thị. Tiếp theo, nhà ảo thuật yêu cầu một người tình nguyện chọn một lá bài và cho ông ta biết lá bài đó nằm ở hàng nào.

Cuối cùng, nhà ảo thuật sắp xếp lại 16 lá bài vào một lưới vuông một lần nữa, có thể theo một thứ tự khác. Một lần nữa, ông ta hỏi người tình nguyện lá bài của cô ấy nằm ở hàng nào. Chỉ với câu trả lời cho hai câu hỏi này, nhà ảo thuật sau đó xác định chính xác lá bài mà người tình nguyện đã chọn. Thật kinh ngạc, phải không?

Bạn quyết định viết một chương trình để giúp bạn hiểu kỹ thuật của nhà ảo thuật. Chương trình sẽ được cung cấp hai cách sắp xếp các lá bài và câu trả lời của người tình nguyện cho hai câu hỏi: số hàng của lá bài được chọn trong cách sắp xếp thứ nhất và số hàng của lá bài được chọn trong cách sắp xếp thứ hai. Các hàng được đánh số từ 1 đến 4 từ trên xuống dưới.

Chương trình của bạn nên xác định lá bài nào người tình nguyện đã chọn; hoặc nếu có nhiều hơn một lá bài mà người tình nguyện có thể đã chọn (nhà ảo thuật đã làm không tốt); hoặc nếu không có lá bài nào phù hợp với câu trả lời của người tình nguyện (người tình nguyện đã gian lận).

Giải quyết bài toán này

Thông thường, các bài toán Google Code Jam có 1 Small input và 1 Large input. Bài toán này chỉ có 1 Small input. Khi bạn đã giải xong Small input, bạn đã hoàn thành việc giải bài toán này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T bộ test nối tiếp sau đó. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên: câu trả lời cho câu hỏi thứ nhất. 4 dòng tiếp theo đại diện cho cách sắp xếp lá bài thứ nhất: mỗi dòng chứa 4 số nguyên, cách nhau bởi một khoảng trắng duy nhất. Dòng tiếp theo chứa câu trả lời cho câu hỏi thứ hai, và bốn dòng tiếp theo chứa cách sắp xếp thứ hai với cùng định dạng.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1).

Nếu có một lá bài duy nhất mà người tình nguyện có thể đã chọn, y nên là số trên lá bài đó. Nếu có nhiều lá bài mà người tình nguyện có thể đã chọn, y nên là "Bad magician!", không có dấu ngoặc kép. Nếu không có lá bài nào phù hợp với câu trả lời của người tình nguyện, y nên là "Volunteer cheated!", không có dấu ngoặc kép. Văn bản cần phải chính xác tuyệt đối, vì vậy hãy cân nhắc việc sao chép/dán nó từ đây.

Ràng buộc

1 ≤ T ≤ 100.
1 ≤ cả hai câu trả lời ≤ 4.
Mỗi số từ 1 đến 16 sẽ xuất hiện đúng một lần trong mỗi cách sắp xếp.

Phân nhóm

Các giới hạn của từng tập dữ liệu được nêu trong mục Ràng buộc.

Đ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
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Case #1: 7
Case #2: Bad magician!
Case #3: Volunteer cheated!

Nguồn

Google Code Jam 2014, Vòng loại, bài Magic Trick.

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

Minesweeper là một trò chơi máy tính trở nên phổ biến vào những năm 1980 và vẫn được đưa vào một số phiên bản của hệ điều hành Microsoft Windows. Bài toán này có ý tưởng tương tự, nhưng nó không yêu cầu bạn phải từng chơi Minesweeper.

Trong bài toán này, bạn đang chơi một trò chơi trên một lưới gồm các ô giống hệt nhau. Nội dung của mỗi ô ban đầu bị ẩn. Có \(M\) quả mìn được giấu trong \(M\) ô khác nhau của lưới. Không có ô nào khác chứa mìn. Bạn có thể nhấp vào bất kỳ ô nào để mở nó. Nếu ô được mở chứa một quả mìn, trò chơi kết thúc và bạn thua. Ngược lại, ô được mở sẽ chứa một chữ số từ 0 đến 8, tương ứng với số lượng ô lân cận có chứa mìn. Hai ô là lân cận nếu chúng chung một đỉnh hoặc một cạnh. Ngoài ra, nếu ô được mở chứa số 0, thì tất cả các ô lân cận của ô đó cũng tự động được mở, một cách đệ quy. Khi tất cả các ô không chứa mìn đã được mở, trò chơi kết thúc và bạn thắng.

Ví dụ, một cấu hình ban đầu của bảng có thể trông như thế này ('*' biểu thị một quả mìn và 'c' là ô được nhấp đầu tiên):

*..*...**.
....*.....
..c..*....
........*.
..........

Không có quả mìn nào liền kề với ô đã nhấp, vì vậy khi nó được mở, nó trở thành số 0 và 8 ô liền kề của nó cũng được mở. Quá trình này tiếp tục, dẫn đến bảng sau:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

Tại thời điểm này, vẫn còn những ô chưa được mở mà không chứa mìn (được ký hiệu bằng các ký tự '.'), vì vậy người chơi phải nhấp lại để tiếp tục trò chơi.

Bạn muốn thắng trò chơi càng nhanh càng tốt. Không có gì nhanh hơn việc thắng chỉ trong một lần nhấp. Cho kích thước của bảng (\(R \times C\)) và số lượng mìn ẩn \(M\), liệu có thể (dù xác suất thấp đến đâu) thắng chỉ trong một lần nhấp không? Bạn có thể chọn nơi mình nhấp. Nếu có thể, hãy in ra bất kỳ cấu hình mìn hợp lệ nào và tọa độ lần nhấp của bạn, tuân theo các quy định trong phần Dữ liệu ra. Ngược lại, in "Impossible".

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) dòng tiếp theo. Mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách: \(R\), \(C\) và \(M\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x:", trong đó x là số thứ tự bộ test (bắt đầu từ 1). Trên \(R\) dòng tiếp theo, hãy xuất cấu hình bảng với \(C\) ký tự mỗi dòng, sử dụng '.' để đại diện cho một ô trống, '*' để đại diện cho một ô có chứa mìn và 'c' để đại diện cho ô được nhấp.

Nếu không có cấu hình khả thi nào, thay vì lưới, hãy xuất một dòng với "Impossible". Nếu có nhiều cấu hình khả thi, hãy xuất bất kỳ cấu hình nào trong số đó.

Ràng buộc

• \(0 \le M < R \times C\).

Phân nhóm

• Small dataset: \(1 \le T \le 230\); \(1 \le R, C \le 5\).
• Large dataset: \(1 \le T \le 140\); \(1 \le R, C \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ụ

5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82

Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********

Nguồn

Google Code Jam 2014, Vòng loại, bài Minesweeper Master.

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