Leonardo phát minh ra máy đo đường đầu tiên: một chiếc xe đo khoảng cách bằng cách thả các viên sỏi khi bánh xe quay. Đếm số sỏi cho biết số vòng quay của bánh xe, từ đó tính được quãng đường đã đi. Với vai trò chuyên gia máy tính, chúng ta bổ sung phần mềm điều khiển để mở rộng chức năng của máy đo. Nhiệm vụ của bạn là lập trình máy đo theo các quy tắc dưới đây.

Lưới hoạt động

Máy đo di chuyển trên một lưới vuông gồm \(256 \times 256\) ô đơn vị. Mỗi ô chứa nhiều nhất \(15\) viên sỏi và được xác định bởi cặp tọa độ (hàng, cột), mỗi tọa độ thuộc khoảng \(0,\ldots,255\). Các ô kề ô \((i,j)\), nếu tồn tại, là \((i-1,j)\), \((i+1,j)\), \((i,j-1)\) và \((i,j+1)\). Ô nằm trên hàng đầu, hàng cuối, cột đầu hoặc cột cuối được gọi là ô biên. Máy đo luôn bắt đầu ở ô \((0,0)\), góc tây bắc, và nhìn về hướng bắc.

Ngôn ngữ của máy đo

Các lệnh cơ bản:

• left: quay \(90\) độ sang trái, ngược chiều kim đồng hồ, và giữ nguyên ô hiện tại. Chẳng hạn, đang nhìn hướng nam thì sau lệnh này sẽ nhìn hướng đông.
• right: quay \(90\) độ sang phải, theo chiều kim đồng hồ, và giữ nguyên ô hiện tại. Chẳng hạn, đang nhìn hướng tây thì sau lệnh này sẽ nhìn hướng bắc.
• move: tiến một ô theo hướng đang nhìn. Nếu không có ô kề theo hướng đó vì đã đến biên, lệnh không có tác dụng.
• get: lấy đi một viên sỏi khỏi ô hiện tại. Nếu ô không có sỏi, lệnh không có tác dụng.
• put: thêm một viên sỏi vào ô hiện tại. Nếu ô đã chứa \(15\) viên sỏi, lệnh không có tác dụng. Máy đo không bao giờ hết sỏi.
• halt: kết thúc thực hiện chương trình.

Máy đo thực hiện các lệnh theo thứ tự trong chương trình. Mỗi dòng chứa nhiều nhất một lệnh; dòng trống được bỏ qua. Ký tự # bắt đầu chú thích: mọi nội dung sau ký tự này đến hết dòng đều bị bỏ qua. Khi đến cuối chương trình, việc thực hiện cũng kết thúc.

Để thay đổi luồng thực hiện theo trạng thái hiện tại, bạn có thể dùng nhãn. Nhãn là xâu phân biệt chữ hoa và chữ thường, dài không quá \(128\) ký tự, chỉ gồm a–z, A–Z, 0–9. Với L là một nhãn hợp lệ:

• L:: khai báo vị trí của nhãn L trong chương trình. Các nhãn được khai báo phải đôi một khác nhau. Khai báo nhãn không tác động đến máy đo.
• jump L: nhảy vô điều kiện đến dòng có nhãn L rồi tiếp tục thực hiện.
• border L: nếu máy đo ở biên và nhìn ra ngoài lưới, nghĩa là lệnh move sẽ không có tác dụng, thì nhảy đến dòng có nhãn L. Nếu không, chương trình tiếp tục bình thường và lệnh này không có tác dụng.
• pebble L: nếu ô hiện tại có ít nhất một viên sỏi thì nhảy đến dòng có nhãn L. Nếu không, chương trình tiếp tục bình thường và lệnh này không có tác dụng.

Yêu cầu

Bạn phải nộp chương trình viết bằng chính ngôn ngữ máy đo vừa mô tả, để máy đo thực hiện hành vi được yêu cầu trong từng phân nhóm.

Ràng buộc

• Kích cỡ chương trình là số lệnh trong chương trình. Khai báo nhãn, chú thích và dòng trống không được tính.
• Độ dài thực thi là số bước đã thực hiện. Mỗi lần thực hiện một lệnh đều tính là một bước, bất kể lệnh có tác dụng hay không. Khai báo nhãn, chú thích và dòng trống không tính là bước.

Ví dụ

move # không tác dụng
right
# bây giờ máy đo đang nhìn hướng đông
move
move

right
leonardo:
pebble davinci # tìm thấy sỏi
border davinci # cuối hàng
move
jump leonardo
davinci:
halt

Phân nhóm

Phân nhóm 1 (9 điểm)

Ban đầu, ô \((0,0)\) chứa \(x\) viên sỏi, ô \((0,1)\) chứa \(y\) viên sỏi và mọi ô khác đều trống, với \(0 \le x,y \le 15\). Chương trình phải kết thúc với máy đo ở \((0,0)\) nếu \(x \le y\), và ở \((0,1)\) nếu \(x>y\). Không yêu cầu hướng nhìn cuối cùng, số lượng hay vị trí của sỏi sau khi kết thúc. Kích cỡ chương trình không quá \(100\); độ dài thực thi không quá \(1\,000\).

