Google Code Jam 2012 - Round 3

Havannah là một trò chơi chiến thuật trừu tượng được tạo ra bởi Christian Freeling. Trò chơi được chơi trên một bàn cờ lục giác với \(S\) ô lục giác trên mỗi cạnh. Mỗi ô lục giác có hai cạnh nằm ngang và bốn cạnh xiên. Các ô lục giác được xác định bởi các cặp giá trị nguyên. Ô lục giác ở góc dưới cùng của bàn cờ là \((1, 1)\). Ô lục giác liền kề với \((x, y)\) theo hướng kim đồng hồ chỉ 2 giờ là \((x, y+1)\). Ô lục giác liền kề với \((x, y)\) theo hướng kim đồng hồ chỉ 10 giờ là \((x + 1, y)\).

Dưới đây là ví dụ về bàn cờ với \(S = 5\):

Trong trò chơi Havannah, mỗi ô lục giác có thể được chiếm bởi tối đa một quân cờ. Các quân cờ một khi đã đặt lên bàn sẽ không bao giờ bị loại bỏ hoặc di chuyển. Mục tiêu của trò chơi là xây dựng từ các quân cờ một tập hợp các quân cờ kết nối thuộc một trong ba loại cấu trúc chiến thắng sau:

• Một vòng (ring) bao quanh một hoặc nhiều ô lục giác trống. Nghĩa là, ít nhất một trong các ô lục giác bên trong phải trống. Cụ thể hơn, có một ô lục giác trống bị ngăn cách với biên ngoài cùng của bàn cờ bởi các ô có quân cờ. Lưu ý rằng quy tắc này khác với trò chơi Havannah chính thức.
• Một cầu (bridge) kết nối bất kỳ hai góc nào của bàn cờ.
• Một nĩa (fork) kết nối bất kỳ ba cạnh nào trong số sáu cạnh của bàn cờ. Các góc không được tính là một phần của bất kỳ cạnh liền kề nào.

Hình ảnh này cho thấy các ví dụ về cấu trúc chiến thắng:

Chương trình của bạn nên xác định xem một chuỗi các nước đi của một người chơi duy nhất có tạo ra một cấu trúc chiến thắng hay không. Nếu có, nó sẽ xuất ra tên của cấu trúc và số thứ tự của nước đi đã hoàn thành nó. Nếu một nước đi hoàn thành nhiều vòng, kết nối nhiều hơn hai góc hoặc kết nối nhiều hơn ba cạnh, cấu trúc đó vẫn được coi là một vòng, một cầu hoặc một nĩa tương ứng. Nhưng nếu một nước đi hoàn thành các cấu trúc thuộc các loại khác nhau cùng một lúc, chương trình của bạn nên xuất ra tên của tất cả chúng. Chúng ta chỉ quan tâm đến nước đi chiến thắng đầu tiên: bỏ qua tất cả các nước đi sau nước đi chiến thắng đó. Nếu không có cấu trúc chiến thắng nào trên bàn cờ sau khi thực hiện tất cả các nước đi trong chuỗi, chương trình của bạn nên xuất ra none.

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 tiếp theo. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên \(S\) và \(M\), lần lượt là số ô lục giác trên mỗi cạnh của bàn cờ và số nước đi trong chuỗi. \(M\) dòng tiếp theo cung cấp chuỗi các nước đi, theo thứ tự, trong đó mỗi dòng chứa một cặp định danh ô lục giác \((x, y)\) cách nhau bởi dấu cách. Tất cả các nước đi trong chuỗi đều nằm trên bàn cờ kích thước \(S\). Trong mỗi bộ test, bàn cờ ban đầu trống và các nước đi không lặp lại.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(n\): " theo sau là một trong các chuỗi:

• none
• bridge in move k
• fork in move k
• ring in move k
• bridge-fork in move k
• bridge-ring in move k
• fork-ring in move k
• bridge-fork-ring in move k

Các bộ test được đánh số bắt đầu từ 1. Các nước đi được đánh số bắt đầu từ 1.

Ràng buộc

Nhóm 1 (Visible Verdict)

• \(1 \le T \le 200\)
• \(2 \le S \le 50\)
• \(0 \le M \le 100\)

Nhóm 2 (Hidden Verdict)

• \(1 \le T \le 20\)
• \(2 \le S \le 3000\)
• \(0 \le M \le 10000\)

Phân nhóm

Các giới hạn cho hai tập kiểm thử được nêu ở trên.

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

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

Case #1: bridge in move 2
Case #2: fork in move 5
Case #3: none
Case #4: ring in move 6
Case #5: bridge-fork in move 5
Case #6: bridge in move 7
Case #7: none

Nguồn

Google Code Jam 2012, Vòng 3, bài Havannah.

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

