Sau khi cắt, hình chữ nhật bé hơn (diện tích bé hơn) sẽ được bỏ đi và hình chữ nhật còn lại sẽ được chuyển cho người chơi kia. Nếu 2 hình chữ nhật được cắt ra có diện tích bằng nhau thì bỏ qua hình nào cùng được. Người chơi nào nhận được hình chữ nhật 1 1 thì không thể cắt tiếp được, và là người thua cuộc trong trò chơi.
Nhiệm vụ của bạn là viết một chương trình để chơi và thắng trò chơi này. Chương trình phải sử dụng một thư viện đặc biệt để chơi. Thư viện cung cấp các hàm demension_x() và demension_y() để trả về kích thước của hình chữ nhật. Khởi đầu kích thước của hình chữ nhật trong khoảng từ 1 đến 100 000 000 và ít nhất có một chiều lớn hơn 1. Trong 50% test kích thước không quá 25.
Còn có thủ tục cut(huong, vitri), thủ tục này được chương trình của bạn gọi khi thực hiện một nước đi. Các tham số huong và vitri mô tả hướng và vị trí của nhát cắt tương ứng. Tham số huong có thể nhận các giá trị vertical hoặc horizontal. Nếu huong = vertical thì nhát cắt là một đường thẳng đứng và tham số vitri thể hiện hoành độ của nhát cắt (xem hình bên) và bạn phải đảm bảo rằng 1 ≤ vitri ≤ demension_x() – 1. Nếu huong = horizontal thì nhát cắt là một đường thẳng nằm ngang và tham số vitri thể hiện tung độ của nhát cắt và bạn phải đảm bảo rằng 1 ≤ vitri ≤ demension_y() – 1.
Khi chương trình của bạn bắt đầu, nó sẽ trở thành một người chơi trong trò chơi. Chương trình của bạn đi trước – nó phải cắt hình chữ nhật ban đầu. Khi chương trình của bạn gọi thủ tục cut, nước đi đó được ghi lại và chuyển lượt đi cho đối thủ của chương trình. Sau nước đi của đối thủ, lượt đi lại thuộc về chương trình của bạn. Giá trị trả về của dimension_x() và dimension_y() sẽ cập nhật theo tình trạng sau mỗi nước đi. Khi chương trình của bạn thắng, thua hoặc đi sai (ví dụ gọi thủ tục cut với tham số không hợp lệ) cuộc chơi sẽ bị dừng lại ngay. Việc kết thúc chương trình là một quá trình tự động, do đó chương trình của bạn phải cố đi được càng nhiều nước càng tốt. Bạn được biết thêm rằng với mọi test dữ liệu, luôn tồn tại một chiến lược mà chương trình của bạn sẽ thắng.
Chương trình của bạn không được phép đọc hay viết vào bất kì tệp nào, nó không được sử dụng input/output chuẩn và không được thay đổi vùng bộ nhớ không thuộc chương trình. Vi phạm bất kỳ điều lệ nào, kết quả của bạn có thể bị loại.
Thử nghiệm
Để bạn có thể thử nghiệm thư viện, bạn sẽ được cung cấp một số ví dụ của các đấu thủ trong thư viện: mã nguồn của chúng ở các file preclib.pas, creclib.c và creclib.h. Thư viện có thể download tại http://contest/. Chiến lược của chúng rất đơn giản, khi chương trình của bạn thực hiện, nó sẽ đấu với những đối thủ đơn giản này. Bạn có thể tự do chỉnh sửa chúng và thử cho chương trình của bạn đấu với những đối thủ mạnh hơn. Tuy nhiên sau này chương trình của bạn sẽ phải đấu với một đối thủ khác mạnh hơn nhiều.
Khi bạn hoàn thành chương trình với việc sử dụng giao diện TEST, nó sẽ được biên dịch với thư viện của một đối thủ không chỉnh sửa được. File input sẽ được đưa vào input chuẩn trong chương trình của bạn. File input phải có hai dòng, mỗi dòng chứa một số nguyên. Dòng đầu chứa chiều rộng và dòng thứ hai chứa chiều cao của hình chữ nhật ban đầu. Các kích thước này cũng được đối thủ trong thư viện đọc.
Nếu bạn chỉnh sửa phần thực hiện (implementation) của thư viện preclib.pas, hãy biên dịch lại nó bằng lệnh: ppc386 –O2 preclib.pas. Cú lệnh này sẽ sinh ra các file preclib.o và preclib.ppu. Các file này được dùng đến khi biên dịch chương trình của bạn, và phải đặt ở thư mục chứa chương trình của bạn. Bạn không được chỉnh sửa phần giao diện (interface) của thư viện preclib.pas.
Nếu bạn chỉnh sửa thư viện creclib.c, bạn phải nhớ đặt nó (đi cùng với creclib.h) vào thư mục chứa chương trình của bạn – chúng cần để biên dịch. Bạn không được chỉnh sửa creclib.h.
Bạn được cung cấp thêm hai chương trình đơn giản minh hoạ việc sử dụng các thư viện trên: crec.c và crec.pas. (Nhớ rằng đó không phải là lời giải chính xác). Bạn có thể biên dịch chúng bằng các lệnh:
gcc –O2 –static crec.c creclib.c –lm
g++ –O2 –static crec.c creclib.c –lm
ppc386 –O2 –XS prec.pas
Thư viện
Bạn được cung cấp một thư viện với các chức năng:
• Thư viện Free Pascal (preclib.ppu, preclib.o)
type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);
Thêm dòng lệnh sau vào file file nguồn rec.pas của bạn:
Uses preclib;
Để biên dịch chương trình của bạn, copy các file preclib.o và preclib.ppu vào thư mục chứa file nguồn của bạn và thực hiện lệnh:
ppc386 –O2 –XS rec.pas
File prec.pas cho bạn một ví dụ về cách sử dụng thư viện preclib.
• Thư viện GNU C/C++ (creclib.h, creclib.c)
typedef enum __direction {vertical, horizontal} direction;
int dimension_x();
int dimension_y();
void cut(direction dir, int position);
Thêm dòng lệnh sau vào file nguồn rec.c hoặc rec.cpp của bạn:
#include ”creclib.h”
Để biên dịch chương trình của bạn, copy file preclib.c và preclib.h vào thư mục chứa file nguồn của bạn và thực hiện lệnh:
gcc -O2 -static rec.c creclib.c -lm
hoặc:
g++ -O2 -static rec.cpp creclib.c -lm
File crec.c cho bạn một ví dụ về cách sử dụng thư viện trong C.
Một tương tác ví dụ
Dưới đây là một ví dụ về sự tương tác giữa chương trình của bạn và thư viện của giám khảo, thể hiện một quá trình chơi đơn giản. Cuộc chơi bắt đầu với hình chữ nhật 4 x 3. Tồn tại chiến lược để chương trình của bạn chiến thắng.