VNOI Marathon 2012

"Trong thần thoại Hy Lạp, có một câu chuyện gắn với một quốc gia mà cho đến nay vẫn là bí ẩn của nhân loại. Đó là vương quốc của người Minos.

Truyện kể rằng vua Minos đắc tội với thần biển Poseidon nên vị thần này đã bỏ bùa mê cho hoàng hậu Pasifage, khiến bà ta yêu phải một con bò. Sự kết hợp kỳ quái này đã sản sinh ra một trong những quái vật đáng sợ nhất truyền thuyết Hy Lạp: Minotaur – quái vật đầu bò, thân người. Để nhốt quái vật lại, vua Minos đã cho xây dựng một cung điện (mê cung) nối tiếng nhờ đến một kiến trúc sư đến từ Athens. Để tránh nạn dịch tàn phá, mỗi năm Athens phải chọn ra 7 cặp trai gái đồng trinh hiến tế cho quái vật.

Đau lòng trước nỗi khổ của dân chúng, hoàng tử của vua Athens là Theseus đã quyết tâm vào cung điện này giết chết quái vật và nhờ sợi chỉ dẫn đường của công chúa Minos mà ra được khỏi mê cung..."

Đề bài

Giờ đã là thế kỷ 30 rồi, khi đi vào mê cung chắc chắn bạn sẽ không cầm theo sợi chỉ như hoàng tử Theseus, mà sẽ mang theo những cổng dịch chuyển tức thời. Cụ thể, bạn cần đi vào một mê cung có kích thước M*N, và có thể mang theo K cặp cổng dịch chuyển tức thời. Các cổng dịch chuyển tức thời hoạt động theo cách: khi bạn đi xuyên qua một cổng thì bạn sẽ đi ra khỏi cổng cùng cặp với nó. Như vậy, để di chuyển trong thời gian nhanh nhất, bạn sẽ đặt một số cổng dịch chuyển tức thời tại một số vị trí của mê cung (và giữ lại cổng cùng cặp với nó) để quay trở lại những vị trí đó khi cảm thấy cần thiết.

Bạn xuất phát từ lối vào của mê cung, và muốn di chuyển đến lối ra của nó. Ở mỗi vị trí, bạn có thể di chuyển theo các cách sau:

• Di chuyển sang 1 trong 4 ô kề cạnh.
• Đặt một cổng dịch chuyển tức thời xuống ô hiện tại, nếu trước đó chưa có cổng dịch chuyển tức thời nào ở ô đó.
• Lấy lại một cổng dịch chuyển tức thời ở ô hiện tại, nếu trước đó bạn đã đặt một cổng dịch chuyển tức thời xuống ô đó.
• Di chuyển đến một cổng dịch chuyển tức thời.

Trong mê cung vô cùng tăm tối, vì vậy bạn không nhìn thấy các ô xung quanh có tường hay không.

Mê cung

Tất cả các mê cung chỉ gồm một thành phần liên thông duy nhất. Trong mê cung có một số ô là tường, bạn không thể đi vào các ô này.

Các ô biên trên mê cung (các ô ở hàng 1, hàng M, cột 1, cột N) đều là tường.

Trong mê cung có một lối vào và một lối ra duy nhất.

Tương tác

Bài này được chấm điểm theo kiểu interactive: Chương trình của bạn và trình chấm sẽ lần lượt gửi output cho nhau (có thể hình dung giống như 2 người đang trò chuyện: người này chỉ nói tiếp khi đã nhận được câu trả lời từ người kia).

Trước khi bắt đầu chấm bài của bạn, với mỗi test, trình chấm sẽ tạo ra thông tin của một mê cung (giống nhau với tất cả các thí sinh), và bạn sẽ được đặt vào vị trí xuất phát.

