#P3598. [Scoi2014]方伯伯的商场之旅
[Scoi2014]方伯伯的商场之旅
[SCOI2014] 方伯伯的商场之旅
题目描述
方伯伯去参加商场举办的游戏。商场的工作人员按位置编号排成一行。位置 的人面前有若干堆石子,分别对应 的 进制表示的各个数位。每堆的石子数等于该数位的数字,石子堆依数位顺序排列。
对每位编号在闭区间 内的工作人员,都要把他面前的石子集中到同一堆。一次操作可将某一堆中的若干颗石子移动到同一个人面前的另一堆。代价等于移动的石子数乘以两堆之间的距离,距离按堆的位置编号之差的绝对值计算。
例如在十进制下,位置 的人面前各堆有 颗石子。集中到第三堆的代价为 ,这是他的最小代价。
商场给出 ,并承诺方伯伯完成任务后,代价越小就送他越多的椰子。求所有这些工作人员的最小总代价。
输入格式
一行三个整数 ,分别表示起始位置、结束位置和进制。
输出格式
输出一行一个整数,表示最小总代价。
样例
3 8 3
5
数据范围
对于 的数据,。