Phân nhóm 2 (12 điểm)

Ban đầu, ô \((0,0)\) chứa \(x\) viên sỏi, ô \((0,1)\) chứa \(y\) viên sỏi và mọi ô khác đều trống, với \(0 \le x,y \le 15\). Chương trình phải kết thúc với máy đo ở \((0,0)\) nếu \(x \le y\), và ở \((0,1)\) nếu \(x>y\), không yêu cầu hướng nhìn cuối cùng. Khi kết thúc, ô \((0,0)\) phải chứa đúng \(x\) viên sỏi và ô \((0,1)\) phải chứa đúng \(y\) viên sỏi; không yêu cầu trạng thái sỏi ở các ô khác. Kích cỡ chương trình không quá \(200\); độ dài thực thi không quá \(2\,000\).

Phân nhóm 3 (19 điểm)

Có đúng hai viên sỏi trên hàng \(0\): một viên ở \((0,x)\), một viên ở \((0,y)\), với \(x \ne y\), \(0 \le x,y \le 255\) và \(x+y\) chẵn. Chương trình phải kết thúc với máy đo ở \((0,(x+y)/2)\), chính giữa hai ô chứa sỏi. Trạng thái cuối cùng của lưới không quan trọng. Kích cỡ chương trình không quá \(100\); độ dài thực thi không quá \(200\,000\).

Phân nhóm 4 (tối đa 32 điểm)

Ban đầu có nhiều nhất \(15\) viên sỏi trên lưới và không có hai viên ở cùng một ô. Hãy gom tất cả sỏi về góc tây bắc: nếu ban đầu có \(x\) viên sỏi thì khi kết thúc, ô \((0,0)\) phải chứa đúng \(x\) viên và mọi ô khác đều trống. Kích cỡ chương trình không quá \(200\).

Gọi \(L\) là độ dài thực thi lớn nhất trên các bộ dữ liệu kiểm tra của phân nhóm. Điểm được tính như sau:

Phân nhóm 5 (tối đa 28 điểm)

Mỗi ô ban đầu có số sỏi tùy ý từ \(0\) đến \(15\). Hãy tìm một ô có số sỏi nhỏ nhất: chương trình phải kết thúc với máy đo ở ô \((i,j)\) sao cho mọi ô khác đều chứa ít nhất số sỏi của ô \((i,j)\). Sau khi chạy, số sỏi trong từng ô phải giống như trước khi chạy. Độ dài thực thi không quá \(44\,400\,000\).

Gọi \(P\) là kích cỡ chương trình nộp. Điểm được tính như sau:

Chi tiết cài đặt và nộp bài

Nộp một tệp ZIP chứa đúng năm tệp sau ngay tại thư mục gốc của tệp nén:

• subtask_1.odo
• subtask_2.odo
• subtask_3.odo
• subtask_4.odo
• subtask_5.odo

Tệp subtask_X.odo là chương trình dành cho phân nhóm \(X\), viết theo cú pháp ngôn ngữ máy đo đã mô tả, và được chạy trên tất cả bộ dữ liệu của phân nhóm đó. Mỗi tệp .odo có dung lượng tối đa 5 MiB, đồng thời tệp ZIP hoàn chỉnh có dung lượng tối đa 20 MiB. Phải nộp đủ cả năm tệp trong mỗi lần nộp; hệ thống không lấy lại tệp từ lần nộp trước. Nếu một chương trình sai cú pháp hoặc vượt giới hạn tài nguyên, phân nhóm tương ứng nhận \(0\) điểm. Điểm bài nộp là tổng điểm của năm phân nhóm.

Dữ liệu vào

Bộ mô phỏng được cung cấp để thử chương trình máy đo với lưới đầu vào. Chương trình dùng cùng định dạng như tệp nộp. Trong tệp mô tả lưới, mỗi dòng chứa ba số R C P, nghĩa là ô ở hàng \(R\), cột \(C\) chứa \(P\) viên sỏi. Mọi ô không được nêu trong tệp đều không có sỏi.

0 10 3
4 5 12

Bộ mô phỏng

Gọi simulator.py trong thư mục bài với tên tệp chương trình làm đối số. Bộ mô phỏng nhận các tùy chọn dòng lệnh sau:

• -h: hiển thị mô tả ngắn về các tùy chọn.
• -g GRID_FILE: đọc mô tả lưới từ tệp GRID_FILE; mặc định là lưới rỗng.
• -s GRID_SIDE: đặt kích thước lưới thành GRID_SIDE x GRID_SIDE; mặc định là \(256\), đúng như đề bài. Lưới nhỏ hơn có thể hữu ích khi tìm lỗi.
• -m STEPS: giới hạn mô phỏng ở nhiều nhất STEPS bước thực thi.
• -c: dùng chế độ biên dịch. Bộ mô phỏng cho đầu ra giống hệt, nhưng thay vì mô phỏng bằng Python, nó sinh và biên dịch một chương trình C nhỏ. Chế độ này tốn thêm thời gian khởi động nhưng sau đó chạy nhanh hơn đáng kể; nên dùng khi chương trình dự kiến thực hiện hơn khoảng \(10\,000\,000\) bước.