#P9585. Minimizing Anger in CC Hotel
Minimizing Anger in CC Hotel
Minimizing Anger in CC Hotel
Little C owns a hotel, called CC Hotel. One day, the hotel receives n guests. Little C must assign each guest to a room on a single floor. There are m rooms available on that floor, and the rooms are arranged in a circular manner. In other words, for every room x (where 1 ≤ x ≤ m), room x is adjacent to room ((x mod m) + 1), and vice versa.
Each room can host at most one guest. The guests are very picky: they require that the rooms adjacent to theirs are empty. For any guest, if k of the rooms adjacent to his assigned room are occupied, then his anger level increases by k points.
Your task is to help Little C assign the n guests into the m rooms (with n ≤ m) in such a way that the total anger value of all guests is minimized. In particular, if the chosen room assignment causes two guests to be assigned in adjacent rooms, both of them will incur an anger value of 1 for that adjacency. Thus, each pair of adjacent occupied rooms contributes 2 points to the total anger value.
Hint: It is always possible to assign guests to rooms. Notice that if m ≥ 2n
, you can avoid placing any guests adjacently, achieving a total anger value of 0. If m < 2n
, then there must be at least 2n - m
pairs of adjacent occupied rooms, resulting in a minimum total anger value of 2*(2n - m)
.
Mathematical Formula:
If \(m \ge 2n\), then \(\text{Anger} = 0\). Otherwise, if \(m < 2n\), then \(\text{Anger} = 2(2n - m)\).
inputFormat
The input consists of a single line containing two integers n and m separated by spaces, representing the number of guests and the number of rooms respectively. You may assume that n ≤ m.
Input Format:
n m
outputFormat
Output a single integer — the minimal total anger value of all guests if they are assigned optimally.
sample
5 10
0