• Đầu tiên, trình chấm sẽ viết ra input của chương trình bạn 3 số nguyên dương M, N, K (10 ≤ M, N ≤ 50, 1 ≤ K ≤ 50)
• Sau khi đọc input từ trình chấm, bạn sẽ output ra cách di chuyển của mình.
  • 0: di chuyển theo hướng Bắc
  • 1: di chuyển theo hướng Đông
  • 2: di chuyển theo hướng Nam
  • 3: di chuyển theo hướng Tây
  • 4 X: Đặt cổng dịch chuyển tức thời có số thứ tự X xuống vị trí hiện tại (các cổng dịch chuyển tức thời được đánh số bằng các số nguyên liên tiếp từ 1 đến K).
  • 5 X: Lấy cổng dịch chuyển tức thời có số thứ tự X khỏi vị trí hiện tại
  • 6 X: Di chuyển đến cổng dịch chuyển tức thời có số thứ tự X
• Sau khi đọc được output của bạn, chương trình chấm sẽ trả lại kết quả, bằng việt in ra input của chương trình bạn:
  • 0 nếu nước đi của bạn không thể thực hiện được. (nếu ô bạn di chuyển đến là tường hoặc bạn đặt cổng dịch chuyển tức thời vào ô đã có cổng dịch chuyển tức thời, hoặc bạn lấy lại cổng dich chuyển tức thời chưa sử dụng/không ở ô hiện tại hoặc di chuyển đến cổng dịch chuyển tức thời chưa được sử dụng).
  • 1 nếu nước đi của bạn được thực hiện thành công
  • 999 nếu bạn đã đến ô đích. Khi nhận được input này, chương trình của bạn phải dừng lại.
• Bước 2 và 3 đến khi bạn đến ô đích, hoặc đã vượt quá số nước di chuyển cho phép.

Chú ý:

• Sau khi output ra một số nguyên, bạn cần output thêm 1 dấu cách hoặc 1 dấu xuống dòng.
• Để trình chấm nhận được output của bạn, sau mỗi lần in ra một nước di chuyển, bạn cần dùng thêm lệnh fflush(stdout) với C++ và flush(output) với pascal. Với pascal, bạn không nên dùng cách đọc từ file có tên trống để tránh lệnh flush(output) hoạt động không như mong muốn.

Example

Trạng thái mê cung
#####
#S.T#
#####

Ký hiệu: '#' thể hiện vị trí có tường, '.' thể hiện ô trống. S là lối vào mê cung, T là lối ra khỏi mê cung. Bạn được cho 1 cổng dịch chuyển tức thời

Input & Output

 Output 

 Input  

Đoạn code mẫu để các bạn tham khảo

Đoạn code dưới đây không có thuật toán cụ thể, chỉ nhằm mục đích giúp các bạn hình dung về cách thức input, output:

C++:

void solve() {

int m, n, k; cin >> m >> n >> k;

for(int turn = 0; turn < 100; turn++) {

for(int direction = 0; direction < 4; direction++) {

cout << direction << ' '; fflush(stdout);

int result; cin >> result;

if (result == 999) return ;

if (result == 1) break;

}

}

}

Pascal:

procedure solve;

var i, direction, result, m, n, k : integer;

begin

read(m, n, k);

for i := 1 to 100 do begin

for direction := 0 to 3 do begin

write(direction, ' '); flush(output);

read(result);

if (result = 999) then exit;

if (result = 1) then break;

end;

end;

end;

Thời gian làm bài

Thời gian làm bài đối với bài này là 3 ngày (72 tiếng). Trong suốt thời gian này, bài làm của bạn sẽ được chấm với 30-40% số test chính thức của bài (và có thể có thêm một vài test không nằm trong bộ test chính thức).

Cách chấm điểm

Gọi X là số nước đi mà bạn thực hiện, Y là số nước đi mà bạn thực hiện, không kể các bước di chuyển loại 4 và 5:

• Nếu bạn in ra một nước đi không theo định dạng trên (chẳng hạn in ra các chữ cái, các ký tự lạ, chỉ số cổng dịch chuyển tức thời không nằm trong khoảng 1..K, ...) bạn được 0 điểm.
• Nếu X > 8MN, bạn được 0 điểm.
• Nế X ≤ 8MN, bạn được (8MN - Y)³ điểm.