Ashish đã quên mật khẩu của mình. Anh ấy nhớ rằng mình đã sử dụng thuật toán sau để tạo mật khẩu: Ashish lấy tối đa \(k\) từ liên tiếp từ một đoạn văn bản và lấy chữ cái đầu tiên của mỗi từ. Sau đó, anh ấy có thể đã thay đổi một số chữ cái sang dạng "l33tspeak" tương đương. Cụ thể, anh ấy có thể đã thay đổi "o" thành "0", "i" thành "1", "e" thành "3", "a" thành "4", "s" thành "5", "t" thành "7", "b" thành "8" và/hoặc "g" thành "9".

Ví dụ, nếu Ashish lấy mật khẩu từ câu đầu tiên của cuốn The Fellowship of the Ring -- "This book is largely concerned with Hobbits, and from its pages a reader may discover much of their character and a little of their history" -- Ashish sẽ rút gọn nó thành "tbilcwhafiparmdmotcaaloth". Sau đó, mật khẩu có thể là "tbilcwh", "7b1lcwh4f", "a", "4", hoặc "4al07h", v.v.

Ashish có một tiện ích mở rộng đặc biệt được cài đặt trong trình duyệt của mình để ngăn máy tính tải lên bất kỳ chuỗi nào chứa mật khẩu của anh ấy. Để tìm ra đoạn văn bản nào anh ấy đã lấy mật khẩu, Ashish đã tạo một trang web để tận dụng tiện ích này. Mỗi giây, trang web sẽ yêu cầu trình duyệt gửi một "chuỗi mật khẩu" cho một đoạn văn bản mới: một chuỗi chứa tất cả các mật khẩu có thể mà Ashish có thể đã chọn từ đoạn văn bản đó. Ngay khi trình duyệt của anh ấy không gửi được chuỗi như vậy, Ashish sẽ biết mình đã lấy mật khẩu từ đâu.

Ví dụ, nếu \(k = 2\) và đoạn văn bản chứa các từ bắt đầu bằng các chữ cái "google", thì một chuỗi mật khẩu cho đoạn văn bản đó là "goo0og00gle9o909l3". Tất cả các chuỗi con có độ dài \(\le 2\) từ chuỗi gốc, và tất cả các biến thể l33tspeak tương đương của chúng, đều được chứa trong chuỗi mới này.

Cho các chữ cái đầu tiên của các từ trong một đoạn văn bản, số ký tự tối thiểu trong "chuỗi mật khẩu" của đoạn văn bản đó là bao nhiêu?

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 theo sau. Mỗi bộ test gồm hai dòng. Dòng đầu tiên chứa số nguyên \(k\). Dòng thứ hai chứa một chuỗi \(S\), đại diện cho các chữ cái đầu tiên của các từ trong một đoạn văn bản. \(S\) chỉ chứa các ký tự 'a' - 'z', không có khoảng trắng.

Dữ liệu ra

Đối 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) và y là số ký tự tối thiểu trong chuỗi mật khẩu cho \(S\).

Ràng buộc

• \(1 \le T \le 20\).
• \(S\) sẽ chứa ít nhất \(2 \times k\) ký tự.
• Sẽ tồn tại một chuỗi mật khẩu với tối đa \(10^{18}\) ký tự.

Phân nhóm

• Test set 1 (Visible Verdict): \(S\) chứa tối đa 1000 ký tự; \(k = 2\).
• Test set 2 (Hidden Verdict): \(S\) chứa tối đa 5000 ký tự; \(2 \le k \le 500\).

Đ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
2
poppop
2
google
2
tbilcwhafiparmdmotcaaloth
10
tbilcwhafiparmdmotcaaloth

Case #1: 6
Case #2: 18
Case #3: 53
Case #4: 1136

Nguồn

Google Code Jam 2012, Vòng 3, bài Lost Password.

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 điện tử và sẽ nhận được một thành tựu nếu hoàn thành tất cả các màn chơi liên tiếp mà không bị chết. Bạn có thể chơi các màn theo bất kỳ thứ tự nào, và mỗi lần chơi một màn, bạn sẽ hoàn thành nó hoặc bị chết. Mỗi màn chơi có một xác suất nhất định để bạn hoàn thành và tốn một khoảng thời gian cụ thể. Bạn nên chơi các màn theo thứ tự nào để thời gian kỳ vọng để đạt được thành tựu là nhỏ nhất? Giả sử rằng thời gian để vượt qua một màn chơi hoặc chết trong màn đó là như nhau, và bạn sẽ bắt đầu lại từ màn đầu tiên trong thứ tự đã chọn ngay khi bạn chết.

Lưu ý: Nếu bạn không hoàn thành được một màn chơi, cá nhân bạn không chết — chỉ có nhân vật của bạn trong trò chơi chết. Nếu không phải như vậy, chỉ có rất ít người cố gắng đạt được thành tựu 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 theo sau, mỗi bộ gồm ba dòng.

• Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất N, số lượng màn chơi.
• Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách \(L_i\). \(L_i\) là số giây mà màn chơi i kéo dài, thời gian này độc lập với việc bạn hoàn thành màn chơi hay bị chết.
• Dòng thứ ba chứa N số nguyên cách nhau bởi dấu cách \(P_i\). \(P_i\) là phần trăm khả năng bạn sẽ chết trong bất kỳ lần thử nào để hoàn thành màn chơi i.

