CHỦ ĐỀ THAM KHẢO “BI ĐỔI MÀU” , BẢNG C – KHỐI THPT

Trò chơi “Bi đổi màu”

Trên lưới hình chữ nhật ô vuông. Các dòng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến m 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), 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

Tại mỗi lượt chơi, bạn chọn một hình vuông kích thước p × p của mình và tọa độ góc trái trên của hình vuông mà mình chọn. Những viên bi nằm trong hình vuông bạn chọn sẽ đổi màu từ xanh sang đỏ và tử đỏ sang xanh. Một chương trình của Ban Tổ chức sẽ chọn một hình vuông có kích thước q x q và vị trí đặt hình vuông, khi đó những viên bi nằm trong hình vuông đó sẽ đổi màu từ đỏ sang xanh và từ xanh sang đỏ (bạn không biết vị trí, kích thước của hình vuông này). Sau mỗi lượt chơi bạn sẽ nhận được số lượng các viên bi xanh trên lưới. Mỗi trận đấu có k lượt chơi. Kết thúc trận điểm số được tính là số lượng viên bi xanh trên lưới.

Phần chuẩn bị

Bạn cần chuẩn bị chương trình, tìm phương án chọn kích thước p và toạ độ (x,y) để đặt hình vuông sao cho sau k lượt chơi bạn được nhiều điểm nhất có thể.

Định dạng tệp thông tin và cách thức giao tiếp sẽ được mô tả chi tiết trong đề chính thức. Lưới hình chữ nhật cho trong tệp tin văn bản gồm m dòng, mỗi dòng là một xâu độ dài n 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.

Lượt xem: 311