#P9585. 「MXOI Round 2」酒店

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

「MXOI Round 2」酒店

题目描述

小 C 开了一家酒店,叫做 CC Hotel。

一天,CC Hotel 来了 nn 位客人。小 C 需要把他们都安排在酒店的某一层中。每个房间中只能安排一位客人。

这一层共有 mm 间房间,这 mm 间房间都是空的,且这 mm 间房间形成了一个环形,即对于所有的 1xm1 \le x \le m,都有第 xx 间房间与第 ((xmodm)+1)((x \bmod m)+1) 间房间相邻,第 ((xmodm)+1)((x \bmod m)+1) 间房间与第 xx 间房间相邻,其中 xmodmx \bmod m 表示 xx 除以 mm 得到的余数。

nn 位客人都十分挑剔,他们希望与自己的房间相邻的房间中没有人。对于某一位客人,若与他的房间相邻的房间中,有 kk 间房间有人,则这位客人会产生 kk 点愤怒值。

你需要帮助小 C 安排房间,使得所有客人的愤怒值之和最小,并输出所有客人的愤怒值之和的最小值。

输入格式

两个整数 n,mn,m

输出格式

一个整数,表示所有客人的愤怒值之和的最小值。

3 5
2
1 4
0

提示

【样例解释 #1】

对于这 55 间房间,其中一组满足条件的安排方案为:不住人、住人、住人、不住人、住人。

可以证明所有客人的愤怒值之和的最小值为 22

【数据范围】

对于 100%100\% 的数据,1n1001 \le n \le 1003m1003 \le m \le 100,保证 nmn \le m

测试点编号 特殊性质
131\sim3 保证 2nm2n\le m
464\sim6 保证 m=n+1m=n+1
7107\sim10