IOI 2012 - Ngày 1

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.

Một phiên bản rất sớm và khá tinh vi của chiếc dù ngày nay được mô tả trong cuốn Codex Atlanticus của Leonardo, khoảng năm \(1485\). Dù của ông gồm vải lanh kín được căng bằng một khung gỗ hình kim tự tháp. Hơn \(500\) năm sau, vận động viên nhảy dù Adrian Nicholas thử nghiệm thiết kế này, dùng một kết cấu nhẹ hiện đại để gắn dù với cơ thể.

Chúng ta muốn dùng các vòng móc nối với nhau, đồng thời làm móc cho tấm vải lanh. Mỗi vòng được làm bằng vật liệu bền và dễ uốn, có thể mở ra rồi đóng lại nên dễ dàng móc nối với các vòng khác. Một cấu hình đặc biệt là chuỗi: một dãy vòng mà mỗi vòng chỉ nối với các vòng láng giềng của nó trong dãy, nhiều nhất là hai vòng. Dãy phải có đầu và cuối, mỗi vòng ở đầu hoặc cuối nối với nhiều nhất một vòng khác. Một vòng đơn lẻ cũng là một chuỗi.

Một vòng có thể nối với ba hoặc nhiều vòng khác, nên còn có những cấu hình khác. Một vòng được gọi là then chốt nếu sau khi mở và loại bỏ nó, tất cả các vòng còn lại tạo thành một tập các chuỗi, hoặc không còn vòng nào. Nói cách khác, sau khi loại bỏ vòng đó chỉ được còn lại các chuỗi.

Yêu cầu và giao diện

Hãy đếm số vòng then chốt trong cấu hình được truyền cho chương trình. Ban đầu các vòng rời nhau; sau đó chúng được móc nối dần. Tại bất kỳ thời điểm nào, chương trình có thể được yêu cầu trả về số vòng then chốt trong cấu hình hiện tại. Bạn phải cài đặt ba chương trình con:

• Init(N): được gọi đúng một lần lúc bắt đầu, cho biết cấu hình ban đầu có \(N\) vòng rời nhau, đánh số từ \(0\) đến \(N-1\).
• Link(A, B): móc nối hai vòng \(A\) và \(B\). Bảo đảm \(A \ne B\) và hai vòng chưa được nối trực tiếp với nhau. Ngoài ra không có điều kiện bổ sung nào, kể cả điều kiện xuất phát từ các ràng buộc vật lý. Link(A, B) và Link(B, A) tương đương nhau.
• CountCritical(): trả về số vòng then chốt trong cấu hình hiện tại.

Chi tiết cài đặt

Nộp đúng một tệp rings.c, rings.cpp hoặc rings.pas, cài đặt các chương trình con với chữ ký sau.

C/C++

void Init(int N);
void Link(int A, int B);
int CountCritical();

Pascal

procedure Init(N : LongInt);
procedure Link(A, B : LongInt);
function CountCritical() : LongInt;

Các chương trình con phải hoạt động như đã mô tả. Bạn có thể cài đặt thêm các chương trình con dùng nội bộ. Bài nộp không được giao tiếp dưới bất kỳ hình thức nào với đầu vào/đầu ra chuẩn hoặc với bất kỳ tệp nào khác.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): N L.
• Mỗi dòng từ \(2\) đến \(L+1\): số -1 để gọi CountCritical(), hoặc hai số A B làm tham số cho Link(A, B).

Dữ liệu ra

Trình chấm mẫu in tất cả các kết quả do CountCritical() trả về.

Ràng buộc

Các vòng được đánh số từ \(0\) đến \(N-1\); mỗi lần gọi Link dùng hai số vòng khác nhau và chưa nối trực tiếp. Giới hạn số vòng và số lần gọi trong từng phân nhóm được cho đầy đủ dưới đây.

Phân nhóm

Ví dụ

7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1

7
7
7
7
4
3
2

