#P9585. 「MXOI Round 2」酒店

    ID: 10721 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 1 上传者: 标签>模拟数学洛谷原创O2优化洛谷月赛

「MXOI Round 2」酒店

Problem Description

Xiao C opened a hotel called CC Hotel.

One day, nn guests came to CC Hotel. Xiao C needs to arrange all of them on a certain floor of the hotel. Each room can accommodate only one guest.

There are mm rooms on this floor. All mm rooms are empty, and these mm rooms form a ring. That is, for every 1xm1 \le x \le m, room xx is adjacent to room ((xmodm)+1)((x \bmod m)+1), and room ((xmodm)+1)((x \bmod m)+1) is adjacent to room xx, where xmodmx \bmod m denotes the remainder when xx is divided by mm.

All nn guests are very picky: they want the rooms adjacent to their own room to be unoccupied. For a guest, if among the rooms adjacent to their room there are kk occupied rooms, then this guest will gain kk points of anger.

You need to help Xiao C assign rooms so that the sum of all guests' anger values is minimized, and output the minimum possible sum of anger values of all guests.

Input Format

Two integers n,mn,m.

Output Format

One integer, representing the minimum possible sum of all guests' anger values.

3 5
2
1 4
0

Hint

Sample Explanation #1

For these 55 rooms, one feasible arrangement is: empty, occupied, occupied, empty, occupied.

It can be proven that the minimum possible sum of all guests' anger values is 22.

Constraints

For 100%100\% of the testdata, 1n1001 \le n \le 100, 3m1003 \le m \le 100, and it is guaranteed that nmn \le m.

Test Point ID Special Property
131\sim3 Guaranteed that 2nm2n \le m
464\sim6 Guaranteed that m=n+1m = n + 1
7107\sim10 None

Translated by ChatGPT 5