Giao diện chấm cục bộ

Gói này dùng giao diện C++17 sau thay cho chương trình đọc tệp salt.in:

#include "saltc.h"
void solve(int n, const int *u, const int *v);

Không định nghĩa main. Bộ chấm C++ đọc cây từ đầu vào chuẩn rồi gọi solve.
Hai mảng u, v có n-1 phần tử, chỉ số từ 0, mô tả các cạnh ban đầu.
Dùng hàm turn với quy ước bên dưới và trở về ngay khi nhận (0,0).
Không đọc đầu vào hoặc ghi đầu ra chuẩn trong lời giải.

Thư viện và đối thủ lịch sử không còn trong tài liệu được phát hành. Đối thủ
cục bộ dùng thuật toán giả ngẫu nhiên với hạt giống cố định; đây là bản thay thế
để kiểm tra luật chơi và API, không tái tạo đối thủ hoặc điểm số lịch sử.

Phần dưới giữ nguyên mô tả lịch sử; giao diện cục bộ ở trên được ưu tiên khi nộp bài.

SALT TREE XV là trò chơi dành cho hai người. Ban đầu, hai người được cho một cây. Họ luân phiên xóa một cạnh hoặc một đỉnh còn tồn tại. Khi xóa một cạnh, chỉ cạnh đó biến mất. Khi xóa một đỉnh, đỉnh đó cùng tất cả các cạnh đang nối với nó đều biến mất. Người xóa đỉnh cuối cùng là người thắng.

Có thể chứng minh rằng người đi trước luôn có chiến lược thắng, bất kể người đi sau chơi như thế nào. Hãy viết chương trình đóng vai người đi trước và luôn giành chiến thắng.

Cây là một đồ thị liên thông, không có chu trình và có ít nhất một đỉnh. Một đỉnh đứng riêng cũng là cây; một đồ thị có chu trình hoặc không liên thông thì không phải cây. Trong quá trình chơi, đồ thị còn lại không nhất thiết liên thông.

Đây là bài tương tác qua thư viện. Giới hạn thời gian là \(3\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Chương trình đọc cây ban đầu từ tệp salt.in:

• Dòng đầu chứa số nguyên \(n\), số đỉnh của cây. Các đỉnh được đánh số từ \(1\) đến \(n\).
• Trong \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên là hai đầu mút của một cạnh. Đầu mút có nhãn nhỏ hơn được ghi trước.

Mỗi cạnh xuất hiện đúng một lần. Thứ tự liệt kê các cạnh không có ý nghĩa.

Giao tiếp

Với C/C++, chương trình phải khai báo:

#include "saltc.h"

Thư viện cung cấp hàm:

void turn(int u, int v, int* ru, int* rv);

• Hai tham số \(u,v\) mô tả nước đi của bạn. Nếu \(u=v\), bạn xóa đỉnh \(u\). Nếu \(u<v\), bạn xóa cạnh nối \(u\) với \(v\). Không được truyền \(u>v\). Đỉnh hoặc cạnh được chọn phải còn tồn tại.
• ru và rv phải là hai con trỏ hợp lệ, trỏ đến hai vùng nhớ khác nhau.
• Sau lời gọi, *ru và *rv mô tả nước đi của đối thủ theo cùng quy ước: hai giá trị bằng nhau biểu thị xóa một đỉnh; giá trị thứ nhất nhỏ hơn giá trị thứ hai biểu thị xóa một cạnh. Luôn có *ru <= *rv.
• Nếu nước đi của bạn xóa đỉnh cuối cùng, thư viện trả về *ru = *rv = 0. Khi đó, chương trình phải kết thúc ngay, không gọi thêm bất kỳ hàm API nào.

Dữ liệu ra

Chương trình không được xuất bất kỳ dữ liệu nào. Hai chương trình dùng đầu vào và đầu ra chuẩn để liên lạc thông qua thư viện; chương trình của bạn không được tự đọc đầu vào chuẩn hoặc ghi đầu ra chuẩn vì điều đó có thể làm hỏng giao tiếp.

Ràng buộc

• \(1 \le n \le 1000\).
• Đồ thị ban đầu là một cây có các đỉnh được đánh số từ \(1\) đến \(n\).
• Mọi nước đi phải xóa một đỉnh hoặc một cạnh còn tồn tại.

Phân nhóm

Có \(5\) bộ dữ liệu, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố. Với mỗi bộ dữ liệu, chương trình chơi một số ván và chỉ nhận điểm nếu thắng tất cả các ván. Nếu có một ván mà chương trình đưa ra nước đi không hợp lệ, thua, hoặc kết thúc trước khi thắng, chương trình nhận \(0\) điểm cho bộ dữ liệu đó.

1. Bộ dữ liệu 1: \(20\) điểm nếu thắng tất cả các ván.
2. Bộ dữ liệu 2: \(20\) điểm nếu thắng tất cả các ván.
3. Bộ dữ liệu 3: \(20\) điểm nếu thắng tất cả các ván.
4. Bộ dữ liệu 4: \(20\) điểm nếu thắng tất cả các ván.
5. Bộ dữ liệu 5: \(20\) điểm nếu thắng tất cả các ván.

Ví dụ giao tiếp

Tệp salt.in chứa cây sau:

7
3 4
5 7
4 6
2 4
1 4
1 7

Cây ban đầu có dạng:

  2
  |
3-4-1-7-5
  |
  6

Sau đây là các nước đi đầu tiên trong một ván chơi minh họa:

Ngay sau khi bạn xóa cạnh \((5,7)\), đỉnh \(5\) vẫn còn nhưng đứng riêng:

  2
  |
3-4-1-7 5
  |
  6

Sau khi đối thủ xóa đỉnh \(4\), các cạnh \((2,4)\), \((3,4)\), \((4,6)\) và \((1,4)\) cũng biến mất:

  2

3   1-7 5

  6

Sau khi bạn xóa đỉnh \(3\), trạng thái trở thành:

  2

    1-7 5

  6

Các hình trên chỉ minh họa một phần ván chơi, chưa mô tả một ván kết thúc.