Google Code Jam 2011 - World Finals

Amy có một bộ bài gồm \(N\) lá bài có giá trị từ \(1\) đến \(N\). Cô ấy sắp xếp bộ bài sao cho các giá trị của các lá bài không có dãy con giảm dần độ dài 3. Ví dụ, \(1, 5, 4, 6, 3, 2\) là một thứ tự không hợp lệ vì \(5, 3, 2\) là một dãy con giảm dần.

Bây giờ Amy đưa bộ bài cho Ben. Ben biết rằng bộ bài không có dãy con giảm dần độ dài 3, nhưng anh ấy không biết thứ tự chính xác. Anh ấy muốn tìm lá bài có giá trị 1. Anh ấy thực hiện việc này bằng cách chọn một lá bài bất kỳ, lật nó lên để xem giá trị, và lặp lại cho đến khi tìm thấy lá bài có giá trị 1. Ở mỗi bước, Ben chọn một lá bài sao cho số lượng lá bài anh ấy phải kiểm tra trong trường hợp xấu nhất là tối thiểu.

Sau đó, Ben nói với bạn rằng anh ấy đã không may mắn và phải kiểm tra tất cả \(N\) lá bài mới tìm thấy lá bài có giá trị 1. Cho biết thứ tự các vị trí mà Ben đã kiểm tra, hãy xác định giá trị của mỗi lá bài trong bộ bài là bao nhiêu? Nếu có nhiều khả năng, hãy chọn bộ bài có thứ tự từ điển lớn nhất.

Một bộ bài A được gọi là lớn hơn về mặt từ điển so với bộ bài B nếu và chỉ nếu, tại vị trí đầu tiên mà chúng khác nhau, lá bài trong A có giá trị lớn hơn giá trị của lá bài trong B.

Ví dụ: \(N = 3\), và Ben đã thử các lá bài theo thứ tự vị trí là \(2, 1, 3\) (các vị trí được đánh số từ 1). Giá trị của các lá bài phải là: \(2, 3, 1\).

Giải thích: Nếu lá bài thứ #2 có giá trị 1, Ben sẽ dừng lại ngay lập tức. Nếu lá bài thứ #2 có giá trị 2, Ben sẽ biết lá bài đầu tiên phải là 1, vì thứ tự \((3, 2, 1)\) chứa dãy con giảm dần độ dài 3, nên không thể xảy ra. Trong cả hai trường hợp, Ben sẽ không cần đến 3 lần đoán. Do đó, ta có thể suy ra lá bài thứ #2 phải có giá trị 3. Tương tự, lá bài thứ #1 không thể có giá trị 1, nếu không Ben đã dừng lại sớm hơn. Vì vậy, các giá trị lá bài phải là \(2, 3, 1\).

Dữ liệu vào

Dòng đầu tiên của đầ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 \(N\), số lượng lá bài trong bộ bài. Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, mô tả thứ tự các vị trí mà Ben đã kiểm tra: số nguyên đầu tiên là vị trí (đánh số từ 1) của lá bài đầu tiên anh ấy kiểm tra, số nguyên thứ hai là vị trí của lá bài thứ hai, và cứ tiếp tục như vậ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", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là dãy giá trị của các lá bài theo đúng thứ tự vị trí từ 1 đến \(N\), cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le T \le 100\)
• Đối với dãy các lần đoán được cung cấp, chắc chắn có ít nhất một bộ bài thỏa mãn tất cả các ràng buộc của bài toán, bao gồm cả ràng buộc rằng chiến thuật của Ben yêu cầu anh ấy phải xem tất cả \(N\) lá bài.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 8\).
• Test set 2 (Hidden): \(1 \le N \le 300\).

Đ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
3
2 1 3
1
1
3
3 2 1

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

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Ace in the Hole.

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 khi thám hiểm hành tinh Theta VIII, đội của bạn bị buộc phải tham gia vào một câu chuyện trong một cuốn sách dở tệ, diễn ra tại một khách sạn/sòng bạc tên là Google Royale. Để thoát khỏi Royale, bạn phải kiếm đủ tiền từ việc đánh bạc để có thể mua lại khách sạn với giá V đô la và rời đi.

Bạn bắt đầu với A đô la và sẽ tham gia vào các vòng đặt cược cho đến khi một trong hai điều kiện sau được đáp ứng. Nếu bạn kết thúc bất kỳ vòng đặt cược nào với \(\le 0\) đô la, bạn sẽ thua; nếu bạn kết thúc một vòng đặt cược với \(\ge \mathbf{V}\) đô la, bạn sẽ mua khách sạn và rời đi. Nếu không, bạn sẽ tiếp tục bắt đầu các vòng đặt cược mới.

