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 – 2012

THƯỜNG TRỰC BAN TỔ CHỨC HỘI THI TIN HỌC TRẺ TOÀN QUỐC LẦN THỨ XVIII-2012	Hà Nội, ngày 20 tháng 5 năm 2012
* * *

 

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 – 2012

1         Chủ đề

Trò chơi đối kháng “Bi đổi màu”

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ế.

-         Tại cuộc thi, đề thi sẽ mô tả chi tiết bài toán cần giải quyết, các đội sẽ có thời gian sử dụng máy tính để hoàn thành chương trình giải quyết bài toán dựa trên chương trình đã được chuẩn bị trước ở nhà.

-         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 thí sinh sử dụng 1 máy tính, sử dụng ngôn ngữ lập trình Pascal (trên FreePascal) hoặc C/C++ (trên DevC++) làm bài thi trên máy trong thời gian thi là 150 phút.

-         Hình thức chấm điểm đối kháng sẽ được sử dụng: Mỗi lượt đấu, chương trình của hai đội sẽ thi đấu với nhau. Các đội sẽ được bắt thăm để đấu với nhau theo hình thức loại trực tiếp.

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: www.dstc.org.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: 04.3.5772351 (đồ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 “Bi đổi mầu” là trò chơi đối kháng gồm hai người chơi trên lưới hình chữ nhật  ô vuông. Các dòng được đánh số từ 1 đến  từ trên xuống dưới, các cột được đánh số từ 1 đến  từ trái qua phải. Ô nằm ở vị trí dòng  và cột  của lưới được gọi là ô  và khi đó,  được gọi là toạ độ dòng còn  được gọi là toạ độ cột của ô này. Ban đầu, trên lưới có  viên bi màu xanh và  viên bi màu đỏ, mỗi ô của lưới có không quá một viên bi.

Hình 1. Ví dụ về lưới chữ nhật và trạng thái bi ban đầu

Sau đó cả hai người cùng chơi đúng  lượt. Tại mỗi lượt chơi, mỗi người trong hai người chọn một hình vuông kích thước p × p  của mình rồi bí mật viết ra một mảnh giấy hai số là tọa độ góc trái trên của hình vuông mà mình chọn. Sau đó cả hai công bố hình vuông của mình. Những viên bi nằm trong hình vuông mà hai người chơi chọn sẽ bị đổi màu, trừ những viên bi nằm trong cả hai hình vuông.

Sau  lượt, trò chơi kết thúc, nếu trên lưới số viên bi xanh nhiều hơn số viên bi đỏ thì người chơi thứ nhất thắng cuộc, ngược lại nếu số viên bi xanh ít hơn số viên bi đỏ thì người thứ hai thắng cuộc. Trường hợp số bi màu xanh bằng số bi màu đỏ thì trò chơi kết thúc với kết quả hoà.

4.2       Cách thức thi đấu

Mỗi đội sẽ phải chuẩn bị một chương trình:

-         Chương trình thi đấu để đưa ra chiến thuật chọn hình vuông p × p.

Ban tổ chức sẽ tổ chức thi đấu giữa các cặp đấu loại trực tiếp. Mỗi cặp đấu sẽ đấu 5 trận. Đội nào chiến thắng nhiều trận hơn sẽ chiến thắng chung cuộc. Trong trường hợp có kết quả hòa, các trận đấu thêm sẽ được tiến hành từng trận một cho đến khi xác định được đội thắng cuộc. Chương trình của hai đội sẽ giao tiếp với chương trình của ban giám khảo để thi đấu với nhau trên một máy tính. Mỗi trận đấu diễn ra như sau:

-          Chương trình của ban tổ chức sẽ lần lượt giao tiếp với từng chương trình thi đấu của hai đội để mô phỏng cách chơi như đã mô tả trên đề bài.

-          Cuối cùng, chương trình của ban giám khảo sẽ xác định kết quả của trận đấu.

4.3       Định dạng tệp thông tin và cách thức giao tiếp (dự kiến)

Lưu ý: Định dạng tệp thông tin sẽ được mô tả chi tiết trong đề chính thức.

Dữ liệu vào được cho trong tệp văn bản “DOIMAU.INP” có dạng:

-          Dòng đầu gồm năm số nguyên dương m,n,k,t, p (m,n,k,t, p ≤ 100)

-           dòng sau, mỗi dòng một xâu độ dài  mô tả trạng thái lưới ban đầu. Mỗi xâu chỉ gồm các ký tự ‘x’, ‘d’, ‘.’ tương ứng mô tả ô chứa bi xanh, chứa bi đỏ và ô không có bi.

Chương trình thi đấu của các đội sẽ giao tiếp với chương trình của ban giám khảo thông qua gọi các hàm từ một thư viện do ban giám khảo cung cấp. Mỗi lượt đi, chương trình thi đấu của các đội sẽ gọi hàm xuất từ thư viện với tham số là hai số nguyên dương x, y cách nhau bởi dấu cách mô tả tọa độ tâm của hình vuông p × p được chọn.

THƯỜNG TRỰC BAN TỔ CHỨC HỘI THI