Google Code Jam 2012 - World Finals

Bạn đã đi bộ trong rừng hàng giờ và muốn về nhà.

Khu rừng có \(N\) khoảng trống được đánh số \(1, 2, \dots, N\). Hiện tại bạn đang ở khoảng trống 1, và bạn phải đến được khoảng trống \(N\) để rời khỏi khu rừng. Mỗi khoảng trống từ 1 đến \(N-1\) có một lối đi bên trái và một lối đi bên phải dẫn đến các khoảng trống khác, cũng như một số lối đi một chiều dẫn vào. Thật không may, khu rừng bị ám, và bất cứ khi nào bạn đi vào một khoảng trống, một trong hai lối đi ra sẽ bị chặn bởi những cái cây dịch chuyển. Chính xác hơn, trong lần ghé thăm thứ \(k\) của bạn tới bất kỳ một khoảng trống nào:

• Bạn phải rời đi theo lối đi bên trái nếu \(k\) là số lẻ.
• Bạn phải rời đi theo lối đi bên phải nếu \(k\) là số chẵn.
• Tất cả các lối đi đều là một chiều, vì vậy bạn không có lựa chọn nào ở mỗi bước: bạn phải đi tiếp qua lối đi duy nhất không bị chặn.

Vì vậy, lần đầu tiên bạn ở khoảng trống số 1, bạn sẽ rời đi theo lối đi bên trái. Nếu bạn quay lại khoảng trống số 1 lần thứ hai, bạn sẽ rời đi theo lối đi bên phải; lần thứ ba, bạn lại rời đi theo lối đi bên trái; và cứ thế tiếp tục.

Bạn bắt đầu tại khoảng trống số 1, và khi bạn đến khoảng trống số \(N\), bạn có thể rời khỏi khu rừng. Bạn cần đi qua bao nhiêu lối đi trước khi thoát ra ngoài?

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ộ bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\).

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\). Ở đây, \(L_i\) đại diện cho khoảng trống bạn sẽ đến nếu đi theo lối đi bên trái từ khoảng trống \(i\), và \(R_i\) đại diện cho khoảng trống bạn sẽ đến nếu đi theo lối đi bên phải từ khoảng trống \(i\).

Không có lối đi nào được chỉ định cho khoảng trống \(N\) vì khi bạn đến đó, bạn đã hoàn thành.

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ố lượng lối đi bạn cần thực hiện để đến được khoảng trống \(N\). Nếu bạn không bao giờ đến được khoảng trống \(N\), hãy xuất "Infinity" thay thế.

Ràng buộc

• \(1 \le T \le 30\).
• \(1 \le L_i, R_i \le N\) với mọi \(i\).

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(2 \le N \le 10\).
• Tập kiểm tra 2 (Hidden Verdict): \(2 \le N \le 40\).

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

Case #1: 8
Case #2: Infinity

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Shifting Paths.

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 nói rằng chúng ta phải tiến lên, không phải lùi lại; \n> đi lên, không phải tiến về phía trước; \n> và luôn xoay, xoay, xoay về phía tự do!” \n> — Kodos, cựu ứng cử viên Tổng thống Hoa Kỳ.

Sau khi nghe câu nói đầy cảm hứng này từ ứng cử viên tổng thống đầu tiên của Mỹ đến từ hành tinh Rigel VII, bạn đã quyết định rằng mình cũng muốn xoay (rotate) để hướng tới tự do. Trong bài toán này, bạn có thể coi "tự do" là việc ở cách xa vị trí xuất phát nhất có thể.

Thiên hà là một mặt phẳng hai chiều. Tàu vũ trụ của bạn bắt đầu tại gốc tọa độ, vị trí \((0, 0)\). Có \(N\) ngôi sao trong thiên hà. Mỗi phút, bạn có thể chọn một ngôi sao và xoay tàu vũ trụ của mình 90 độ theo chiều kim đồng hồ quanh ngôi sao đó. Bạn cũng có thể chọn đứng yên tại chỗ.

Hỏi bạn có thể đi bao xa so với gốc tọa độ sau \(M\) phút?