Mỗi vòng đặt cược bao gồm một hoặc nhiều lần tung đồng xu. Nếu bạn có \(X\) đô la khi bắt đầu vòng, bạn có thể chọn bất kỳ số nguyên B nào trong khoảng từ \(1\) đến min(X, M) để đặt cược cho lần tung đồng xu đầu tiên.

• Với xác suất \(50\%\), bạn thắng lần tung đồng xu, và Royale trả ngay cho bạn B đô la. Bạn hiện có X + B đô la, và vòng đặt cược kết thúc.
• Với xác suất \(50\%\), bạn thua lần tung đồng xu và nợ Royale B đô la. Lúc này bạn có thể trả B đô la nợ và kết thúc vòng. Hoặc nếu 2B ≤ M, bạn có thể chọn trì hoãn việc trả tiền và thực hiện lần tung đồng xu thứ hai với mức cược gấp đôi: 2B đô la. Nếu bạn lại thua, bạn nợ Royale \(B + 2B = 3B\) đô la. Bạn có thể tiếp tục gấp đôi mức cược theo cách này lên 4B, 8B, v.v., cho đến khi bạn thắng một lần tung đồng xu, bạn chọn dừng lại, hoặc mức cược tiếp theo của bạn vượt quá M. Bạn thậm chí có thể tiếp tục nếu tổng tất cả các khoản cược trong vòng hiện tại vượt quá \(X\).

Sau khi vòng chơi kết thúc, bạn phải trả cho Royale cho mỗi lần tung đồng xu bạn thua, và nếu bạn thắng một lần tung đồng xu, Royale sẽ trả cho bạn số tiền đó. Ví dụ, nếu bạn bắt đầu với mức cược \(1\) đô la, thua ba lần tung đồng xu, và sau đó thắng một lần, bạn sẽ nhận được \(\$8 - \$4 - \$2 - \$1 = \$1\). Nếu bạn thua ba lần tung đồng xu và sau đó dừng lại, bạn sẽ mất \(\$4 + \$2 + \$1 = \$7\). Nếu bạn còn lại \(0\) đô la hoặc ít hơn sau khi trả tiền, bạn sẽ phá sản và thua cuộc.

May mắn thay, bạn có một người máy đi cùng, và anh ta có thể tính toán xác suất bạn sẽ thắng nếu tuân theo một chiến thuật tối ưu. Xác suất đó là bao nhiêu, và mức đặt cược đầu tiên lớn nhất có thể là bao nhiêu để đạt được xác suất đó? Hãy nhớ rằng bạn không được phép đặt cược nhiều hơn M!

Ví dụ

Giả sử bạn quyết định sử dụng chiến thuật (không tối ưu) sau. Bạn có A = 5 đô la; M = 20 và V = 40. Chuỗi sự kiện sau có thể xảy ra:

• Vòng 1: Bạn có thể bắt đầu bằng cách đặt cược \(1, 2, 3, 4\) hoặc \(5\) đô la. Bạn quyết định bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thắng lần tung đầu tiên. Bạn nhận \(2\) đô la, vòng kết thúc. Bây giờ bạn có \(7\) đô la.
• Vòng 2: Bạn bắt đầu vòng đặt cược bằng cách cược \(5\) đô la.
  • Bước 1 (\(B=5\)): Bạn thua lần tung đầu tiên. Bây giờ bạn nợ Royale \(5\) đô la. Vì 5*2 ≤ 20, bạn có thể tung đồng xu lần nữa với mức cược 5*2=10 đô la. Bạn chọn không làm vậy. Bạn mất \(5\) đô la, vòng kết thúc. Bây giờ bạn có \(2\) đô la.
