Kiểm tra dị ứng

Đề bài

Kelly bị dị ứng với đúng một trong số \(N\) loại thực phẩm, nhưng cô ấy không chắc là loại nào. Vì vậy, cô ấy quyết định thực hiện một số thí nghiệm để tìm ra loại thực phẩm đó.

Trong mỗi thí nghiệm, Kelly chọn một vài loại thực phẩm và ăn tất cả chúng. Cô ấy đợi \(A\) ngày để xem mình có phản ứng dị ứng nào không. Nếu không, cô ấy biết mình không bị dị ứng với bất kỳ loại thực phẩm nào đã ăn. Nếu có phản ứng, cô ấy phải đợi cho đến khi phản ứng đó biến mất: việc này mất tổng cộng \(B\) ngày (tính từ thời điểm cô ấy ăn thực phẩm).

Để đơn giản hóa việc thử nghiệm, Kelly quyết định đợi cho đến khi mỗi thí nghiệm kết thúc (sau \(A\) hoặc \(B\) ngày) trước khi bắt đầu thí nghiệm tiếp theo. Khi bắt đầu mỗi thí nghiệm, cô ấy có thể chọn nhóm thực phẩm muốn ăn dựa trên kết quả của các thí nghiệm trước đó.

Kelly chọn loại thực phẩm để ăn cho mỗi thí nghiệm sao cho tối thiểu hóa số ngày trong trường hợp xấu nhất trước khi cô ấy biết mình bị dị ứng với loại nào trong số \(N\) loại thực phẩm. Hỏi cô ấy mất bao lâu trong trường hợp xấu nhất?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ test nằm trên một dòng, chứa ba số nguyên cách nhau bởi dấu cách: \(N\), \(A\) và \(B\).

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) và \(y\) là số ngày Kelly cần để tìm ra loại thực phẩm mình bị dị ứng trong trường hợp xấu nhất.

Ràng buộc

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

Phân nhóm

• Small dataset:

  • \(1 \le N \le 10^{15}\).
  • \(1 \le A \le B \le 100\).

  • Large dataset:

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

  • \(1 \le A \le B \le 10^{12}\).

Đ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 5 7
8 1 1
1 23 32

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Allergy Testing.

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

Trong trò chơi League of Legends™, bạn có thể chơi một chế độ gọi là "ARAM", viết tắt của "All Random, All Mid". Bài toán này sử dụng một ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi League of Legends để hiểu nó.

Mỗi khi bạn bắt đầu một trận ARAM, bạn được chỉ định ngẫu nhiên đều một trong N "tướng" (champions). Bạn có khả năng thắng cao hơn với một số tướng so với các tướng khác, vì vậy nếu không may mắn, bạn có thể ước mình được nhận một tướng khác. May mắn thay, trò chơi có chức năng "Reroll" (đổ lại).

Khả năng đổ lại hoạt động giống như một loại tiền tệ. Trước khi chơi trận ARAM đầu tiên, bạn bắt đầu với R RD ("reroll dollars"). Bạn chỉ có thể đổ lại nếu bạn có ít nhất 1 RD, và bạn phải tốn 1 RD để đổ lại. Sau mỗi trận đấu, bạn nhận thêm 1/G RD (trong đó G là một số nguyên), nhưng bạn không bao giờ có thể có nhiều hơn R RD: nếu bạn đang có R RD và chơi một trận, bạn vẫn sẽ có R RD sau trận đó.

Nếu bạn có ít nhất 1 RD và chọn đổ lại, bạn sẽ tốn 1 RD và được chỉ định lại một trong N tướng một cách ngẫu nhiên đều. Có khả năng bạn sẽ nhận lại đúng tướng mà bạn đã có lúc đầu. Nếu bạn không thích tướng vừa đổ lại và vẫn còn ít nhất 1 RD, bạn có thể đổ lại tiếp. Miễn là bạn còn ít nhất 1 RD, bạn có thể tiếp tục đổ lại.

