Alice và Bob là những nhà ảo thuật nổi tiếng. Catherine, một người phụ nữ giàu có rất yêu thích các màn trình diễn tuyệt vời của họ, tuyên bố rằng cô sẽ tặng họ một khối tài sản lớn nếu họ thực hiện được trò ảo thuật sau:

1. Bob đi vào một căn phòng hoàn toàn cách biệt với bên ngoài. Bob chỉ có thể trao đổi với Catherine. Sau đó, Alice nói cho Catherine một số \(n\) trong khoảng từ \(2\) đến \(5\,000\).
2. Catherine nói cho Alice một số \(X\) trong khoảng từ \(1\) đến \(10^{18}\).
3. Alice tạo một cây có đúng \(n\) đỉnh và đưa cây đó cho Catherine.
4. Catherine xóa khỏi cây nhiều nhất

cạnh, rồi đưa các cạnh còn lại cho Bob.

1. Bob quan sát kỹ đồ thị nhận được và nói ra số mà Catherine đã nói cho Alice.

Alice và Bob không nghĩ mình đủ thông minh để luôn biểu diễn thành công trò ảo thuật này, nên họ cần bạn giúp đỡ. Hãy viết chương trình cài đặt chiến lược của Alice và chiến lược của Bob để họ vượt qua thử thách của Catherine.

Chi tiết cài đặt

Bạn cần nộp hai tệp chương trình riêng biệt, Alice.cpp và Bob.cpp. Hai chiến lược không thể truyền thông tin cho nhau bằng biến toàn cục hoặc trạng thái dùng chung.

Chương trình của Alice

Tệp Alice.cpp cài đặt chiến lược của Alice và phải khai báo thư viện Alice.h bằng chỉ thị tiền xử lý #include. Bạn cần cài đặt hàm:

std::vector<std::pair<int, int>> Alice();

• Trong mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần ở thời điểm bắt đầu.
• Hàm phải trả về một vector các cặp biểu diễn các cạnh của cây mà Alice tạo ở bước \(3\).
• Các đỉnh của cây phải được đánh số bắt đầu từ \(1\).
• Cây trả về phải hợp lệ: có đúng \(n-1\) cạnh và tất cả các đỉnh đều liên thông.

Hàm Alice() phải gọi hàm sau đúng một lần:

long long setN(int n);

Alice dùng lời gọi này để chọn tham số \(n\) đã nói cho Catherine ở bước \(1\). Hàm setN trả về giá trị \(X\) mà Catherine nói cho Alice ở bước \(2\).

Chương trình của Bob

Tệp Bob.cpp cài đặt chiến lược của Bob và phải khai báo thư viện Bob.h bằng chỉ thị tiền xử lý #include. Bạn cần cài đặt hàm:

long long Bob(std::vector<std::pair<int, int>> V);

• Trong mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần sau lời gọi hàm Alice().
• Tham số \(V\) là danh sách các cạnh của đồ thị mà Catherine đưa cho Bob ở bước \(4\).
• Các cạnh trong \(V\) được sắp xếp như sau:
  • Trong mỗi cạnh, đầu mút có số nhỏ hơn đứng trước.
  • Toàn bộ các cạnh được sắp xếp tăng dần theo đầu mút thứ nhất làm khóa chính, rồi theo đầu mút thứ hai làm khóa phụ.
• Hàm phải trả về một số nguyên biểu diễn giá trị \(X\).

Tương tác mẫu

Trình tự lời gọi và giá trị trả về trong ví dụ là:

Ví dụ này biểu diễn kịch bản sau:

1. Alice nói số \(4\) cho Catherine.
2. Catherine nói số \(3\) cho Alice.
3. Alice tạo một cây gồm \(4\) đỉnh và các cạnh {{1, 2}, {2, 3}, {2, 4}}, rồi đưa cây cho Catherine.
4. Catherine xóa cạnh nối đỉnh \(2\) với đỉnh \(3\), rồi đưa các cạnh còn lại {{1, 2}, {2, 4}} cho Bob.
5. Bob nói số \(3\). Vì câu trả lời đúng, Alice và Bob thực hiện thành công trò ảo thuật.

Ràng buộc

Phân nhóm

1. 5 điểm: \(X \le 5\,000\).
2. 30 điểm: \(X \le 25\,000\,000\).
3. 65 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc ở dòng đầu tiên một giá trị \(T\), trong đó \(T \in \{1,2\}\).

Nếu \(T=1\):

• Dòng \(2\) chứa \(X\) (\(1 \le X \le 10^{18}\)).
• Trình chấm mẫu gọi Alice() rồi in kết quả theo định dạng:
  • Dòng \(1\): \(n\).
  • Dòng \(2+i\) với \(0 \le i \le n-2\): \(u[i]\ v[i]\), biểu diễn một cạnh nối \(u[i]\) và \(v[i]\).

Nếu \(T=2\):

• Dòng \(2\) chứa \(n\ m\), trong đó \(2 \le n \le 5\,000\) và

với $n$ là số đỉnh và $m$ là số cạnh còn lại.

• Dòng \(3+i\) với \(0 \le i \le m-1\) chứa \(u[i]\ v[i]\), biểu diễn một cạnh nối \(u[i]\) và \(v[i]\).
• Trình chấm mẫu gọi Bob() rồi in \(X\) trên dòng đầu tiên.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài Magic Show. Đề và gói bài chính thức: APIO 2024 Tasks.