Google Code Jam 2008 - APAC Semifinal

Ôi không! Sự cân bằng chính trị mỏng manh của thế giới cuối cùng đã sụp đổ, và mọi quốc gia đều đã tuyên chiến với nhau. Bạn đã cảnh báo bất cứ ai sẵn lòng lắng nghe rằng điều này sẽ xảy ra, nhưng họ có chú ý không? Ha! Bây giờ điều duy nhất bạn có thể hy vọng là sống sót càng lâu càng tốt.

May mắn thay (có thể coi là vậy), các trung tâm công nghiệp của mọi quốc gia đều đã bị ném bom nguyên tử, vì vậy phương thức tấn công duy nhất còn lại là tung ra hết đợt lính nghĩa vụ này đến đợt lính nghĩa vụ khác vào nhau. Điều này giới hạn mỗi quốc gia chỉ có thể tấn công các nước láng giềng trực tiếp của mình. Thế giới là một lưới \(R \times C\) với \(R\) hàng, được đánh số từ 1 ở cực Bắc đến \(R\) ở cực Nam, và \(C\) cột, được đánh số từ 1 ở cực Tây đến \(C\) ở cực Đông. Mỗi quốc gia chiếm một ô của lưới, có nghĩa là mỗi quốc gia có thể tiếp cận tối đa 4 quốc gia láng giềng liền kề.

Mọi quốc gia bắt đầu với một giá trị sức mạnh cụ thể mà ai cũng biết. Họ không có khái niệm về chiến lược nâng cao, vì vậy vào đầu mỗi ngày, họ sẽ chỉ đơn giản chọn người hàng xóm mạnh nhất của mình (ưu tiên quốc gia ở phía Bắc nhất, sau đó là phía Tây nhất nếu có kết quả hòa) và tấn công họ bằng một đội quân. Đội quân sẽ có sức mạnh bằng với sức mạnh hiện tại \(S\) của quốc gia đó; vào cuối ngày, nó sẽ làm giảm sức mạnh của người hàng xóm đó đi một lượng là \(S\). Một quốc gia có sức mạnh chạm mức 0 sẽ bị tiêu diệt. Lưu ý rằng tất cả các quốc gia tấn công cùng một lúc; sức mạnh của một đội quân là như nhau bất kể quốc gia đó có bị tấn công trong ngày hôm đó hay không.

Quốc gia của bạn nằm ở \((c, r)\), tại cột \(c\) và hàng \(r\). May mắn thay, quốc gia của bạn đang nghe theo lời khuyên của bạn, vì vậy bạn không cần phải tuân theo chiến lược điên rồ này. Bạn có thể chọn tấn công bất kỳ người hàng xóm nào của mình vào một ngày nhất định (hoặc không làm gì cả). Tuy nhiên, bạn không thể tấn công nhiều hàng xóm cùng lúc, hoặc tấn công với một đội quân có sức mạnh ít hơn sức mạnh tối đa hiện có.

Hãy xác định số ngày tối đa bạn có thể sống só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. T bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa bốn số nguyên, C, R, c, và r. R dòng tiếp theo, mỗi dòng chứa C số nguyên, cho biết sức mạnh bắt đầu \(S_{c_i,r_i}\) của quốc gia ở cột ci và hàng ri. Nó có thể bằng 0, cho biết quốc gia đó đã bị tiêu diệt. Sức mạnh bắt đầu của quốc gia bạn sẽ không phải là 0.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #A: " theo sau là:

• "B day(s)", trong đó B là số ngày nhiều nhất bạn có thể hy vọng sống sót.
• "forever", nếu bạn có thể sống lâu hơn tất cả những người hàng xóm của mình.

Ràng buộc

