Trong bài toán tương tác này, bạn phải đi từ lối vào của một mê cung chưa biết đến lối ra mà không tốn quá nhiều thời gian.

Chiến binh nổi tiếng Malcolm, người hùng của Arcania, đi qua một khu rừng tối vào ban đêm. Anh đã đi rất lâu và bắt đầu nghĩ rằng mình bị lạc, nhưng đột nhiên gặp một bức tường đá chắn đường. Những dấu khắc trên phiến đá lộ ra dưới lớp lá rụng cho thấy rõ rằng anh đã phát hiện một mê cung do người lùn xây dựng.

Người hùng biết rất ít về khu rừng và những cây mọc ở đó. May thay, anh từng ở bên người lùn rất lâu, nên giờ đây chỉ cần nhìn các dấu khắc là có thể biết nhiều điều về một mê cung.

Các dấu khắc trên mê cung này tạo thành các ký tự “SK3”. Ký tự “S” có nghĩa là mê cung có hình vuông, tức là nền mê cung gồm $n \times n$ ô vuông, mỗi ô có kích thước $1 \times 1$ mét. Bao quanh các ô là một bức tường mỏng liên tục có hai chỗ mở. Chỗ thứ nhất là lối vào, nơi người hùng đang đứng gần đó. Nó nằm trên bức tường phía nam của ô góc tây nam của mê cung. Chỗ thứ hai là lối ra nằm trên bức tường phía bắc của ô góc đông bắc.

Hai ô bất kỳ có chung cạnh có thể được nối bằng một lối đi hoặc bị ngăn bởi một đoạn tường trong mỏng dài một mét. Từ mỗi ô có thể đi sang bất kỳ ô chung cạnh nào nếu giữa chúng không có tường. Ngoài ra, có thể tự do đi qua lối ra. Lối vào chỉ mở cho đến khi người hùng bước vào mê cung. Sau đó, nó đóng ngay lập tức và chỉ mở lại khi người hùng đến lối ra an toàn.

Các ký tự “K3” cho người đi mê cung có kinh nghiệm biết rằng mê cung có cấu trúc sau. Đầu tiên, từ tất cả các đoạn tường trong mỏng có thể có (tổng cộng có $n \times (n-1)$ đoạn theo hướng bắc–nam và cũng từng ấy đoạn theo hướng đông–tây), chọn ngẫu nhiên một phần ba, làm tròn xuống nếu không nguyên, rồi xét chúng theo một thứ tự ngẫu nhiên cố định. Sau đó, các đoạn tường được đặt vào mê cung theo thứ tự ấy. Nếu việc đặt một đoạn tường sẽ chia hình vuông chứa mê cung thành các phần không liên thông, đoạn đó bị loại bỏ, không được đặt. Vì vậy, mê cung tạo ra được bảo đảm liên thông.

Malcolm rất vui: anh biết nhiều về mê cung đến mức chắc chắn có thể đến lối ra. Mục tiêu của anh là xuất phát từ ô rừng kề lối vào và đến ô rừng kề lối ra. Anh cũng cần nhanh lên: người đi từ lối vào đến lối ra đủ nhanh sẽ thấy kho báu giấu trong rừng gần lối ra. Tất nhiên, điều này chỉ đúng nếu chưa có ai đến kho báu trước đó.

Nghĩ lại, vẫn còn những điều đáng lo. Thứ nhất, Malcolm không biết kích thước mê cung: độ dài cạnh hình vuông $n$ có thể là bất kỳ số nguyên mét nào từ $10$ đến $200$. Thứ hai, mê cung cũng tối như khu rừng xung quanh, nên Malcolm phải di chuyển gần như trong mù lòa. Đầu mỗi bước, người hùng chọn một trong bốn hướng chính: bắc, đông, nam hoặc tây. Sau đó, anh thử đi một mét theo hướng ấy. Nếu gặp vật cản, anh đứng nguyên chỗ cũ. Nếu không, anh chuyển sang ô kề theo hướng đã chọn. Thời gian cho mỗi bước không phụ thuộc kết quả của bước đó, nên điều quan trọng là tổng số bước.

Hãy giúp người hùng di chuyển sao cho đến ô yêu cầu đủ nhanh. Lời giải được xem là đúng nếu người hùng đi nhiều nhất $5 \cdot n + 300$ bước và đến ô nằm bên ngoài lối ra của mê cung.

Giao tiếp

Trong bài toán này, chương trình của ban giám khảo phản hồi các lệnh mà lời giải gửi ra đầu ra chuẩn. Mỗi lệnh xác định bước tiếp theo của Malcolm. Mỗi lệnh nằm trên một dòng riêng và gồm một chữ cái tiếng Anh viết hoa: “N” để đi về phía bắc, “E” về phía đông, “S” về phía nam và “W” về phía tây.

Với mỗi lệnh được gửi, chương trình ban giám khảo lập tức trả về một dòng qua đầu vào chuẩn của lời giải. Dòng đó chứa một từ viết bằng chữ cái tiếng Anh thường: “no” nếu vật cản chặn đường đi, “ok” nếu bước đi thành công nhưng người hùng chưa đến ô đích, và “end” nếu bước đi thành công và người hùng đã ở ô đích. Sau khi nhận phản hồi “end”, lời giải phải kết thúc mà không xuất thêm bất kỳ nội dung nào.

Để tránh đầu ra bị lưu trong bộ đệm, hãy đẩy hết bộ đệm đầu ra sau mỗi lệnh. Ví dụ, có thể dùng fflush (stdout) trong C hoặc C++, System.out.flush () trong Java, flush (output) trong Pascal hoặc sys.stdout.flush () trong Python.

Trong mỗi kiểm thử, mê cung được cố định từ trước sau khi được sinh ngẫu nhiên.

Nếu lời giải đã thực hiện ít nhất $100\,000$ bước nhưng chưa vượt giới hạn thời gian và chưa đến ô đích, việc chấm sẽ kết thúc với kết quả “Sai đáp án”.

Ví dụ

Ghi chú

Hình trên thể hiện mê cung được sinh trong kiểm thử đầu tiên. Malcolm xuất phát ở ô đánh dấu bằng hình tròn và phải đến ô đánh dấu bằng dấu chéo. Chẳng hạn, có thể vượt qua mê cung bằng dãy lệnh sau (bên dưới các lệnh là kết quả thực hiện của chúng):

N W N E N W N E N E E E S E E N N N N N E N E S E E N
ok no ok ok ok ok ok ok ok ok ok no ok ok ok ok ok ok ok ok ok ok ok no ok ok end

Trong hình, lời giải này được thể hiện bằng một đường màu xám đậm nét.