Editorial for Bedao Mini Contest 15 - ROBOT


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Để Robot có thể quay về vị trí ban đầu thì số lên di chuyển lên trên phải bằng số lần di chuyển xuống dưới và số lần di chuyển qua trái phải bằng số lần di chuyển qua phải. Nói cách khác, trong ~n~ kí tự, số kí tự ~U~ bằng số kí tự ~D~ và số kí tự ~L~ bằng số kí tự ~R~. Do đó ~n~ phải là số chẵn, nếu không sẽ không thể thay đổi sao cho thỏa mãn điều kiện trên được.

Gọi ~a~, ~b~ và ~x~, ~y~ lần lượt là số kí tự ~U~, ~D~ và ~L~, ~R~. Ta cần thay đổi ít nhất sao cho ~a = b~ và ~x = y~

Đáp án tối ưu sẽ là ~\frac{|a - b| + |x - y|}{2}~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.