Google Code Jam 2011 - Round 2

Giới thiệu

A.I. War là một trò chơi chiến thuật thời gian thực được phát triển bởi Arcen Games. Bài toán này được lấy cảm hứng từ trò chơi đó, nhưng không yêu cầu bạn phải từng chơi nó.

Bài toán

Bạn đang đối mặt với một trí tuệ nhân tạo (A.I.) trong một cuộc chiến sinh tử vì tương lai của thiên hà. Để đánh bại A.I., bạn cần đe dọa hành tinh quê hương của nó. Một số hành tinh được kết nối với nhau bằng các lỗ sâu (wormhole); bất kỳ hành tinh nào cũng có thể được kết nối với bất kỳ số lượng hành tinh nào khác bằng các lỗ sâu này.

Bạn bắt đầu bằng việc chỉ sở hữu hành tinh quê hương của mình. Mỗi lượt, bạn có thể chinh phục bất kỳ hành tinh nào mà bạn đe dọa. Bạn đe dọa một hành tinh nếu bạn không sở hữu nó, và nó được kết nối bằng một lỗ sâu với bất kỳ hành tinh nào bạn đang sở hữu. Khi bạn đã chinh phục một hành tinh, bạn sở hữu nó. Ngay khi bạn đe dọa hành tinh quê hương của A.I., bạn không được phép chinh phục thêm bất kỳ hành tinh nào nữa.

Trong khi tham gia ngày quan trọng nhất tại trường chiến thuật, bạn đã khám phá ra hai điều về A.I.:

• Với mỗi hành tinh bạn chinh phục, A.I. sẽ trở nên mạnh mẽ hơn, vì nó coi bạn là một mối đe dọa và sản xuất thêm nhiều tàu để tự vệ.
• A.I. sẽ phòng thủ mọi hành tinh mà bạn hiện đang đe dọa.

Bạn đã kết hợp hai sự thật đó để tạo ra một chiến lược:

1. Bạn sẽ chinh phục các hành tinh cho đến khi bạn đe dọa được căn cứ quê hương của A.I.
2. Nếu có nhiều cách để hoàn thành bước 1, hãy thực hiện sao cho số lượng hành tinh bị chinh phục là ít nhất có thể.
3. Nếu có nhiều cách để hoàn thành bước 2, hãy thực hiện sao cho cuối cùng bạn đe dọa được số lượng hành tinh là nhiều nhất có thể.

Cho biết các hành tinh và các lỗ sâu, bạn sẽ chinh phục bao nhiêu hành tinh và đe dọa bao nhiêu hành tinh trên đường đến căn cứ quê hương của A.I. nếu bạn tuân theo chiến lược mô tả ở trên?

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 nối tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên cách nhau bởi dấu cách: P, số lượng hành tinh, và W, số lượng lỗ sâu. Hành tinh quê hương của bạn là hành tinh 0, và hành tinh quê hương của A.I. là hành tinh 1.

Dòng thứ hai của mỗi bộ test sẽ chứa W cặp số nguyên cách nhau bởi dấu phẩy, các cặp cách nhau bởi dấu cách \(x_i\),\(y_i\). Mỗi cặp này cho biết có một lỗ sâu hai chiều kết nối các hành tinh \(x_i\) và \(y_i\).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: c t", trong đó x là số thứ tự bộ test (bắt đầu từ 1), c là số lượng hành tinh bạn chinh phục nếu tuân theo chiến lược trên, và t là số lượng hành tinh bạn đe dọa ở thời điểm kết thúc (bao gồm cả hành tinh quê hương của A.I.).

Ràng buộc

• 1 ≤ T ≤ 50.
• 0 ≤ \(x_i\) < \(y_i\) < P.
• Mỗi lỗ sâu là duy nhất: Nếu i ≠ j, thì (\(x_i\), \(y_i\)) ≠ (\(x_j\), \(y_j\)).
• Sẽ luôn có ít nhất một cách để đi từ hành tinh quê hương của bạn đến hành tinh quê hương của A.I. bằng một chuỗi các lỗ sâu.

Phân nhóm

• Small dataset (Test set 1): 2 ≤ P ≤ 36; 1 ≤ W ≤ 630.
• Large dataset (Test set 2): 2 ≤ P ≤ 400; 1 ≤ W ≤ 2000.