• Vòng 3: Bạn bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thua. Bây giờ bạn nợ Royale \(2\) đô la. Bạn chọn tung đồng xu khác với mức cược \(4\) đô la.
  • Bước 2 (\(B=4\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(6\) đô la. Số tiền này nhiều hơn số bạn có, nhưng không sao. Bạn chọn tung đồng xu khác với mức cược \(8\) đô la.
  • Bước 3 (\(B=8\)): Bạn thắng. Bạn nhận \(8\) đô la, trả \(2+4=6\) đô la nợ, vòng kết thúc. Bây giờ bạn có \(4\) đô la.
• Vòng 4: Bạn bắt đầu vòng đặt cược bằng cách cược \(2\) đô la.
  • Bước 1 (\(B=2\)): Bạn thua. Bây giờ bạn nợ Royale \(2\) đô la. Bạn chọn tung đồng xu khác với mức cược \(4\) đô la.
  • Bước 2 (\(B=4\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(6\) đô la. Bạn chọn tung đồng xu khác với mức cược \(8\) đô la.
  • Bước 3 (\(B=8\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(14\) đô la. Bạn chọn tung đồng xu khác với mức cược \(16\) đô la.
  • Bước 4 (\(B=16\)): Bạn thua. Bây giờ bạn nợ tổng cộng \(30\) đô la. Vì 2*16 > M, bạn không thể tung thêm và phải trả nợ. Bây giờ bạn có \(-26\) đô la; bạn đã thua.

Dữ liệu vào

Dòng đầu tiên của đầ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ố nguyên cách nhau bởi khoảng trắng: A, M và V.

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 z", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1); y là xác suất thắng nếu bạn tuân theo chiến thuật tối ưu; và z là mức đặt cược đầu tiên lớn nhất bạn có thể thực hiện mà không làm giảm xác suất thắng. y phải 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 \mathbf{T} \le 100\).

Phân nhóm

• Test set 1 (Visible): \(1 \le \mathbf{M} \le 20\); \(1 \le \mathbf{A} < \mathbf{V} \le 20\).
• Test set 2 (Hidden): \(1 \le \mathbf{M} \le 10^{16}\); \(1 \le \mathbf{A} < \mathbf{V} \le 10^{16}\).

Đ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 1 3
3 6 12
4 20 15
13 6 20

Case #1: 0.333333333 1
Case #2: 0.500000000 3
Case #3: 0.755555555 3
Case #4: 0.730769231 6

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Google Royale.

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 có một robot trên một xa lộ vô tận hướng Đông-Tây, và nó cần giao một chiếc bánh. Cứ mỗi dặm dọc theo xa lộ, về cả hai hướng, đều có một cột đèn. Bạn muốn lập trình cho robot di chuyển chính xác \(N\) cột đèn về phía Đông và để lại chiếc bánh ở đó. Lộ trình không nhất thiết phải đi thẳng, miễn là cuối cùng robot để lại bánh đúng vị trí.

Thật không may, robot chỉ được trang bị bộ nhớ rất hạn chế và không có logic nâng cao. Để điều khiển robot, bạn phải cung cấp cho nó một chương trình rất đơn giản ngay từ đầu. Chương trình này phải bao gồm một hoặc nhiều câu lệnh, mỗi câu lệnh cho robot biết phải làm gì trong những điều kiện nhất định. Các câu lệnh này phải có định dạng sau:

<S> <M> -> <action>

Điều này có nghĩa là nếu tất cả các điều kiện sau được đáp ứng:

1. Robot đang ở trạng thái S.
2. Robot đang ở một cột đèn được đánh dấu bằng số M.

Thì nó sẽ thực hiện chính xác một trong các hành động sau:

1. Đánh dấu cột đèn hiện tại bằng một số mới, thay đổi trạng thái và di chuyển. Để thực hiện việc này, action phải có định dạng "D NS NM", trong đó D là hướng di chuyển (W cho hướng Tây và E cho hướng Đông), NS là trạng thái mới của robot và NM là dấu mới cho cột đèn hiện tại.
2. Để lại bánh tại vị trí hiện tại và tự hủy. Để thực hiện việc này, action phải có định dạng "R".

Nếu bạn đưa ra hai hoặc nhiều câu lệnh có cùng giá trị S và M, robot sẽ hoạt động sai và làm hỏng bánh.

Nếu tại bất kỳ thời điểm nào robot ở trạng thái \(X\) tại một cột đèn được đánh dấu \(Y\) mà không có câu lệnh nào với \(S=X\) và \(M=Y\), robot sẽ bối rối và ăn mất bánh.

Tất cả các trạng thái và dấu đánh phải là số nguyên có giá trị tuyệt đối không quá một triệu (\(10^6\)). Giả sử ban đầu robot ở trạng thái \(0\) và tất cả các cột đèn đều được đánh dấu bằng số \(0\).

Cho \(N\), hãy viết một chương trình để robot để lại bánh đúng nơi quy định. Chương trình của bạn phải sử dụng tối đa \(30\) câu lệnh và phải kết thúc trong vòng \(X\) bước.

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 bao gồm một dòng duy nhất chứa một số nguyên \(N\), cho biết cột đèn nơi robot phải để lại bánh.

Dữ liệu ra

Đối với mỗi bộ test, trước tiên hãy in ra "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng câu lệnh bạn sẽ sử dụng. Tiếp theo in ra y dòng, mỗi dòng đại diện cho một câu lệnh cho robot theo định dạng đã mô tả ở trên.

CẢNH BÁO: Phản hồi của giám khảo có thể mất nhiều hơn bình thường khoảng 5 giây vì đầu ra của bạn được chạy như một phần của quá trình xác thực.

Ràng buộc

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

Phân nhóm

• Test set 1 (Visible): \(0 \le N \le 500\); \(X = 250,000\) (\(2.5 \times 10^5\)).
• Test set 2 (Hidden): \(0 \le N \le 5000\); \(X = 150,000\) (\(1.5 \times 10^5\)).

Đ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
0
4
0

Case #1: 1
0 0 -> R
Case #2: 5
0 0 -> E 1 1
1 0 -> E 2 1
2 0 -> E 3 1
3 0 -> E -1 1
-1 0 -> R
Case #3: 3
0 0 -> E 1 1
0 1 -> R
1 0 -> W 0 1

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Program within a Program.

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

Mưa xói mòn đảo Atlantis cho tới khi đất biến mất. Bản đồ là lưới \(H\times W\), mỗi ô có độ cao đất không âm (mét) so với mực biển. Ngoài bản đồ có độ cao 0; ô cao 0 là nước, ô cao hơn là đất.

Nước chảy từ ô nguồn sang ô chung cạnh nếu mực nước ở đích không cao hơn nguồn. Mưa rất nhanh: nếu chưa có lối chảy, nước tích lại tới khi có. Ngoài bản đồ nhận vô hạn nước. Với bản đồ:

5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9

gọi mực nước là độ cao đất cộng độ sâu nước, trạng thái nhanh chóng thành:

5 9 9 9 9 9
0 8 9 5 5 5
3 9 9 9 9 9

Ô 0 ở giữa không nối ra ngoài nên chứa nước; ô 0 ở biên nối được ra ngoài. Nếu có nhiều đích chảy, nước chọn ô có mực thấp nhất (hòa không ảnh hưởng).

Mỗi cuối ngày, nếu nước chảy từ \(S\) sang \(T\), đất ở \(S\) giảm \(\min(\text{WaterLevel}(S)-\text{WaterLevel}(T),M)\). Mọi ô xói mòn đồng thời. Với \(M=5\), bản đồ thành:

0 4 4 4 4 4
0 3 5 0 2 0
0 4 4 4 4 4

Nước dư chảy đi và nước lại tích, cho mực:

0 4 4 4 4 4
0 3 5 2 2 0
0 4 4 4 4 4

Sau ngày tiếp theo:

0 0 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0

Hãy tính số ngày tới khi mọi độ cao bằng 0.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(H,W,M\), sau đó \(H\) dòng, mỗi dòng \(W\) độ cao.

Dữ liệu ra

In Case #x: y, với \(y\) là số ngày đảo bị xói mòn hoàn toàn.

Ràng buộc

• \(1\le T\le40\); bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(1\le H,W\le10\), \(1\le M\le100\), độ cao 0–100.
• Lớn: \(1\le H,W\le20\), \(1\le M\le10^{15}\), độ cao 0–\(10^{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
3 6 5
5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9
3 6 3
3 8 10 11 10 8
7 5 2 12 8 8
6 9 11 9 8 4

Case #1: 3
Case #2: 5

3 8 10 11 10 8
7 7 7 12 8 8
6 9 11 9 8 4

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

0 2 4 5 4 2
1 4 2 6 5 2
0 3 5 3 2 0

0 0 1 2 1 0
0 1 2 3 2 0
0 0 2 0 0 0

0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Rains Over Atlantis.

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

Tôi có một chuỗi \(S\) bao gồm các ký tự chữ cái viết thường từ 'a' đến 'z'. Mỗi dãy ký tự giống nhau liên tiếp dài nhất được gọi là một "run" (đoạn chạy). Ví dụ, chuỗi "bookkeeper" có 7 runs. Có bao nhiêu hoán vị khác nhau của \(S\) có đúng số lượng runs bằng với số lượng runs của \(S\)?

Hai hoán vị \(a\) và \(b\) được coi là khác nhau nếu tồn tại một vị trí \(i\) mà tại đó chúng có ký tự khác nhau: \(a[i] \neq b[i]\).

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\) dòng tiếp theo, mỗi dòng chứa một chuỗi duy nhất \(S\) gồm các ký tự chữ cái viết thường và không rỗng.

Dữ liệu ra

Đối 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ự bộ dữ liệu (bắt đầu từ 1) và y là số lượng hoán vị khác nhau của \(S\) có đúng số lượng runs bằng với \(S\), lấy modulo \(1000003\).

Ràng buộc

• \(1 \le T \le 100\).
• \(S\) có độ dài ít nhất 1 ký tự.

Phân nhóm

• Test set 1 (Visible): \(S\) có độ dài tối đa 100 ký tự.
• Test set 2 (Hidden): \(S\) có độ dài tối đa \(450,000\) ký tự. \(S\) có tối đa 100 runs. Kích thước tệp đầu vào không quá 1 megabyte.

Đ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
aabcd
bookkeeper

Case #1: 24
Case #2: 7200

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Runs.

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