问题1037--字符串拉伸

1037: 字符串拉伸

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

有一个字符串“0123456789”,长度为10个字符,现在你要把它拉伸成一个长度为L的字符串,拉伸的规则是把每个字符由单个变成连续的一段,例如“0001111122333344556788999”就是一个拉伸后的字符串,它的长度为25,其中,出现次数最多的字符是‘1’,共5次,出现次数最少的字符是‘6’(或‘7’),只有1次。
所谓的均匀拉伸是指:拉伸以后的字符串中,出现次数最少的字符和出现次数最多的字符,它们的出现次数之差不超过1。比如下面这个字符串就是一个长度为25的均匀拉伸:
0001122233445556677888999
对于给定的长度L,符合均匀拉伸的字符串可能有多个,例如下面这个字符串和上面的不同,但也是一个长度为25的均匀拉伸:
0011223344555666777888999
你的任务就是,给定L,统计有多少种不同的均匀拉伸。

输入

一个整数L(10<=L<=2*109)。

输出

输出一个整数C,表示长度为L的不同均匀拉伸字符串共有C个。

样例输入 Copy

11

样例输出 Copy

10

来源/分类