Bạn có biết công ty Just Ordinary Inventions không? Công việc của công ty này là tạo ra những “phát minh hết sức bình thường” (just ordinary inventions).

JOI đang chơi trò chơi mới nhất do công ty Just Ordinary Inventions phát triển.

Trong trò chơi này, người chơi khám phá một hầm ngục gồm một số căn phòng và các con đường. Mỗi con đường nối hai căn phòng khác nhau và có thể đi theo cả hai chiều. Giữa hai căn phòng khác nhau có nhiều nhất một con đường, và không có con đường nào có hai đầu là cùng một phòng. Có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác bằng một số con đường. Các phòng trông rất giống nhau: chỉ nhìn vào căn phòng thì hoàn toàn không thể phân biệt hai phòng có cùng số con đường đi ra.

Để hỗ trợ người chơi, mỗi phòng có một dấu mốc và một bệ đặt đá quý. Dựa vào dấu mốc, người chơi có thể đánh số các con đường đi ra từ phòng đó là \(1, 2, \ldots\). Cấu trúc hầm ngục không thay đổi trong suốt trò chơi, nên đi theo con đường có cùng số thứ tự từ cùng một phòng luôn dẫn đến cùng một phòng đích. Trên bệ có một viên đá quý mà người chơi có thể đổi màu. Màu của viên đá là một trong các màu \(1, 2, \ldots, X\). Khi trò chơi bắt đầu, đá quý trong mọi phòng đều có màu \(1\). Màu của chúng chỉ thay đổi khi người chơi chủ động đổi màu.

JOI nhận ra rằng nếu biết cấu trúc hầm ngục, tức là biết các phòng được nối với nhau như thế nào, thì sẽ dễ dàng chinh phục trò chơi. Tuy nhiên, dù thử nhiều cách, JOI vẫn không xác định được cấu trúc đó. Bạn quyết định viết một chương trình giúp JOI khám phá hầm ngục.

Yêu cầu

Hãy viết chương trình khám phá và xác định cấu trúc hầm ngục. Tuy nhiên, JOI không muốn được tiết lộ toàn bộ cấu trúc. Vì vậy, thay vì trả lời trực tiếp cấu trúc hầm ngục, với mỗi số nguyên \(i\) từ \(1\) đến \(R\), chương trình phải trả lời số cặp phòng có số con đường ít nhất cần đi qua để di chuyển giữa chúng bằng đúng \(i\). Hai cặp chỉ khác nhau ở thứ tự hai phòng được xem là cùng một cặp.

Thư viện được cung cấp cho phép thực hiện các thao tác sau:

• Biết số con đường đi ra từ phòng hiện tại.
• Biết màu viên đá quý trong phòng hiện tại.
• Đổi màu viên đá quý trong phòng hiện tại thành màu chỉ định, có thể là chính màu đang có; sau đó chọn một con đường đi ra từ phòng và di chuyển theo đường đó sang phòng khác.
• Biết con đường vừa đi qua mang số thứ tự nào trong các con đường đi ra từ phòng hiện tại.

Chi tiết cài đặt

Bạn phải viết một chương trình thực hiện việc trả lời cho JOI. Chương trình phải bao gồm tệp tiêu đề dungeon2.h:

#include "dungeon2.h"

Hàm cần cài đặt

void Inspect(int R);

Hàm này được gọi đúng một lần khi bắt đầu. Tham số R cho biết chương trình phải trả lời số cặp phòng có khoảng cách ngắn nhất bằng \(i\) với mỗi số nguyên \(i\) từ \(1\) đến \(R\). Thứ tự hai phòng trong một cặp không quan trọng.

Hàm trả lời

void Answer(int D, int A);

Lời gọi này trả lời rằng có \(A\) cặp phòng mà số con đường ít nhất cần đi qua để di chuyển giữa hai phòng bằng đúng \(D\).

Các lời gọi Answer phải thỏa mãn mọi điều kiện sau:

Nếu một lời gọi Answer bị đánh giá là sai, không có gì bảo đảm rằng chương trình sẽ tiếp tục được thực thi.