Đ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
2 1
0,1
3 3
0,1 1,2 0,2
5 5
0,4 0,2 2,4 1,2 1,4
7 9
0,6 0,2 0,4 2,4 3,4 2,3 3,5 4,5 1,5

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

Nguồn

Google Code Jam 2011, Vòng 2, bài A.I. War.

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 ở trong một sân bay, đứng tại điểm 0. Một hành lang có chiều dài \(X\) dẫn đến cổng khởi hành, nơi máy bay của bạn sắp cất cánh. Có những băng chuyền chuyển động trong hành lang, mỗi băng chuyền di chuyển với tốc độ \(w_i\). Khi bạn đi bộ hoặc chạy trên một trong những băng chuyền đó, bạn sẽ di chuyển với tốc độ (tốc độ của bạn + \(w_i\)). Các băng chuyền không thay đổi vị trí; chúng chỉ giúp bạn di chuyển nhanh hơn. Các băng chuyền không chồng lấn lên nhau: tại bất kỳ điểm nào trên hành lang, có tối đa một băng chuyền, nhưng một băng chuyền có thể bắt đầu tại điểm mà một băng chuyền khác kết thúc.

Tốc độ đi bộ bình thường của bạn là \(S\). Tuy nhiên, bạn lo lắng rằng mình có thể không kịp chuyến bay, vì vậy bạn có thể chạy một chút - bạn có thể chạy với tốc độ \(R\) trong tổng cộng tối đa \(t\) giây. Bạn không nhất thiết phải chạy trong \(t\) giây liên tục: bạn có thể chia \(t\) giây này thành bất kỳ số lượng khoảng thời gian nào, hoặc thậm chí không sử dụng hết chúng.

Bạn mất bao lâu để đến được cổng, giả sử bạn chọn khi nào đi bộ và khi nào chạy để đến nơi sớm nhất có thể?

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 năm số nguyên: \(X\) (chiều dài hành lang, tính bằng mét), \(S\) (tốc độ đi bộ của bạn, tính bằng mét trên giây), \(R\) (tốc độ chạy của bạn, tính bằng mét trên giây), \(t\) (thời gian chạy tối đa, tính bằng giây) và \(N\) (số lượng băng chuyền).

Mỗi dòng trong số \(N\) dòng tiếp theo chứa ba số nguyên: \(B_i\), \(E_i\) và \(w_i\) - điểm bắt đầu và điểm kết thúc của băng chuyền (tính bằng mét từ điểm xuất phát của bạn) và tốc độ của băng chuyền (tính bằng mét trên giây).

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à thời gian (tính bằng giây) bạn cần để đến điểm \(X\) nếu bạn đi bộ và chạy một cách tối ưu. 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 chấp nhận.

Ràng buộc

• \(1 \le T \le 40\).
• \(1 \le S < R \le 100\).
• \(1 \le w_i \le 100\).
• \(0 \le B_i < E_i \le X\).
• \(E_i \le B_{i+1}\).

Phân nhóm

• Small dataset (Test set 1):

  • \(1 \le t \le 100\).
  • \(1 \le X \le 100\).
  • \(1 \le N \le 20\).

• Large dataset (Test set 2):

  • \(1 \le t \le 10^6\).
  • \(1 \le X \le 10^6\).
  • \(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
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

Nguồn

Google Code Jam 2011, Vòng 2, bài Airport Walkways.

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ất cả bạn bè của bạn sẽ đi ăn tối tại một nhà hàng tối nay. Họ đều rất giỏi toán, nhưng họ cũng rất kỳ lạ: người bạn thứ \(a\) của bạn (bắt đầu từ 1) sẽ không vui trừ khi tổng chi phí của bữa ăn là một số nguyên dương và chia hết cho \(a\).

Các bạn của bạn lần lượt vào nhà hàng từng người một. Ngay khi có ai đó bước vào nhà hàng, nếu người đó không vui thì cả nhóm sẽ gọi phục vụ ngay lập tức.

Miễn là có ít nhất một người không vui trong nhà hàng, một trong những người không vui đó sẽ mua món đồ có giá thấp nhất để làm cho anh ta hoặc cô ta vui. Điều này sẽ tiếp tục cho đến khi không còn ai trong nhà hàng không vui, và sau đó người phục vụ sẽ rời đi. May mắn thay, nhà hàng bán đồ ăn ở mọi mức giá nguyên dương. Xem phần giải thích của ví dụ đầu tiên để biết thêm chi tiết.

Các bạn của bạn có thể chọn vào nhà hàng theo bất kỳ thứ tự nào. Sau khi người phục vụ đã được gọi, nếu có nhiều hơn một người không vui trong nhà hàng, bất kỳ ai trong số những người không vui đó đều có thể chọn mua một thứ gì đó trước. Cách thức thực hiện tất cả các lựa chọn đó có thể ảnh hưởng đến số lần nhóm gọi phục vụ.

Là chủ nhà hàng, bạn thuê một số người phục vụ rất mệt mỏi. Bạn muốn tính độ chênh lệch (spread) của những người bạn của mình: sự khác biệt giữa số lần tối đa họ có thể gọi phục vụ và số lần tối thiểu họ có thể gọi phục vụ.

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ộ trên một dòng. Mỗi bộ test sẽ chứa một số nguyên \(N\), số lượng bạn bè mà bạn có.

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à độ chênh lệch cho bộ test đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N \le 1000\) (Dữ liệu nhỏ).
• \(1 \le N \le 10^{12}\) (Dữ liệu lớn).

