Google Code Jam 2008 - AMER Semifinal

Bạn đang cố gắng tính số tiếp theo trong một dãy \(S_n\) được tạo ra bởi một đoạn mã bí mật. Bạn biết rằng đoạn mã này được tạo theo quy trình sau:

Đầu tiên, với mỗi \(k\) từ \(0\) đến \(29\), chọn một số \(C_k\) nằm trong khoảng từ \(0\) đến \(10006\) (bao gồm cả hai đầu).

Sau đó, với mỗi số nguyên \(n\) từ \(0\) đến \(1,000,000,000\) (bao gồm cả hai đầu):

• Viết \(n\) ở hệ nhị phân.
• Lấy các số \(C_k\) ứng với mỗi bit \(k\) được bật (bằng 1) trong biểu diễn nhị phân của \(n\). Ví dụ, khi \(n=5\), các bit \(0\) và \(2\) được bật, nên \(C_0\) và \(C_2\) được chọn.
• Cộng các số \(C_k\) này lại với nhau, chia cho \(10007\), và lấy số dư làm kết quả cho \(S_n\).

Bạn sẽ được cho một chuỗi các giá trị liên tiếp của dãy \(S\), nhưng bạn không biết các số của mình bắt đầu từ vị trí nào trong dãy (mặc dù bạn biết rằng vẫn còn ít nhất một số nữa trong dãy), và bạn không biết các giá trị \(C_k\) nào đã được chọn khi tạo dãy.

Hãy tìm số tiếp theo trong dãy, hoặc xuất ra UNKNOWN nếu không thể xác định được từ dữ liệu đã cho.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(T\), số lượng bộ test trong file dữ liệu.

Với mỗi bộ test:

• Một dòng chứa số nguyên \(N\), số lượng phần tử của dãy \(S\) mà bạn có.
• Một dòng chứa \(N\) số nguyên cách nhau bởi dấu cách, nằm trong khoảng từ \(0\) đến \(10006\), là các phần tử đã biết của dãy.

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ test (bắt đầu từ 1), và \(Y\) là số tiếp theo trong dãy, hoặc chuỗi UNKNOWN nếu không thể xác định được số tiếp theo.

Ràng buộc

