Bạn đang khảo sát một hang động có \(N\) căn phòng. Các lối đi ngầm nối hai chiều một số cặp phòng. Mỗi phòng nối với ít nhất một lối đi. Không lối đi nào nối một phòng với chính nó, và không có hai phòng nào được nối bởi nhiều hơn một lối đi.

Khi ở trong một phòng, bạn xác định được số hiệu phòng và nhìn thấy có bao nhiêu lối đi nối với nó, nhưng không thể phân biệt các lối đi. Bạn muốn ước lượng tổng số lối đi trong hang và được phép thực hiện nhiều nhất \(K\) thao tác. Mỗi thao tác là một trong hai loại:

• được dịch chuyển tức thời bằng phép thuật đến một phòng do bạn chọn; hoặc
• đi qua một lối đi ngẫu nhiên nối với phòng hiện tại để đến phòng ở đầu kia.

Khi quyết định đi qua một lối đi, bạn không thể chọn lối nào vì chúng trông giống hệt nhau. Một lối đi được chọn cho bạn với xác suất đều.

Bạn bắt đầu cuộc khảo sát trong một phòng tùy ý. Hãy dùng nhiều nhất \(K\) thao tác để ước lượng số lối đi nối các phòng trong hang.

Nếu \(E\) là ước lượng và \(P\) là số lối đi thực tế, lời giải được coi là đúng cho một bộ test khi và chỉ khi

Để vượt qua một Test Set, lời giải phải đúng ở ít nhất \(90\%\) số bộ test trong Test Set đó.

Dữ liệu vào

Đây là bài tương tác. Hãy bảo đảm bạn đã đọc phần Interactive Problems trong FAQ của Google Code Jam.

Ban đầu, chương trình phải đọc một dòng chứa số nguyên \(T\), là số bộ test. Sau đó phải xử lý lần lượt \(T\) bộ test theo giao thức bên dưới.

Dữ liệu ra

Chương trình gửi các lệnh dịch chuyển, đi bộ và ước lượng tới bộ chấm theo giao thức tương tác bên dưới. Phải flush đầu ra sau mỗi lệnh.

Giao thức tương tác

Với mỗi bộ test, trước tiên chương trình đọc một dòng chứa hai số nguyên \(N,K\): số phòng trong hang và số thao tác phòng tối đa được phép thực hiện. Các phòng được đánh số từ \(1\) đến \(N\). Hang được xác định từ đầu bộ test và không thay đổi trong khi bạn khám phá. Sau đó, chương trình xử lý nhiều nhất \(K+1\) lượt trao đổi.

Lượt trao đổi thứ \(i\) bắt đầu bằng việc đọc một dòng chứa hai số nguyên \(R_i,P_i\), lần lượt là số hiệu phòng hiện tại và số lối đi nối với phòng đó. Sau đó, chương trình phải in đúng một trong các dòng sau:

• Một chữ hoa W: yêu cầu đi qua một lối đi ngẫu nhiên.
• Một chữ hoa T và một số nguyên \(S\): yêu cầu dịch chuyển tức thời đến phòng \(S\).
• Một chữ hoa E và một số nguyên \(E\): kết thúc khảo sát và ước lượng hang có \(E\) lối đi.

Sau một thao tác ước lượng, bộ chấm lập tức bắt đầu bộ test kế tiếp nếu còn, bất kể ước lượng có đúng hay không. Nếu không còn bộ test, bộ chấm chờ chương trình kết thúc và không in thêm gì.

Nếu vào bất kỳ lúc nào bộ chấm nhận từ chương trình một dòng sai định dạng, hoặc nếu lượt trao đổi thứ \(K+1\) của một bộ test không phải thao tác ước lượng, bộ chấm in một số duy nhất -1 rồi không in thêm gì. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận lỗi Time Limit Exceeded. Chương trình có trách nhiệm thoát kịp thời để nhận Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, chương trình nhận phán quyết tương ứng.

Ràng buộc

• Mỗi phòng nối với ít nhất một lối đi.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le T\le100\), \(2\le N\le10^5\), và \(K=8000\).
• Theo quy tắc chấm chính thức, lời giải phải đúng ở ít nhất \(90\%\) số bộ test trong Test Set này để vượt qua Test Set.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng của Google. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ để biết thêm chi tiết.

Hướng dẫn cho công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Bạn được khuyến khích thêm các bộ test của riêng mình. Lưu ý rằng dù công cụ nhằm mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hành xử khác. Nếu mã vượt qua công cụ nhưng không vượt qua bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với Google.

Tải công cụ kiểm thử

Ví dụ

Judge  Solution
1
5 3
4 1
       T 5
5 2
       W
4 1
       T 1
1 3
       E 5

Nguồn

Google Code Jam 2022, Vòng loại, bài Twisty Little Passages.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.