Chu trình trong danh sách liên kết
Đề bài
Mô tả
Đây là bài toán tương tác.
Trong khoa học máy tính, danh sách liên kết là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử (các nút) được nối với nhau bằng liên kết. Mỗi nút chứa dữ liệu và một tham chiếu (con trỏ) tới nút tiếp theo trong dãy. Cấu trúc này cho phép danh sách co giãn linh hoạt, vì các nút không cần nằm liên tiếp trong bộ nhớ như mảng.
Dưới đây là định nghĩa danh sách liên kết bằng C++:
struct Node {
int value;
Node* next; // pointer to the next node
}
struct LinkedList {
Node* head; // pointer to the first node of the linked list
}
Khi một nút trong danh sách liên kết trỏ tới một nút đứng trước nó trong danh sách, danh sách có một chu trình. Lưu ý rằng một nút có thể trỏ tới chính nó, khi đó chu trình có độ dài . Ví dụ, danh sách gồm nút trong đó nút trỏ lại nút có một chu trình độ dài (gồm các nút ).
Trong bài này, ban giám khảo chuẩn bị một trình tương tác, được khởi tạo với nút đầu của một danh sách liên kết bí mật gồm nút và có chu trình. Bạn không có bất kỳ thông tin nào về danh sách này, kể cả độ dài . Nhiệm vụ của bạn là tìm độ dài của chu trình.
Để làm việc đó, bạn có thể đánh dấu một số nút, và mỗi khi đến một nút, trình tương tác sẽ cho bạn biết nút đó đã được đánh dấu hay chưa. Cụ thể:
- Ban đầu, mọi nút đều chưa được đánh dấu.
- Trình tương tác có một biến con trỏ . Tại mọi thời điểm, trỏ tới một nút nào đó của danh sách. Ban đầu trỏ tới nút đầu.
- Bạn ra lệnh cho trình tương tác trong nhiều nhất lượt. Trong mỗi lượt:
- Bạn cho trình tương tác biết bạn muốn đánh dấu vĩnh viễn nút mà đang trỏ tới, hay không làm gì với nút này.
- Trình tương tác chuyển sang nút tiếp theo, tức là thực hiện phép gán .
- Trình tương tác cho bạn biết nút mà vừa trỏ tới đã được đánh dấu trước đó hay chưa.
- Sau đó, bạn cần xác định độ dài của chu trình.
Tương tác
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Đầu tiên, chương trình của bạn đọc số bộ dữ liệu (). Với mỗi bộ dữ liệu:
- Đầu tiên, chương trình của bạn tương tác với trình tương tác trong nhiều nhất lượt. Trong mỗi lượt:
- Chương trình của bạn in ra 1 nếu muốn đánh dấu vĩnh viễn nút mà đang trỏ tới, hoặc 0 nếu không.
- Sau đó chương trình của bạn đọc một ký tự : Y nếu nút mà trỏ tới (sau phép gán ) đã được đánh dấu trước đó, hoặc N nếu chưa.
- Sau đó chương trình của bạn in ra -1 để trả lời rằng độ dài chu trình là . Chương trình của bạn tiếp tục với bộ dữ liệu tiếp theo, hoặc kết thúc ngay nếu đây là bộ dữ liệu cuối cùng.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Sau mỗi lần in, đừng quên xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() trong C++, sys.stdout.flush() trong Python.
Ràng buộc
- .
- , tổng qua tất cả các bộ dữ liệu không vượt quá .
- Mỗi bộ dữ liệu được dùng nhiều nhất lượt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 N N N N N N N Y N Y |
0 0 1 0 1 0 0 0 1 1 -1 6 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Danh sách là danh sách nút ở trên (nút trỏ lại nút ). Chương trình đánh dấu nút và nút ; ở lượt thứ , quay lại nút đã đánh dấu (Y). Sau đó chương trình đánh dấu nút và nút (nút đã được đánh dấu từ trước): đến nút được N, đến nút được Y, và trả lời độ dài chu trình là . Đề gốc minh họa một cách tương tác khác trên cùng danh sách; ví dụ chỉ minh họa cách trao đổi, không minh họa cách suy ra đáp án. |
| 3 N N Y N N N N Y Y N N N N Y N |
0 0 1 -1 1 0 0 1 0 1 1 -1 1 0 0 1 0 1 1 -1 3 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: danh sách nút trỏ tới chính nó, lượt. Bộ thứ hai: nút, nút trỏ tới chính nó (chu trình độ dài ). Bộ thứ ba: nút, nút trỏ lại nút (chu trình độ dài ). |
Bình luận