• \(1 \le T \le 20\)

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le N \le 5\)
• Tập dữ liệu lớn (Test set 2 - Hidden): \(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ụ

3
7
1 2 3 4 5 6 7
4
1 10 11 200
4
1000 1520 7520 7521

Case #1: UNKNOWN
Case #2: 201
Case #3: 3514

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Code Sequence.

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

Alice và Bob muốn chơi một trò chơi. Trò chơi được chơi trên một bàn cờ có \(R\) hàng và \(C\) cột, tổng cộng có \(RC\) ô vuông. Một số ô vuông trong số này đã bị cháy.

Một quân vua sẽ được đặt trên một ô chưa bị cháy của bàn cờ, và Alice cùng Bob sẽ lần lượt thực hiện các nước đi với quân vua đó.

Trong một nước đi, người chơi phải di chuyển quân vua đến bất kỳ ô nào trong số 8 ô lân cận của nó, với hai điều kiện sau:

• Ô đích phải không bị cháy.
• Quân vua chưa từng ở ô đích đó trước đây.

Nếu một người chơi không thể thực hiện nước đi, người đó sẽ thua cuộc. Alice sẽ đi trước; bạn cần xác định ai sẽ thắng, giả sử cả hai người chơi đều chơi tối ư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, \(N\).

\(N\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên \(R\) và \(C\). \(R\) dòng tiếp theo sẽ chứa các chuỗi có độ dài \(C\), đại diện cho \(C\) ô của mỗi hàng. Mỗi chuỗi sẽ chỉ chứa các ký tự '.', '#' và 'K':

• '#' nghĩa là ô bị cháy;
• '.' nghĩa là ô chưa bị cháy và đang trống;
• 'K' nghĩa là quân vua đang ở ô đó khi bắt đầu trò chơi.

Sẽ chỉ có duy nhất một ký tự 'K' trong mỗi bộ test.

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) theo sau là A nếu Alice thắng, hoặc B nếu Bob thắng.

Ràng buộc

• \(1 \le N \le 100\)

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le R, C \le 4\)

  • Large dataset (Test set 2 - Hidden):

  • \(1 \le R, C \le 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ụ

2
2 2
K.
.#
4 2
K#
.#
.#
.#

Case #1: B
Case #2: A

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài King.

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 làm theo một công thức để chuẩn bị bữa trưa của mình.

Công thức là một hỗn hợp được tạo ra bằng cách kết hợp các thành phần lại với nhau trong một chiếc bát. Mỗi thành phần sẽ là:

• Một hỗn hợp khác mà bạn phải làm trước trong một chiếc bát riêng biệt; hoặc
• Một nguyên liệu cơ bản mà bạn đã có sẵn trong bếp, có thể được thêm vào trực tiếp.

Để tạo ra một hỗn hợp, bạn cần chuẩn bị sẵn tất cả các thành phần của nó, lấy một chiếc bát trống và trộn các thành phần vào đó. Không thể tạo ra hỗn hợp bằng cách thêm các thành phần vào một hỗn hợp đã có sẵn trong bát.

Ví dụ, nếu bạn muốn làm CAKE (một hỗn hợp) từ CAKEMIX (một hỗn hợp) và lies (một nguyên liệu cơ bản), thì trước tiên bạn phải làm CAKEMIX trong bát riêng của nó, sau đó thêm CAKEMIX và lies vào một chiếc bát thứ hai để làm CAKE.

Khi bạn đã sử dụng một hỗn hợp như một thành phần và làm trống chiếc bát mà nó được chuẩn bị, bạn có thể tái sử dụng chiếc bát đó cho một hỗn hợp khác. Vì vậy, số lượng bát bạn cần để chuẩn bị công thức sẽ phụ thuộc vào thứ tự mà bạn quyết định thực hiện các hỗn hợp.

Hãy xác định số lượng bát tối thiểu mà bạn sẽ cần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(C\), số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Một dòng chứa số nguyên \(N\), số lượng hỗn hợp trong bộ dữ liệu.
• \(N\) dòng, mỗi dòng cho một hỗn hợp, bao gồm:
  • Một chuỗi cho biết tên hỗn hợp;
  • Một số nguyên \(M\), số lượng thành phần trong hỗn hợp này;
  • \(M\) chuỗi, cho biết tên của từng thành phần của hỗn hợp này.

Các token trên một dòng sẽ được phân tách bằng các dấu cách đơn.

Hỗn hợp đầu tiên trong một bộ dữ liệu là công thức bạn đang thực hiện.

Tên của các hỗn hợp là các chuỗi có độ dài từ 1 đến 20 chữ cái VIẾT HOA.

Tên của các nguyên liệu cơ bản là các chuỗi có độ dài từ 1 đến 20 chữ cái viết thường.

Mỗi hỗn hợp được sử dụng trong đúng một hỗn hợp khác, ngoại trừ công thức chính (hỗn hợp đầu tiên), không được sử dụng trong bất kỳ hỗn hợp nào khác. Mỗi thành phần sẽ xuất hiện tối đa một lần trong danh sách thành phần của một hỗn hợp. Không có hỗn hợp nào (trực tiếp hoặc gián tiếp) yêu cầu chính nó như một thành phần.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy xuất một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ dữ liệu (bắt đầu từ 1) và \(Y\) là số lượng bát trộn tối thiểu cần thiết.

Ràng buộc

• \(1 \le C \le 10\)
• \(2 \le M \le 10\)

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ụ

2
3
SOUP 3 STOCK salt water
STOCK 2 chicken VEGETABLES
VEGETABLES 2 celery onions
5
MILKSHAKE 4 milk icecream FLAVOR FRUIT
FRUIT 2 banana berries
FLAVOR 2 SPICES CHOCOLATE
SPICES 2 nutmeg cinnamon
CHOCOLATE 2 cocoa syrup

Case #1: 2
Case #2: 3

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Mixing Bowls.

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

Dave đang làm một bài kiểm tra trắc nghiệm trên Internet. Dave có thể có nhiều cơ hội để nộp đáp án cho bài kiểm tra, nhưng anh ấy chỉ vượt qua nếu trả lời đúng tất cả các câu hỏi. Anh ấy phải trả lời mọi câu hỏi trong bài kiểm tra để thực hiện một lần nộp. Thông tin duy nhất anh ấy nhận được sau khi nộp là liệu anh ấy có vượt qua hay không.

Đối với mỗi câu hỏi, anh ấy ước tính xác suất để mỗi trong số 4 đáp án là đúng, độc lập với các câu trả lời của anh ấy cho các câu hỏi khác. Với một số lượng lượt nộp cố định \(M\) mà anh ấy có thể thực hiện, Dave muốn chọn các bộ đáp án của mình sao cho tối đa hóa xác suất vượt qua bài kiểm tra.

Xác suất Dave sẽ vượt qua bài kiểm tra là bao nhiêu nếu anh ấy chọn các bộ đáp án của mình một cách tối ư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, \(C\). Tiếp theo là \(C\) bộ test.

Mỗi bộ test bắt đầu bằng một dòng chứa \(M\) và \(Q\). Dave được phép thực hiện \(M\) lượt nộp để giải bài kiểm tra. Có \(Q\) câu hỏi trong bài kiểm tra. \(Q\) dòng tiếp theo, mỗi dòng chứa 4 xác suất đúng của 4 đáp án. Sẽ có tối đa 6 chữ số sau dấu phẩy thập phân. Các xác suất trên mỗi dòng là không âm và có tổng bằng 1.

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ự của bộ test (bắt đầu từ 1) và \(Y\) là xác suất thành công.
Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-6}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le C \le 100\)

Phân nhóm

• Small dataset (Test set 1 - Visible):

  • \(1 \le Q \le 6\)
  • \(1 \le M \le 1000\)

  • Large dataset (Test set 2 - Hidden):

  • \(1 \le Q \le 30\)

  • \(1 \le M \le 10000\)

Đ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
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0

Case #1: 0.625
Case #2: 1.0
Case #3: 0.5

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Test Passing Probability.

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