Dữ liệu ra

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), tiếp theo là N số nguyên cách nhau bởi dấu cách. Số nguyên thứ j trong danh sách phải là chỉ số của màn chơi thứ j bạn nên thử vượt qua để giảm thiểu thời gian kỳ vọng đạt được thành tựu.

Các chỉ số đi từ 0 đến N-1. Nếu có nhiều thứ tự cho cùng một thời gian kỳ vọng, hãy xuất thứ tự nhỏ nhất về mặt từ điển. Trong hai thứ tự, thứ tự nhỏ hơn về mặt từ điển là thứ tự có chỉ số nhỏ hơn tại vị trí đầu tiên mà chúng khác nhau.

Ràng buộc

• 1 ≤ T ≤ 100.
• 0 ≤ \(P_i\) < 100.

Phân nhóm

• Nhóm test 1 (Visible Verdict):
• 1 ≤ N ≤ 20.
• \(L_i\) = 1.
• Nhóm test 2 (Hidden Verdict):
• 1 ≤ N ≤ 1000.
• 1 ≤ \(L_i\) ≤ 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ụ

3
4
1 1 1 1
50 0 20 20
3
100 10 1
0 50 0
3
100 80 50
40 20 80

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

Nguồn

Google Code Jam 2012, Vòng 3, bài Perfect Game.

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 vừa chuyển từ quê nhà lên một thành phố lớn! Bạn yêu mọi thứ ở môi trường mới, ngoại trừ đồ ăn. Quê hương của bạn cung cấp những món ăn ngon nhất trong vùng (được gọi là "đồ ăn chất lượng") và chắc chắn bạn sẽ nhớ nó.

May mắn thay, nhà hàng lớn nhất ở quê bạn có cung cấp dịch vụ giao hàng. Bạn có thể mua bất kỳ lượng thức ăn nào trong một lần giao. Có một khoản phí giao hàng cố định cho mỗi lần giao, bất kể lượng thức ăn được mua trong lần đó là bao nhiêu.

Nhà hàng này phục vụ nhiều loại thức ăn khác nhau. Mỗi loại thức ăn có hai thuộc tính: giá mỗi bữa ăn và thời gian hết hạn. Một "bữa ăn" sẽ nuôi sống bạn trong một ngày; một khi bữa ăn đã được ăn, nó không thể được ăn lại. Thời gian hết hạn của một loại thức ăn là số ngày tối đa mà thức ăn đó vẫn có thể ăn được, tính từ thời điểm bạn nhận được nó. Thời gian hết hạn bằng 0 có nghĩa là bạn phải ăn loại thức ăn đó ngay trong ngày giao hàng.

Trong một lần giao hàng, bạn có thể mua bao nhiêu loại thức ăn khác nhau tùy thích và bao nhiêu bữa ăn của mỗi loại tùy thích, miễn là bạn có đủ tiền. Lưu ý rằng nếu một loại thức ăn cụ thể có thời gian hết hạn là \(t\), việc đặt mua nhiều hơn \(t+1\) bữa ăn của loại đó trong một lần giao hàng là không hợp lý: ít nhất một bữa ăn sẽ bị hỏng trước khi bạn kịp ăn nó.

Nhà hàng này có dịch vụ giao hàng rất nhanh, vì vậy bạn sẽ nhận được tất cả thức ăn trong một lần giao vào cùng ngày bạn đặt mua, và bạn có thể ăn một số thức ăn ngay trong ngày hôm đó. Giao hàng là cách duy nhất để bạn nhận được đồ ăn chất lượng.

Cho một số tiền nhất định mà bạn có thể chi cho giá các bữa ăn và phí giao hàng, số ngày tối đa bạn có thể ăn đồ ăn chất lượng mỗi ngày là bao nhiêu?

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 tiếp theo. Mỗi bộ test bắt đầu bằng ba số nguyên \(M\), \(F\) và \(N\), lần lượt biểu thị số tiền bạn có, phí giao hàng và số lượng loại thức ăn mà nhà hàng cung cấp. \(N\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(P_i\) và \(S_i\), lần lượt biểu thị giá mỗi bữa ăn và thời gian hết hạn của một loại thức ăn.

Dữ liệu ra

Đối 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) và y là số ngày tối đa mà bạn có thể duy trì việc ăn ít nhất một bữa đồ ăn chất lượng mỗi ngày.

Ràng buộc

• \(1 \le T \le 50\).
• \(1 \le F \le M\).
• \(1 \le N \le 200\).
• \(1 \le P_i \le M\).

Phân nhóm

• Test set 1 (Visible Verdict):
• \(0 \le S_i \le 2,000,000\).
• \(1 \le M \le 2,000,000\).
• Test set 2 (Hidden Verdict):
• \(0 \le S_i \le 10^{18}\).
• \(1 \le M \le 10^{18}\).

Đ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
32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5

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

Nguồn

Google Code Jam 2012, Vòng 3, bài Quality Food.

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