Phân nhóm

Các giới hạn cho tập nhỏ và tập lớn được nêu ở trê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ụ

4
1
3
6
16

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

Nguồn

Google Code Jam 2011, Vòng 2, bài Expensive Dinner.

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

Vì đã chán với những cái bẫy trong thiết kế căn cứ bí mật của mình, bạn quyết định chọn một thứ gì đó cổ điển nhưng luôn thú vị - lưỡi dao xoay. Bạn đã đặt hàng một tấm kim loại rất nặng, từ đó bạn sẽ cắt ra lưỡi dao; một lưới ô vuông đồng nhất kích thước \(C \times R\) sẽ được vẽ trên tấm kim loại. Bạn đã xác định được hình dạng tốt nhất cho lưỡi dao -- trước tiên bạn sẽ cắt một hình vuông lớn gồm \(K \times K\) ô lưới, với \(K \ge 3\). Sau đó, bạn sẽ cắt bỏ bốn ô góc \(1 \times 1\) của hình vuông đó để tạo thành một lưỡi dao. Sau khi xác định xong tất cả những điều này, bạn bắt đầu đợi tấm kim loại được giao đến.

Khi tấm kim loại đến nơi, bạn đã bị sốc khi phát hiện ra rằng nó có những khiếm khuyết! Bạn mong đợi mỗi ô có khối lượng \(D\), nhưng hóa ra khối lượng có thể thay đổi một chút do sự khác biệt về độ dày. Điều này thật tệ vì bạn muốn lắp một trục xoay chính xác vào tâm của lưỡi dao và xoay nó thật nhanh, vì vậy trọng tâm của lưỡi dao cũng phải nằm chính xác tại tâm của nó. Định nghĩa về trọng tâm của một vật thể phẳng có thể được tìm thấy bên dưới.

Cho lưới và khối lượng của từng ô, kích thước lớn nhất có thể của lưỡi dao mà bạn có thể tạo ra để trọng tâm nằm chính xác ở tâm của nó là bao nhiê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ộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa 3 số nguyên: \(R, C\) và \(D\) — kích thước của lưới và khối lượng bạn mong đợi mỗi ô sẽ có. \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) chữ số \(w_{ij}\), cho biết sự chênh lệch giữa khối lượng thực tế và khối lượng mong đợi của các ô lưới. Mỗi ô có mật độ đồng nhất, nhưng có thể có khối lượng nguyên trong khoảng từ \(D + 0\) đến \(D + 9\), bao gồm cả hai đầu.

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: \(K\)", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(K\) là kích thước lớn nhất có thể của lưỡi dao bạn có thể cắt ra. Nếu không tìm thấy lưỡi dao chấp nhận được nào có kích thước ít nhất là 3, hãy in "IMPOSSIBLE" thay thế.

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le w_{ij} \le 9\).
• Kích thước tệp đầu vào không quá 625KB.

Phân nhóm

• Test set 1 (Visible): \(3 \le R \le 10, 3 \le C \le 10, 1 \le D \le 100\).
• Test set 2 (Hidden): \(3 \le R \le 500, 3 \le C \le 500, 1 \le D \le 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ụ

2
6 7 2
1111111
1122271
1211521
1329131
1242121
1122211
3 3 7
123
234
345

Case #1: 5
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2011, Vòng 2, bài Spinning Blade.

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