Hình ảnh minh họa 3 lần xoay đầu tiên cho một lộ trình có thể có trong ví dụ 1. Lưu ý rằng lộ trình này không nhất thiết phải là một phần của bất kỳ giải pháp tối ưu nào.

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, bắt đầu bằng hai dòng chứa các số nguyên \(N\) và \(M\). \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\), đại diện cho vị trí của các ngôi sao.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: \(D\)", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(D\) là khoảng cách từ gốc tọa độ đến vị trí cuối cùng tối ưu. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-6}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 100\);
• \(-1000 \le X_i \le 1000\);
• \(-1000 \le Y_i \le 1000\).
• Không có hai ngôi sao nào ở cùng một vị trí.
• Có thể có một ngôi sao tại gốc tọa độ.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 10\); \(1 \le M \le 10\).
• Test set 2 (Hidden): \(1 \le N \le 5000\); \(1 \le M \le 10^8\).

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

Case #1: 6.3245553203
Case #2: 10.0000000000
Case #3: 6.3245553203

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Twirling Towards Freedom.

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

Konstantin và Ilia sống cùng một nhà. Konstantin sống ở tầng trên và thích các hoạt động nhảy nhót, di chuyển đồ đạc và nói chung là gây tiếng ồn. Ilia sống ở tầng dưới và thích ngủ.

Để có một buổi tối vui vẻ, Konstantin muốn thực hiện ít nhất \(K\) hoạt động. Đêm qua, Ilia đã nhờ Konstantin cố gắng đừng làm anh ấy thức giấc; và vì Konstantin là một người hàng xóm rất tốt, anh ấy đã đồng ý. Tuy nhiên, anh ấy hiểu yêu cầu của Ilia hơi máy móc, và anh ấy sẽ chọn các hoạt động của mình sao cho giảm thiểu xác suất Ilia bị đánh thức sau khi đã ngủ.

Mỗi hoạt động có thể thực hiện của Konstantin có một xác suất đi kèm là \(a_i/b_i\). Nếu Konstantin thực hiện hoạt động này, thì sau khi kết thúc, Ilia sẽ thức với xác suất \(a_i/b_i\), và ngủ trong trường hợp ngược lại, bất kể trước đó anh ấy đang thức hay đang ngủ. Hơn nữa, đối với mỗi hoạt động, Konstantin có thể thực hiện tối đa \(c_i\) lần (nhiều hơn thế sẽ gây nhàm chán, và Konstantin sẽ không có một buổi tối vui vẻ nếu anh ấy thấy chán).

Konstantin muốn chọn một số lượng hoạt động để thực hiện theo thứ tự, sao cho:

• Tổng số hoạt động được thực hiện ít nhất là \(K\).
• Hoạt động thứ \(i\) được thực hiện không quá \(c_i\) lần.
• Xác suất \(Q\) mà Ilia bị đánh thức một hoặc nhiều lần trong suốt quá trình thực hiện các hoạt động là nhỏ nhất có thể.

Ilia bắt đầu ở trạng thái thức, vì vậy để anh ấy bị đánh thức, anh ấy phải đang ngủ ở cuối một hoạt động nào đó, và sau đó thức dậy ở cuối hoạt động tiếp theo.

\(Q\) nhỏ nhất mà Konstantin có thể đạt được trong khi vẫn có một buổi tối vui vẻ là bao nhiêu? Lưu ý rằng Konstantin không thể biết Ilia đang thức hay đang ngủ, vì vậy anh ấy không thể điều chỉnh các hoạt động của mình dựa trên thông tin đó.

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 cặp số nguyên \(N, K\) trên một dòng riêng biệt. \(N\) dòng tiếp theo, mỗi dòng đại diện cho một hoạt động mà Konstantin có thể chọn. Mỗi dòng có định dạng a_i/b_i c_i, cho biết có một hoạt động sẽ khiến Ilia thức với xác suất \(a_i/b_i\) và Konstantin có thể thực hiện tối đa \(c_i\) lần mà không bị chán.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa Case #x: Q, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(Q\) là xác suất nhỏ nhất Ilia bị đánh thức trong quá trình thực hiện các hoạt động của Konstantin. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-6}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le a_i \le b_i \le 1000000\) với mọi \(i\).
• \(1 \le b_i\) và \(1 \le c_i\) với mọi \(i\).
• \(1 \le K \le\) tổng tất cả các \(c_i\) trong bộ test đó.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 100\); Tổng tất cả các \(c_i\) không quá 100.
• Test set 2 (Hidden): \(1 \le N \le 10000\); Tổng tất cả các \(c_i\) không quá \(10^6\).