Có người nói Leonardo rất ngưỡng mộ Johannes Gutenberg, người thợ rèn Đức đã phát minh ra kỹ thuật in bằng chữ rời, và bày tỏ lòng kính trọng bằng cách thiết kế máy soạn thảo tôm đồng — il gambero scrivano. Thiết bị đánh máy đơn giản này phần nào giống một máy đánh chữ hiện đại và chỉ nhận hai loại lệnh: gõ ký tự tiếp theo và hoàn tác các lệnh gần nhất. Điểm đáng chú ý là khả năng hoàn tác rất mạnh: bản thân thao tác hoàn tác cũng là một lệnh và cũng có thể bị hoàn tác.

Yêu cầu và giao diện

Hãy cài đặt phiên bản phần mềm của máy soạn thảo. Ban đầu văn bản rỗng. Máy nhận một dãy lệnh từ người dùng và các truy vấn về vị trí cụ thể trong văn bản hiện tại:

• Init(): được gọi một lần lúc bắt đầu, không có tham số; có thể dùng để khởi tạo cấu trúc dữ liệu. Lời gọi này không bao giờ phải hoàn tác.
• TypeLetter(L): thêm một chữ cái thường \(L\) thuộc a–z vào cuối văn bản.
• UndoCommands(U): hoàn tác \(U\) lệnh gần nhất, với \(U\) là số nguyên dương.
• GetLetter(P): trả về ký tự tại vị trí \(P\) trong văn bản hiện tại, với \(P\) là số nguyên không âm. Ký tự đầu tiên có chỉ số \(0\). Đây là truy vấn, không phải lệnh, nên bị bỏ qua khi đếm các lệnh cần hoàn tác.

Sau lời gọi Init() ban đầu, mỗi chương trình con khác có thể được gọi không lần nào hoặc nhiều lần, theo thứ tự tùy ý. Bảo đảm \(U\) không vượt quá số lệnh đã nhận trước đó, và \(P\) nhỏ hơn độ dài văn bản hiện tại, tức số ký tự trong văn bản.

UndoCommands(U) hoàn tác \(U\) lệnh trước đó theo thứ tự ngược lại. Nếu lệnh bị hoàn tác là TypeLetter(L), ký tự \(L\) được bỏ khỏi cuối văn bản hiện tại. Nếu lệnh bị hoàn tác là UndoCommands(X), thì \(X\) lệnh trước đó được thực hiện lại theo đúng thứ tự ban đầu.

Chi tiết cài đặt

Nộp đúng một tệp scrivener.c, scrivener.cpp hoặc scrivener.pas, cài đặt các chương trình con với chữ ký sau.

C/C++

void Init();
void TypeLetter(char L);
void UndoCommands(int U);
char GetLetter(int P);

Pascal

procedure Init;
procedure TypeLetter(L : Char);
procedure UndoCommands(U : LongInt);
function GetLetter(P : LongInt) : Char;

Các chương trình con phải hoạt động như đã mô tả. Bạn có thể cài đặt thêm các chương trình con dùng nội bộ. Bài nộp không được giao tiếp dưới bất kỳ hình thức nào với đầu vào/đầu ra chuẩn hoặc với bất kỳ tệp nào khác.

Dữ liệu vào

Trình chấm mẫu đọc dòng đầu là tổng số lệnh và truy vấn trong dữ liệu. Mỗi dòng tiếp theo có một trong các dạng:

• T, một dấu cách, rồi một chữ cái thường: lệnh TypeLetter.
• U, một dấu cách, rồi một số nguyên: lệnh UndoCommands.
• P, một dấu cách, rồi một số nguyên: truy vấn GetLetter.

Dữ liệu ra

Trình chấm mẫu in các ký tự do GetLetter trả về, mỗi ký tự trên một dòng riêng.

Ràng buộc

\(U>0\) và không vượt quá số lệnh đã nhận; \(0 \le P\) và \(P\) nhỏ hơn độ dài văn bản hiện tại. Tổng số lệnh và truy vấn được giới hạn theo phân nhóm dưới đây.

Phân nhóm

Ví dụ

14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2

b
d
c
d