Loadding...
Sắp xếp container
Chú ý: Bạn cần download module mô phỏng để giải bài toán này.
Công ty vận tải hàng hóa tạm chứa container đợi giải phóng.
Cứ mỗi giờ, container được đưa đến kho chứa hàng. Chúng được lưu ở kho trong một số dương
giờ. Khi một container được đưa đến kho, trong vận đơn có ghi ngày dự kiến container sẽ được
giải phóng. Container đầu tiên được đưa đến kho vào thời gian 1. Thời gian tối đa một container
được lưu kho không quá 5 giờ.
Trong bài toán này, thời gian (tính bằng giờ) là một số dương tăng dần nhưng không lớn hơn 150.
Một chiếc cần cẩu hoạt động trong kho hàng có nhiệm vụ đưa container ra vào kho hàng, có lúc
nó còn sắp xếp lại vị trí các container trong kho.
Bài toán:
Hãy viết chương trình thực hiện việc tiếp nhận, lưu kho và giải phóng container một cách hợp lý.
Một chương trình hợp lý là số lần cần cẩu phải di chuyển container là ít nhất. Kho hàng là một
hình hộp chữ nhật. Chiều dài (X), chiều rộng (Y) và chiều cao (Z) của kho hàng được cho trước.
Mỗi container là một khối lập phương kích thước 1 x 1 x 1. Container có thể được để chồng lên
những chiếc container khác hoặc để trên sàn kho. Cần cẩu chỉ có thể di chuyển chiếc container
trên cùng.
Chuyển một chiếc container từ vị trí này đến vị trí khác tức là cần cẩu đã di chuyển một lần. Cần
cẩu di chuyển liên tục. Khi kho hàng hết chỗ, chương trình phải từ chối nhận tiếp container.
Chương trình của bạn có thể hoạt động không hợp lý hoặc không hoạt động được nữa khi kho
hàng gần đầy. Chương trình có thể từ chối nhận tiếp container mới vào bất cứ lúc nào.
Input:
Chương trình của bạn phải tương tác với một module mô phỏng để lấy dữ liệu và chương trình
của bạn phải khai báo hoạt động và thông báo qua module đó. Kho hàng chưa có container nào
khi chương trình bắt đầu chạy.
Khi chương trình chạy chương trình mô phỏng sẽ cung cấp số lần di chuyển hợp lý nhất với mỗi
Page 1Khi chương trình chạy, chương trình mô phỏng sẽ cung cấp số lần di chuyển hợp lý nhất với mỗi
bộ dữ liệu thử nghiệm. Mỗi container được xác định bằng một số nguyên dương duy nhất.
Chương trình của bạn có thể gọi các hàm sau bất cứ lúc nào:
int GetX();
function CetX: integer;
DECLARE FUNCTION GetX CDECL ()
Trả lại chiều dài cho kho hàng (số nguyên).
int GetY();
function GetY: integer;
DECLARE FUNCTION GetY CDECL ()
Trả lại chiều rộng cho kho hàng (số nguyên).
int GetZ();
function GetZ: integer;
DECLARE FUNCTION GetZ CDECL ()
Trả lại chiều cao cho kho hàng (số nguyên).
X,Y,Z không lớn hơn 32.
Các hàm trên cung cấp thông tin về thứ tự các hoạt động (container đến hoặc giải phóng).
int GetNevtContainer();
function GerNexrContainer: integer;
DECLARE FUNCTION GetNextContainer CDECL ()
Trả lại số hiệu của các container (số nguyên dương) tiếp theo container được lưu kho. Nếu không còn container nào được lưu kho, chương trình sẽ trả về số 0 để nhắc chương trình của bạn nên
thoát ra.
int GetNewtAction();
function CetNextAction: integer;
DECLARE FUNCTION GetNextAction CDECL ()
Trả lại một số nguyên chỉ hành động: số 1 để lưu kho một container mới, số 2 để giải phóng một container.
int GetNextStorageTime();
function GetNextStorageTime: integer;
DECLARE FUNCTIOIN GetNextStorageTime CDECL ()
Trả lại thời gian tính bằng giờ từ khi chương trình bắt đầu chạy đến khi một container được giải
phóng. Giá trị này được trả lại nhằm mục đích sắp kế hoạch cho chương trình của bạn; lệnh giải
phóng hàng phải bắt đầu sau không quá 5 giờ. Hàm này chỉ trả lại giá trị có nghĩa khi hàm
GetNextAction trả về 1.
Thứ tự gọi ba hàm trên không quan trọng.
Output:
Khi chương trình của bạn tìm thấy thông tin nó cần về container tiếp theo, hãy dùng các hàm dưới
đây để vận hành kho hàng:
2 Sắp xếp container
int MoveContainer(int xl, int yl, int x2, int y2);
function MoveContainer(xl, yl, xZ, y2: integer): integer;
DECLARE FUNCTION MoveContainer CDECL (BYVAL xl AS INTEGER, BYVAL yl
AS INTEGER, BYVAL x2 AS INTEGER, BYVAL y2 AS INTEGER)
Di chuyển container trên đỉnh chồng container tại vị trí x1, y1 sang đỉnh chồng container tại vị trí
x2, y2. Trả lại giá trị 1 nếu hoạt động thực hiện được, trả lại giá trị 0 nếu hoạt động không thực
hiện được.
void RefuseContainer();
procedure RefuseContainer;
DECLARE SUB RefuseContainer CDECL ()
Từ chối tiếp nhận container tiếp theo.
void StoreArrivingContainer(int x, int y);
procedure StoreArrivingContainer(x, y: integer);
DECLARE SUB StoreArrivingContainer CDECL (BYVAL x AS INTEGER, BYVAL y
AS INTEGER)
Lưu container tiếp theo trên đỉnh chồng container tại vị trí x, y.
void RemoveContainer(int x, int y);
procedure RemoveContainer(x, y: integer);
DECLARE SUB RemoveContainer CDECL (BYVAL x AS INTEGER, BYVAL y AS
INTEGER)
Giải phóng container trên đỉnh chồng container tại vị trí x, y ra khỏi kho hàng.
Nếu chương trình của bạn không thực hiện được yêu cầu, thì nó sẽ thoát ra.
Những di chuyển không thực hiện được sẽ không được module mô phỏng download về chấp
nhận và do đó di chuyển cũng không được thực hiện và bạn không được điểm.
Chương trình của bạn không cần báo cáo tệp output. Module mô phỏng mà chương trình của bạn
tương tác khi hoạt động sẽ tự tạo ra tệp chứa các bản ghi về thông tin các hoạt động. Tệp này sẽ
được dùng để cho điểm.
Sắp xếp:
Chương trình của bạn đọc lệnh với container tiếp theo. Sau đó, di chuyển các container đến chỗ
lưu kho hay giải phóng.
Module mô phỏng:
Module mô phỏng này mang tên StackLib chứa các thông tin liên quan đến việc lập trình của bạn.
Nếu bạn lập trình bằng ngôn ngữ C và C++ thì module này sẽ tự động kết nối với chương trình
của bạn khi bạn thêm file đầu trang. Nếu bạn dùng ngôn ngữ QuickBasic bạn phải gõ thêm lệnh
QB /L STACKLIB
Đánh giá:
Chương trình sẽ được kiểm tra bằng nhiều bộ dữ liệu và với mỗi bộ dữ liệu chương trình sẽ được
3 Sắp xếp container
cho điểm theo giải pháptối ưu nhất dựa trên các tiêu thức:
Tổng số lần di chuyển của cần cẩu.
Mỗi lần từ chối một container chương trình sẽ bị tính thêm 5 di chuyển.
Mỗi container không được lưu kho hay giải phóng thì chương trình của bạn sẽ bị tính thêm
5 lần di chuyển (chương trình thoát ra trước khi quá trình hoạt động hoàn thành).
Tổng số điểm của chương trình bạn viết sẽ được tính theo tỷ lệ so với chương trình tối ưu
nhất được biết đến.
Nếu chương trình của bạn thực hiện số lần di chuyển gấp đôi số lần cần thiết, nó sẽ được
cho 0 điểm.
Số điểm tối thiểu là 0% và tối đa 100%
Sưu tầm