Ví dụ, nếu R=2 và G=2, và bạn sử dụng một lần đổ lại trong trận đầu tiên, sau trận đó bạn sẽ có 1.5 RD. Nếu bạn chơi một trận khác mà không đổ lại, bạn sẽ có 2.0 RD. Nếu bạn chơi thêm một trận nữa mà không đổ lại, bạn vẫn sẽ có 2.0 RD (vì bạn không bao giờ có thể có nhiều hơn R=2). Nếu bạn sử dụng hai lần đổ lại trong trận tiếp theo, sau trận đó bạn sẽ có 0.5 RD.

Bạn được cung cấp danh sách các tướng và xác suất thắng trận nếu bạn chơi mỗi tướng đó. Nếu bạn chơi \(10^{100}\) trận và chọn chiến thuật tối ưu, tỉ lệ trận thắng mà bạn mong đợi là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách: N, R và G. Dòng tiếp theo chứa N số thực P\(_i\), cho biết xác suất bạn sẽ thắng nếu chơi tướng i.

Dữ liệu ra

Với mỗi bộ test, 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à tỉ lệ trận thắng bạn sẽ đạt được nếu chơi \(10^{100}\) trận.

y sẽ được coi là chính xác nếu nó nằm trong sai số tuyệt đối hoặc tương đối \(10^{-10}\) so với đáp án đúng.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(0.0 \le \mathbf{P}_i \le 1.0\).
• P\(_i\) được biểu diễn dưới dạng một chữ số, theo sau là dấu chấm thập phân và 4 chữ số sau dấu thập phân.

Phân nhóm

• Small dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{R} \le 2, 1 \le \mathbf{G} \le 3\).
• Large dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{R} \le 20, 1 \le \mathbf{G} \le 20\).

Đ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 1
1.0000 0.0000
3 1 1
1.0000 0.0000 0.5000
6 2 3
0.9000 0.6000 0.5000 0.1000 0.2000 0.8000

Case #1: 0.750000000000
Case #2: 0.666666666667
Case #3: 0.618728522337

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài ARAM.

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 ý: League of Legends là nhãn hiệu của Riot Games. Riot Games không xác nhận và không liên quan đến Google Code Jam.

Khi cảm thấy buồn chán, Mija đôi khi thích chơi một trò chơi với các ma trận. Cô ấy cố gắng biến đổi một ma trận này thành một ma trận khác với số bước di chuyển ít nhất. Đối với Mija, một bước di chuyển là hoán đổi bất kỳ hai hàng nào của ma trận hoặc bất kỳ hai cột nào của ma trận.

Hôm nay, Mija có một ma trận rất đặc biệt \(M\). \(M\) là một ma trận kích thước \(2N \times 2N\), trong đó mỗi phần tử là 0 hoặc 1. Mija quyết định thử và biến đổi \(M\) thành một ma trận bàn cờ (checkerboard matrix), nơi các phần tử xen kẽ giữa 0 và 1 dọc theo mỗi hàng và mỗi cột. Bạn có thể giúp Mija tìm số bước di chuyển tối thiểu để biến đổi \(M\) thành một ma trận bàn cờ khô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\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa một số nguyên duy nhất: \(N\). \(2N\) dòng tiếp theo, mỗi dòng chứa \(2N\) ký tự là các hàng của \(M\); mỗi ký tự là 0 hoặc 1.

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ố lần hoán đổi hàng và hoán đổi cột tối thiểu cần thiết để biến \(M\) thành một ma trận bàn cờ. Nếu không thể biến \(M\) thành ma trận bàn cờ, y sẽ là "IMPOSSIBLE".

Ràng buộc

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

Phân nhóm

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

Đ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
01
10
2
1001
0110
0110
1001
1
00
00

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Checkerboard Matrix.

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

Vlad rất thích kẹo. Bạn có một túi đựng các loại kẹo khác nhau và bạn định cho Vlad giữ lại một trong số chúng. Bạn chọn một thứ tự cho các viên kẹo, sau đó đưa từng viên một cho Vlad. Đối với mỗi viên kẹo Vlad nhận được (sau viên đầu tiên), anh ấy sẽ so sánh viên kẹo đang giữ với viên kẹo vừa được đưa, giữ lại viên anh ấy thích hơn và vứt viên còn lại đi.