Đ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/2 3
1/5 2
2/5 1
2/2 2
3 2
1/2 2
1/3 2
3/4 2
3 3
99/100 1
1/2 2
1/50 3

Case #1: 0.000000000
Case #2: 0.083333333
Case #3: 0.015000000

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Upstairs/Downstairs.

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

Ngày xửa ngày xưa, một nền văn minh ngoài hành tinh đã xây dựng một tượng đài khổng lồ. Sàn của tượng đài trông như thế này:

###############
#.............#
#.###########.#
#.#.........#.#
#.#.#######.#.#
#.#.#.....#.#.#
#.#.#.###.#.#.#
#.#.#.#.#.#.#.#
#.#.#.###.#.#.#
#.#.#.....#.#.#
#.#.#######.#.#
#.#.........#.#
#.###########.#
#.............#
###############

Mỗi ký tự # đại diện cho một viên gạch màu đỏ, và mỗi ký tự . đại diện cho một viên gạch màu xanh. Hoa văn này kéo dài hàng dặm (đối với mục đích của bài toán này, bạn có thể giả định nó là vô tận). Ngày nay, chỉ còn lại một vài viên gạch. Những viên còn lại đã bị hư hại bởi mưa methane và bão bụi. Cho biết vị trí và màu sắc của các viên gạch còn lại, bạn có thể tìm thấy tâm của hoa văn 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ộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa \(N\), số lượng viên gạch còn lại. \(N\) dòng tiếp theo, mỗi dòng chứa \(X_i\), \(Y_i\), và màu của viên gạch (hoặc # hoặc .).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #c: \(X\) \(Y\)", trong đó c là số thứ tự bộ test (bắt đầu từ 1) và (\(X\), \(Y\)) là vị trí tâm của hoa văn. Nếu có nhiều hơn một câu trả lời khả thi, hãy xuất (\(X\), \(Y\)) gần (\(0, 0\)) nhất theo khoảng cách Manhattan (khoảng cách theo x cộng với khoảng cách theo y). Nếu vẫn còn hòa, hãy xuất điểm có \(X\) lớn nhất. Nếu vẫn còn hòa sau đó, hãy xuất điểm có \(Y\) lớn nhất. Nếu không có câu trả lời khả thi, hãy xuất "Case #c: Too damaged".

Ràng buộc

• \(1 \le T \le 50\).
• Danh sách các tọa độ trong mỗi bộ test sẽ không chứa các phần tử trùng lặp.

Phân nhóm

