ĐỀ THI LẬP TRÌNH THÁNG 9

Bài 1: Sắp xếp hàng hóa trong kho

Tại mỗi cửa hàng của Viettel XNK, sau khi nhập hàng và trưng bày thì thừa rất nhiều vỏ hộp. Mỗi vỏ hộp có chiều dài, chiều rộng, chiều cao và số thứ tự xác định theo thứ tự nhập hàng. Vỏ hộp A có thể bỏ vào vỏ hộp B nếu vỏ hộp B rỗng và xoay hộp A sao cho các chiều của hộp A nhỏ hơn hộp B.

Để làm gọn kho hàng, nhân viên dọn kho đặt toàn bộ vỏ hộp thành một dãy. Bắt đầu từ vỏ hộp đầu tiên, anh ta tìm vỏ hộp rỗng gần nó nhất và có số thứ tự sau nó rồi bỏ vào đó. Nếu không có hộp nào thảo mãn thì anh ta tiếp tục với vỏ hộp tiếp theo.

Đầu vào: file input.txt

-          Dòng đầu là số hộp n nguyên dương: (1 < n < 300)

-          N dòng tiếp theo là các chiều của vỏ hộp có số thứ tự tương ứng

Đầu ra: file output.txt

-          Chỉ có một dòng duy nhất thể hiện số hộp còn lại sau khi kết thúc việc dọn kho.

Ví dụ:

input.txt

 21

 1 4 2

 6 5 2

 6 3 7

 8 8 2

 6 3 3

 4 4 9

 9 5 6

 4 1 6

 4 19 8

 13 1 8

 8 17 7

 13 18 16

 11 10 8

 11 14 4

 18 25 28

 26 2 19

 23 21 22

 15 8 15

 14 27 13

 26 14 17

 23 28 6

output.txt

6

Bài 2: Điều khiển tự động

Tổng công ty Bưu chính Viettel hiện thực hóa quyết tâm xây dựng doanh nghiệp bưu chính tầm cỡ quốc tế bằng cách đầu tư hệ thống robot để tự động lấy hàng trong kho hàng. Các robot này được điều khiển thông qua 2 loại thông tin:

1. Kho hàng được biểu diễn dưới dạng ma trận kích thước mxn (m,n <=100). Trong đó mỗi ô có kích thước bằng kích thước của robot. Ô có giá trị là 0 nếu là đường đi, 1 nếu là chướng ngại, 2 là vị trí của robot, 3 là vị trí cần tới để lấy hàng. (Giá trị 2 và 3 bản chất vẫn là đường đi và chỉ xuất hiện duy nhất 1 lần trong ma trận)

2. Robot thực hiện thao tác di chuyển dựa vào tập lệnh được nhập vào, trong đó gồm các lệnh đơn lẻ sau:

- L: quay 90 sang trái, giữ nguyên vị trí

- R: quay 90 sang phải, giữ nguyên vị trí

- U: di chuyển về phía trước 1 ô,  giữ nguyên hướng

- D: di chuyển lùi về phía sau 1 ô, giữ nguyên hướng

Viettel Post cần xây dựng một hệ thống phần mềm để ra lệnh cho robot di chuyển đến vị trí lấy hàng một cách tối ưu nhất (ít thao tác nhất). Để dễ điều khiển, mặc định ban đầu robot nhìn về hướng bắc.

Đầu vào: file input.txt

-          Dòng đầu là 2 số nguyên dương n và m cách nhau bởi 1 dấu cách: (4 <= n,m < = 100)

-          N dòng tiếp theo thể hiện thông tin kho, mỗi dòng có m số nguyên dương có giá trị 0,1, 2 hoặc 3.

Đầu ra: file output.txt

-          Độ dài chuỗi lệnh tối ưu nhất để điều khiển robot di chuyển từ vị trí 2 đến vị trí 3.

Ví dụ:

input.txt

4 5

0 0 0 1 0

0 0 1 0 3

2 0 1 0 0

0 0 0 0 0

output.txt

9

Tập lệnh ví dụ: DLUUUURUU