30/09/2018, 21:37

Xin ý tưởng một bài toán khó

Một sân được lát bằng các ô vuông 11, mỗi ô thì được tô một màu . Một sân được gọi là TỐT nếu tất cả các hình chữ nhật có chu vi 2n không có 2 hình vuông nào trùng màu. Với input là n tìm số màu nhỏ nhất cần để tô vào sân để sân TỐT .

Nguyen Ca viết 23:47 ngày 30/09/2018

Có ý tưởng này không biết được không:
chu vi = 2*n nên a(dài)+b(rộng) =n. Như vậy diện tích có thể thay đổi tùy thuộc a và b.

Liệt kê các trường hợp mà a +b =n -> diện tích là ab -> số đỉnh ab (mỗi đỉnh là 1 ô vuông 1*1) -> tạo ma trận kề cho mỗi trường hợp
Áp dùng bài toán tô màu đồ thị cho mỗi trường hợp -> tim ra số màu thích hợp
So sánh lấy trường hợp có số màu nhỏ nhất.
Ý tưởng thế. Ai có cao kiến gi không

Kollein Vĩnh viết 23:48 ngày 30/09/2018

Bạn dùng phương pháp giải ngược
Và tỉ lệ…

chichi viết 23:40 ngày 30/09/2018

Noi chi tiết hơn đi bạn

Kollein Vĩnh viết 23:45 ngày 30/09/2018

Đặt c: số màu ít nhất để tô
A,B lần lượt là cạnh nhỏ và cạnh lớn (A < B).
thoả theo đề bài với ô vuông 11 Có các trường hợp sau:
max(A)=B-1, sân gần giống hình vuông
min(A)=1, sân giống như cái cột nhà
max(B)=2n-A, với A là min sân cũng giống cột nhà
min(B)=3, vì A+B=2*n => min(n)=2 cái này dễ hiểu mà
=> A+B=4 do đó B=3 trường hợp này B vừa là min vừa là max do min(n) bắt buộc phải bằng 2
… Tới đây vậy chắc bạn đã hiểu làm gì tiếp theo