HƯỚNG DẪN CHI TIẾT

NỘI DUNG THI KHỐI TRUNG HỌC PHỔ THÔNG (BẢNG C)

HỘI THI TIN HỌC TRẺ TOÀN QUỐC LẦN THỨ XXIV – 2018

1 Chủ đề

Trò chơi “ĐẨY HÌNH”

2 Thông tin chung

- Sử dụng chương trình máy tính để giải quyết một bài toán cho trước có liên quan đến thực tế.

- Thí sinh Trung học phổ thông (bảng C) về dự Hội thi toàn quốc được tổ chức theo đội (mỗi đội có 02 người). Mỗi đội được phép mang theo 01 máy tính hoặc yêu cầu Ban tổ chức chuẩn bị 01 máy tính để làm bài trong thời gian thi là 150 phút.

- Tại cuộc thi, Ban giám khảo sẽ công bố đề thi chi tiết bài toán cần giải quyết và cung cấp các dữ liệu đầu vào, các đội được phép sử dụng toàn bộ tài nguyên của máy tính để đưa ra kết quả ra tương ứng với các dữ liệu đầu vào.

- Hình thức chấm điểm: Với mỗi bộ dữ liệu, Ban giám khảo sẽ đánh giá kết quả ra tương ứng của các đội và cho điểm.

Trong quá trình chuẩn bị làm bài thi từ nhà, các thí sinh phải thường xuyên cập nhật thông tin liên quan đến bài thi thông qua địa chỉ trang web: tainangviet.vn, hoặc khi cần thiết có thể trao đổi với Ban tổ chức qua địa chỉ email: vinhnguyen73@gmail.com, hoặc điện thoại: 024.3.5772353 (đồng chí Nguyễn Sỹ Vinh).

3 Sơ đồ mô tả quá trình chuẩn bị

4 Nội dung thi

4.1 Tổng quan

Trò chơi “Đẩy hình” là trò chơi trên khay hình chữ nhật kích thước m×n ô vuông. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i, j) và khi đó, i được gọi là toạ độ dòng còn j được gọi là toạ độ cột của ô này.

Trên mỗi ô của khay có thể có đặt một khối gỗ sơn màu kích thước 1×1×1, đáy của khối gỗ nằm trọn một ô. Trên khay có ít nhất một ô không đặt khối gỗ. Tại mỗi bước, người chơi có thể đẩy khối gỗ sang một trong các ô chung cạnh không có khối gỗ. Nhiệm vụ của người chơi là tìm cách đẩy các khối gỗ để đưa về một trạng thái cho trước.

	1	2	3
1
2
3

Hình 1. Ví dụ về khay hình chữ nhật kích thước 3×3 và 6 khối gỗ màu xanh, 2 khối gỗ màu vàng trên khay, ô (3,3) là ô không chứa khối gỗ.

4.2 Cách thức thi đấu

Các đội được cung cấp các bộ dữ liệu, mỗi bộ sẽ chứa thông tin về kích thước khay, trạng thái các khối gỗ ban đầu (gồm các thông tin về vị trí các khối gỗ, màu của khối gỗ), trạng thái các khối gỗ ở trạng thái đích. Các đội được quyền sử dụng toàn bộ tài nguyên máy tính của đội mình để đưa ra phương đẩy.

Ban giám khảo kiểm tra tính đúng đắn của phương án xếp cho từng bộ dữ liệu của mỗi đội và cho điểm.

BAN TỔ CHỨC HỘI THI