• \(1 \le T \le 100\)
• \(1 \le c \le C\)
• \(1 \le r \le R\)

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le C \le 5\)
• \(1 \le R \le 5\)
• \(0 \le S_{ci,ri} \le 10\)
• Large dataset (Test set 2 - Hidden):
• \(1 \le C \le 50\)
• \(1 \le R \le 50\)
• \(0 \le S_{ci,ri} \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 3 2 2
2 3 2
1 7 1
2 1 2
4 3 2 1
1 2 2 0
10 8 5 10
10 2 9 10

Case #1: forever
Case #2: 3 day(s)

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Apocalypse Soon.

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ời tham gia chương trình truyền hình nổi tiếng "Bạn có muốn trở thành triệu phú?". Tất nhiên là bạn muốn rồi!

Quy tắc của trò chơi rất đơn giản:

• Trước khi trò chơi bắt đầu, người dẫn chương trình quay một vòng quay may mắn để xác định \(P\), xác suất thắng mỗi lần đặt cược.
• Bạn bắt đầu với một số tiền: \(X\) đô la.
• Có \(M\) vòng đặt cược. Trong mỗi vòng, bạn có thể đặt cược bất kỳ phần nào trong số tiền hiện có của mình, kể cả không đặt gì hoặc đặt tất cả. Số tiền không giới hạn ở số nguyên đô la hay số nguyên cent.
  Nếu bạn thắng cược, tổng số tiền của bạn sẽ tăng thêm đúng bằng số tiền bạn đã đặt. Ngược lại, số tiền của bạn sẽ giảm đi đúng bằng số tiền đó.
• Sau khi tất cả các vòng đặt cược kết thúc, bạn chỉ được giữ lại số tiền thắng cuộc (lúc này số tiền được làm tròn xuống hàng đơn vị đô la) nếu bạn tích lũy được từ \(1.000.000\) đô la trở lên. Nếu không, bạn không được gì cả.

Cho \(M\), \(P\) và \(X\), hãy xác định xác suất bạn giành được ít nhất \(1.000.000\) đô la nếu bạn chơi một cách tối ưu (tức là bạn chơi sao cho tối đa hóa cơ hội trở thành triệu phú của mình).

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\).
Mỗi dòng trong \(N\) dòng tiếp theo có định dạng "\(M\) \(P\) \(X\)", trong đó:

• \(M\) là một số nguyên, số vòng đặt cược.
• \(P\) là một số thực, xác suất thắng mỗi vòng.
• \(X\) là một số nguyên, số tiền đô la ban đầu.

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.
• \(Y\) là xác suất trở thành triệu phú, nằm trong khoảng từ 0 đến 1.

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 N \le 100\)
• \(0 \le P \le 1.0\), có tối đa 6 chữ số sau dấu phẩy thập phân.
• \(1 \le X \le 1.000.000\)

Phân nhóm

