Wednesday 12 August 2020

A. Rainbow Dash, Fluttershy and Chess Coloring - Codeforces Round #662 (Div. 2)

Link đề bài trên Codeforces.

Tóm tắt: Cho bàn cờ kích thước n ×  với các biên đã được dựng sẵn. Mỗi lần chơi, chú kỳ lân Rainbow Dash sẽ tô một ô bất kỳ thành màu xanh dương, sau đó chú sẽ tô các ô chạm vào ô đó theo kiểu bàn cờ vua. Khi Rainbow Dash không tô được ô nào theo quy tắc đó nữa, Fluttershy sẽ tô một số ô thành màu vàng cũng theo quy tắc trên. Trò chơi lặp lại đến khi bàn cờ vua hoàn tất.

Tìm số lượt tô ít nhất để hoàn thành trò chơi.

Hướng giải: trong bàn cờ vua n × n, số lượng ô đen bằng số lượng ô trắng (nếu n chẵn) và hơn nhau 1 ô (nếu n lẻ). Tổng quát, để tô hết các ô cần n / 2 + 1 lượt, trong đó n / 2 làm tròn xuống.

Link code mẫu (C++).


No comments:

Post a Comment

Popular posts