Bạn có thể kỳ vọng rằng với bất kỳ thứ tự nào bạn chọn, Vlad sẽ luôn giữ lại viên kẹo yêu thích nhất của anh ấy. Nhưng thực tế không phải vậy! Anh ấy không nhất thiết phải có một viên kẹo yêu thích nhất duy nhất. Chúng ta biết với bất kỳ cặp kẹo nào, anh ấy sẽ thích viên nào hơn, nhưng lựa chọn của anh ấy không nhất thiết tuân theo một thứ hạng đơn giản. Anh ấy có thể chọn Cam khi được đưa Cam và Chanh, chọn Chuối khi được đưa Cam và Chuối, và chọn Chanh khi được đưa Chanh và Chuối!

Có một viên kẹo cụ thể mà bạn muốn Vlad giữ lại cuối cùng. Cho biết sở thích của Vlad đối với từng cặp kẹo, hãy xác định xem có thứ tự nào để Vlad giữ lại đúng viên kẹo đó hay không. Nếu có, hãy tìm thứ tự có thứ tự từ điển nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) bộ dữ liệu tiếp theo. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa các số nguyên \(N\) và \(A\), cách nhau bởi một dấu cách. \(N\) là số lượng kẹo, và \(A\) là số hiệu của viên kẹo mà chúng ta muốn Vlad giữ lại cuối cùng. Các viên kẹo được đánh số từ \(0\) đến \(N-1\). \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự. Ký tự thứ \(j\) của dòng thứ \(i\) sẽ là 'Y' nếu Vlad thích kẹo \(i\) hơn kẹo \(j\), 'N' nếu Vlad thích kẹo \(j\) hơn kẹo \(i\), và '-' nếu \(i = j\). Lưu ý rằng nếu \(i \neq j\), ký tự thứ \(j\) của hàng thứ \(i\) phải khác với ký tự thứ \(i\) của hàng thứ \(j\).

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra "Case #x: ", trong đó x là số thứ tự bộ dữ liệu, tiếp theo là "IMPOSSIBLE" hoặc một danh sách các số hiệu kẹo cách nhau bởi dấu cách, đại diện cho thứ tự có thứ tự từ điển nhỏ nhất khiến Vlad giữ lại kẹo \(A\).

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \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ụ

3
2 0
-Y
N-
2 0
-N
Y-
4 3
-YNN
N-YY
YN-Y
YNN-

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Paradox Sort.

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

Trong một vũ trụ song song, mọi người phát cuồng vì việc sử dụng các con số là lũy thừa của hai. Họ đã định nghĩa một chiến thuật sắp xếp thú vị cho các hoán vị của các số từ \(1\) đến \(2^N\). Họ định nghĩa thao tác hoán đổi như sau:

• Một dãy số để hoán đổi là hợp lệ nếu và chỉ nếu nó là một dãy các số liền kề có kích thước \(2^k\), và vị trí bắt đầu của nó (vị trí của phần tử đầu tiên trong dãy) là bội số của \(2^k\) (với các vị trí được đánh chỉ số từ \(0\)).
• Một thao tác hoán đổi hợp lệ kích thước-k được định nghĩa bằng cách hoán đổi hai dãy số hợp lệ, phân biệt, mỗi dãy có kích thước \(2^k\).

Để sắp xếp hoán vị đã cho, bạn được phép sử dụng tối đa một thao tác hoán đổi cho mỗi kích thước \(k\), với \(k \in [0, N)\). Ngoài ra, lưu ý rằng việc hoán đổi một dãy với chính nó là không được phép.

Ví dụ, cho hoán vị \([3, 6, 1, 2, 7, 8, 5, 4]\) (một hoán vị của các số từ \(1\) đến \(2^3\)), hoán vị này có thể được sắp xếp như sau:

• \([3, 6, 1, 2, 7, 8, 5, 4]\): thực hiện một lần hoán đổi kích thước-2 cho các dãy \([3, 6, 1, 2]\) và \([7, 8, 5, 4]\).
• \([7, 8, 5, 4, 3, 6, 1, 2]\): thực hiện một lần hoán đổi kích thước-0 cho \([5]\) và \([3]\).
• \([7, 8, 3, 4, 5, 6, 1, 2]\): thực hiện một lần hoán đổi kích thước-1 cho \([7, 8]\) và \([1, 2]\).
• \([1, 2, 3, 4, 5, 6, 7, 8]\): hoàn thành.

Các bước trên đã sử dụng mỗi kích thước hoán đổi (\(0, 1\), và \(2\)) tối đa một lần. Ngoài ra, hãy chú ý rằng tất cả các lần hoán đổi đều hợp lệ vì cả hai dãy cho mỗi kích thước \(k\) đều bắt đầu tại các chỉ số là bội số của \(2^k\).

Hãy đếm xem có bao nhiêu cách để sắp xếp hoán vị đã cho bằng cách sử dụng các quy tắc trên. Một cách là một chuỗi các thao tác hoán đổi có thứ tự, và hai cách được coi là giống nhau chỉ khi các chuỗi đó đồng nhất.

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. Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất \(N\). Dòng tiếp theo chứa \(2^N\) số nguyên cách nhau bởi dấu cách: một hoán vị của các số \(1, 2, \dots, 2^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ố cách sắp xếp hoán vị đã cho bằng các quy tắc trên.

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le N \le 4\).
• Large dataset: \(1 \le N \le 12\).

Đ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
2 1
2
1 4 3 2
3
7 8 5 6 1 2 4 3
2
4 3 2 1

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

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Power Swapper.

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 một cây gồm \(N\) nút có màu, liệu có thể vẽ cây này trên mặt phẳng 2D sao cho nó có một trục đối xứng hay không?

Một cách hình thức, một cây được gọi là đối xứng trục nếu mỗi đỉnh có thể được gán một vị trí trên mặt phẳng 2D sao cho:

• Tất cả các vị trí là phân biệt.
• Nếu đỉnh \(v_i\) có màu \(C\) và tọa độ \((x_i, y_i)\), thì phải tồn tại một đỉnh \(v_i'\) có màu \(C\) tại tọa độ \((-x_i, y_i)\) -- Lưu ý nếu \(x_i = 0\), \(v_i\) và \(v_i'\) là cùng một đỉnh.
• Với mỗi cạnh \((v_i, v_j)\), phải tồn tại một cạnh \((v_i', v_j')\).
• Nếu các cạnh được biểu diễn bằng các đoạn thẳng nối các đỉnh đầu mút, không có hai cạnh nào có điểm chung ngoại trừ tại các đầu mút của các cạnh kề nhau.

Dữ liệu vào

Dòng đầu tiên của đầ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 một dòng chứa một số nguyên duy nhất \(N\), số lượng đỉnh trong cây.
\(N\) dòng tiếp theo, mỗi dòng chứa một chữ cái in hoa duy nhất. Dòng thứ \(i\) đại diện cho màu của nút thứ \(i\).
\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i < j \le N\)). Điều này biểu thị rằng cây có một cạnh nối đỉnh thứ \(i\) và đỉnh thứ \(j\). Các cạnh sẽ tạo thành một cây liên thô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à "SYMMETRIC" nếu cây đối xứng trục theo định nghĩa trên hoặc "NOT SYMMETRIC" nếu ngược lại.

Ràng buộc

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

Phân nhóm

• Small dataset: \(2 \le N \le 12\).
• Large dataset: \(2 \le N \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
4
R
G
B
B
1 2
2 3
2 4
4
R
G
B
Y
1 2
2 3
2 4
12
Y
B
Y
G
R
G
Y
Y
B
B
B
R
1 3
1 9
1 10
2 3
3 7
3 8
3 11
4 8
5 7
6 7
8 12

Case #1: SYMMETRIC
Case #2: NOT SYMMETRIC
Case #3: SYMMETRIC

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Symmetric Trees.

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