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.