• Test set 1 (Visible Verdict):
• \(1 \le N \le 100\).
• \(-100 \le X_i \le 100\).
• \(-100 \le Y_i \le 100\).
• Test set 2 (Hidden Verdict):
• \(1 \le N \le 1000\).
• \(-10^{15} \le X_i \le 10^{15}\).
• \(-10^{15} \le Y_i \le 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ụ

6
1
0 0 .
1
0 0 #
3
0 0 #
0 1 #
1 0 #
5
50 30 #
49 30 #
49 31 #
49 32 #
50 32 #
2
-98 0 #
99 50 .
4
88 88 .
88 89 .
89 88 .
89 89 .

Case #1: 0 0
Case #2: 1 0
Case #3: 1 1
Case #4: 50 31
Case #5: 1 0
Case #6: Too damaged

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Xeno-archaeology.

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 Zombie Smash: một trò chơi mà mục tiêu là đập những con zombie bằng chiếc Búa Đập Zombie tin cậy khi chúng hiện ra từ các ngôi mộ trong nghĩa địa. Nghĩa địa được biểu diễn bằng một lưới 2D phẳng. Mỗi con zombie sẽ hiện ra từ một ngôi mộ tại một ô \((X, Y)\) trên lưới, đứng yên trong \(1000\) mili giây (ms), sau đó biến mất trở lại vào mộ. Tại một thời điểm, có tối đa một con zombie đứng quanh một ngôi mộ.

Bạn có thể di chuyển đến bất kỳ ô nào trong số 8 ô kề với vị trí hiện tại của mình trong \(100\) ms; tức là bạn có thể di chuyển theo hướng Bắc, Đông, Nam, Tây, Tây Bắc, Đông Bắc, Tây Nam và Đông Nam từ vị trí hiện tại. Bạn có thể đi xuyên qua hoặc đứng trên một ô ngay cả khi nó đang có zombie. Bạn có thể đập một con zombie ngay lập tức khi bạn đến ô mà zombie đó đang đứng, nhưng sau khi đập một con zombie, bạn phải mất \(750\) ms để Búa Đập Zombie sạc lại trước khi có thể đập con zombie tiếp theo. Bạn có thể di chuyển trong khi búa đang sạc. Ví dụ, ngay sau khi đập một con zombie tại \((0, 0)\):

• Sẽ mất \(750\) ms để đến và đập một con zombie tại \((1, 1)\) hoặc
• Mất \(2000\) ms để đến và đập một con zombie tại \((20, 20)\).

Bạn bắt đầu tại ô \((0, 0)\) khi bắt đầu trò chơi (thời điểm \(= 0\)). Sau khi chơi một màn, bạn muốn biết mình có thể đập được tối đa bao nhiêu con zombie nếu chơi một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất T, số lượng bộ thử nghiệm. Tiếp theo là T bộ thử nghiệm, mỗi bộ bắt đầu bằng một dòng chứa một số nguyên duy nhất Z, số lượng zombie trong màn chơi.

Z dòng tiếp theo, mỗi dòng chứa 3 số nguyên cách nhau bởi dấu cách, đại diện cho vị trí và thời điểm mà một con zombie cụ thể sẽ xuất hiện và biến mất. Dòng thứ i sẽ chứa các số nguyên X\(_i\), Y\(_i\) và M\(_i\), trong đó:

• X\(_i\) là tọa độ X của ô mà zombie i xuất hiện,
• Y\(_i\) là tọa độ Y của ô mà zombie i xuất hiện,
• M\(_i\) là thời điểm zombie i xuất hiện, tính bằng mili giây kể từ khi bắt đầu trò chơi. Khoảng thời gian mà zombie có thể bị đập là bao gồm cả hai đầu: nếu bạn đến ô đó tại bất kỳ thời điểm nào trong khoảng [M\(_i\), M\(_i\) + 1000] với chiếc búa đã sạc đầy, bạn có thể đập con zombie ở ô đó.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #c: d", trong đó c là số thứ tự bộ thử nghiệm (bắt đầu từ 1), và d là số lượng zombie tối đa bạn có thể đập được trong màn chơi này.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(-1000 \le \mathbf{X}_i, \mathbf{Y}_i \le 1000\).
• \(0 \le \mathbf{M}_i \le 100000000 = 10^8\).
• Hai con zombie sẽ không bao giờ ở cùng một vị trí tại cùng một thời điểm. Nói cách khác, nếu một con zombie xuất hiện tại \((x, y)\) vào thời điểm \(t\), thì bất kỳ con zombie nào khác xuất hiện tại \((x, y)\) phải xuất hiện vào hoặc trước \((t - 1001)\), hoặc vào hoặc sau \((t + 1001)\).

Phân nhóm

• Tập thử nghiệm 1 (Visible Verdict): \(1 \le \mathbf{Z} \le 8\).
• Tập thử nghiệm 2 (Hidden Verdict): \(1 \le \mathbf{Z} \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
4
1 0 0
-1 0 0
10 10 1000
10 -10 1000
3
1 1 0
2 2 0
3 3 0
5
10 10 1000
-10 10 1000
10 -10 1000
-10 -10 1000
20 20 2000

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

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Zombie Smash.

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