Các hàm dùng để khám phá

void Move(int I, int C);

Trước tiên, đổi viên đá quý trong phòng hiện tại, trước khi di chuyển sang màu C. Sau đó, người chơi đi theo con đường thứ I đi ra từ phòng này để đến phòng khác.

Các lời gọi Move phải thỏa mãn mọi điều kiện sau:

Trong tệp dungeon2.h được cung cấp, tham số màu được đặt tên là V, nên khai báo tương ứng là void Move(int I, int V);. Đây vẫn là cùng hàm Move với tham số thứ hai biểu thị màu cần đặt.

int NumberOfRoads();

Trả về số con đường đi ra từ phòng hiện tại.

int LastRoad();

Trả về số thứ tự của con đường vừa được dùng để di chuyển, theo cách đánh số tại phòng hiện tại. Nếu chưa từng gọi Move, hàm trả về \(-1\).

int Color();

Trả về màu viên đá quý trên bệ trong phòng hiện tại.

Sau khi lời gọi Inspect kết thúc, các câu trả lời sẽ được kiểm tra. Bạn được phép cài đặt các hàm phụ và khai báo biến toàn cục để sử dụng nội bộ. Tuy nhiên, chương trình nộp bài không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác bằng bất kỳ cách nào.

Cách nộp bài

Nộp một tệp mã nguồn C++ chứa hàm Inspect và include dungeon2.h được đính kèm theo bài. Không viết hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn. Hệ thống chấm đặt người chơi ban đầu trong một phòng cố định, cung cấp các hàm Move, NumberOfRoads, LastRoad, Color, Answer, rồi gọi Inspect đúng một lần.

Ràng buộc

Các ký hiệu \(N, D_i, T_{ij}\) có ý nghĩa như trong phần dữ liệu vào của trình chấm mẫu. Mọi bộ dữ liệu thỏa mãn:

• \(2 \le N \le 200\).
• \(3 \le X \le 100\).
• \(1 \le R \le 200\).
• \(1 \le D_i \le N-1\) với mọi \(1 \le i \le N\).
• \(1 \le T_{ij} \le N\) và \(T_{ij} \ne i\) với mọi \(1 \le i \le N\), \(1 \le j \le D_i\).
• Với mỗi \(1 \le i \le N\), các giá trị \(T_{i1}, T_{i2}, \ldots, T_{iD_i}\) đôi một khác nhau.
• Với mỗi \(1 \le i \le N\) và \(1 \le j \le D_i\), tồn tại \(k\) thỏa mãn:

• Có thể đi từ bất kỳ phòng nào đến bất kỳ phòng nào khác bằng một số con đường.

Các bài toán con

Gọi \(N\) là số phòng và \(M\) là số con đường trong hầm ngục của bộ dữ liệu.

1. 17 điểm: \(N \le 50\), \(M \le 100\), \(X=100\).
2. 27 điểm: \(N \le 50\), \(M \le 100\), \(X=3\).
3. 56 điểm: \(X=3\).

Cách tính điểm bài toán con 3

Trong mỗi bộ kiểm thử, gọi \(C\) là số lần gọi Move. Gọi \(L\) là giá trị lớn nhất của tỉ số sau trên tất cả các bộ kiểm thử của bài toán con 3:

Điểm của bài toán con 3 được tính chính xác như sau:

Ở đây, \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Trên hệ thống chấm, nếu chương trình kết thúc đúng cách và câu trả lời được đánh giá là đúng, cột chi tiết hiển thị Accepted. Tuy nhiên, khi chấm bài toán con 3, đối với một bộ kiểm thử thỏa mãn điều kiện dưới đây, cột kết quả sẽ hiển thị sai, ngay cả khi cột chi tiết hiển thị Accepted:

Ví dụ giao tiếp

Dưới đây là một ví dụ dữ liệu vào của trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0

Chuỗi lời gọi hàm

Lưu ý rằng các lời gọi trong ví dụ này không nhất thiết là những thao tác có ý nghĩa để giải bài toán.