• Small dataset (Test set 1): \(1 \le M \le 5\)
• Large dataset (Test set 2): \(1 \le M \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
1 0.5 500000
3 0.75 600000

Case #1: 0.500000
Case #2: 0.843750

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Millionaire.

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ó hình ảnh của hai tác phẩm điêu khắc. Các tác phẩm điêu khắc bao gồm nhiều quả cầu kim loại đặc và một số ống cao su nối các cặp quả cầu. Các ống trong mỗi tác phẩm được kết nối theo cách mà đối với bất kỳ cặp quả cầu nào, đều có đúng một đường đi men theo một chuỗi các ống (không lặp lại bất kỳ ống nào) giữa hai quả cầu đó. Tất cả các quả cầu đều có cùng bán kính và tất cả các ống đều có cùng chiều dài.

Bạn nghi ngờ rằng tác phẩm điêu khắc nhỏ hơn trong số hai tác phẩm thực chất được tạo ra bằng cách đơn giản là loại bỏ một số quả cầu và ống từ tác phẩm lớn hơn. Bạn muốn viết một chương trình để kiểm tra xem điều này có khả thi hay không.

Dữ liệu vào sẽ chứa một số bộ test. Một tác phẩm điêu khắc được mô tả bằng cách đánh số các quả cầu liên tiếp từ 1 và liệt kê các cặp quả cầu được nối với nhau bằng ống. Việc đánh số được chọn độc lập cho mỗi tác phẩm điêu khắc.

Dữ liệu vào

• Một dòng chứa một số nguyên C, số lượng bộ test trong file dữ liệu.

Đối với mỗi bộ test:

• Một dòng chứa số nguyên N, số lượng quả cầu trong tác phẩm điêu khắc lớn.
• N−1 dòng, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách, cho biết hai quả cầu có số hiệu đó trong tác phẩm điêu khắc lớn được nối với nhau bằng một ống.
• Một dòng chứa số nguyên M, số lượng quả cầu trong tác phẩm điêu khắc nhỏ.
• M−1 dòng, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách, cho biết hai quả cầu có số hiệu đó trong tác phẩm điêu khắc nhỏ được nối với nhau bằng một ống.

Dữ liệu ra

• C dòng, mỗi dòng cho một bộ test theo thứ tự xuất hiện trong file dữ liệu, chứa "Case #X: YES" nếu tác phẩm điêu khắc nhỏ trong trường hợp X có thể được tạo ra từ tác phẩm điêu khắc lớn trong trường hợp X, hoặc "Case #X: NO" nếu không thể. (X là số thứ tự của bộ test, từ 1 đến C.)

Ràng buộc

Phân nhóm

• Small dataset (Test set 1 - Visible):
  • 1 ≤ C ≤ 100
  • 2 ≤ N ≤ 8
  • 1 ≤ M < N
• Large dataset (Test set 2 - Hidden):
  • 1 ≤ C ≤ 50
  • 2 ≤ N ≤ 100
  • 1 ≤ M < 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ụ

2
5
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
5
1 2
1 3
1 4
4 5
4
1 2
2 3
3 4

Case #1: NO
Case #2: YES

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài Modern Art Plagiarism.

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 nghiên cứu các loài động vật trong một khu rừng và cố gắng xác định loài nào là chim và loài nào không phải.

Bạn thực hiện việc này bằng cách đo hai chỉ số của mỗi con vật – chiều cao và cân nặng của chúng. Để một con vật là chim, chiều cao của nó cần nằm trong một khoảng nhất định và cân nặng của nó cần nằm trong một khoảng khác, nhưng bạn không chắc chắn các khoảng chiều cao và cân nặng đó là gì. Bạn cũng biết rằng mọi con vật thỏa mãn các khoảng này đều là chim.

Bạn đã mang một số con vật mà bạn đo được cho các nhà sinh vật học xem, và họ đã cho bạn biết con nào là chim và con nào không. Điều này đã cung cấp cho bạn một số thông tin về các khoảng chiều cao và cân nặng của chim. Đối với những con vật còn lại, chương trình của bạn nên xác định xem chúng chắc chắn là chim, chắc chắn không phải chim, hoặc bạn không thể biết được từ thông tin hiện có.

Dữ liệu vào

Một dòng chứa một số nguyên C, số lượng bộ dữ liệu kiểm tra.

Sau đó, với mỗi bộ dữ liệu trong số C bộ:

• Một dòng chứa một số nguyên N, số lượng động vật bạn đã cho các nhà sinh vật học xem.
• N dòng, mỗi dòng cho một con vật, theo định dạng "H W X", trong đó H là chiều cao, W là cân nặng, và X là chuỗi "BIRD" hoặc "NOT BIRD". Tất cả các số đều là số nguyên dương.
• Một dòng chứa một số nguyên M, số lượng động vật bạn chưa cho các nhà sinh vật học xem.
• M dòng, mỗi dòng cho một con vật, theo định dạng "H W", trong đó H là chiều cao và W là cân nặng. Tất cả các số đều là số nguyên dương.

Dữ liệu ra

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

• Một dòng chứa chuỗi "Case #X: " trong đó X là số thứ tự của bộ dữ liệu, bắt đầu từ 1.
• M dòng, mỗi dòng chứa một trong các chuỗi "BIRD", "NOT BIRD", hoặc "UNKNOWN".

Ràng buộc

• \(1 \le \mathbf{C} \le 10\)
• \(1 \le\) tất cả chiều cao và cân nặng \(\le 1000000\)

Phân nhóm

• Small dataset: \(1 \le \mathbf{N} \le 10, 1 \le \mathbf{M} \le 10\).
• Large dataset: \(1 \le \mathbf{N} \le 1000, 1 \le \mathbf{M} \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
5
1000 1000 BIRD
2000 1000 BIRD
2000 2000 BIRD
1000 2000 BIRD
1500 2010 NOT BIRD
3
1500 1500
900 900
1400 2020
3
500 700 NOT BIRD
501 700 BIRD
502 700 NOT BIRD
2
501 600
502 501
1
100 100 NOT BIRD
3
107 93
86 70
110 115

Case #1:
BIRD
UNKNOWN
NOT BIRD
Case #2:
UNKNOWN
NOT BIRD
Case #3:
UNKNOWN
UNKNOWN
UNKNOWN

Nguồn

Google Code Jam 2008, Vòng bán kết châu Á - Thái Bình Dương, bài What are Birds?.

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