[USACO Oct08]搭建篱笆

成绩 0 开启时间 2013年01月21日 星期一 06:50
折扣 0.8 折扣时间 2013年01月21日 星期一 06:50
允许迟交 关闭时间 2013年01月21日 星期一 06:50
输入文件 quad.in 输出文件 quad.out

勤奋的农夫约翰想要修建一个4面的篱笆墙把他的奶牛们围起来。他有一块长为N的木板(4<=N<=2500)于是他想要在三个点把他们切断用以得到4块木板。

只要能构成成四边形篱笆,这4块板子的长度可以是任意正整数。那么为了得到完整的篱笆农夫约翰有多少不同的种方法切这个长木板呢?

注意:

  • 对于两种方案而言,只要一方存在一个另一方没有的切割点,那它们就将视为不同的方案。不必担心对称或那个其他复杂的情况的排除。
  • 请注意,篱笆所围的面积应当大于0。
  • 你将高兴的是,我们保证答案适合有符号的32位整型变量。

分数:250

问题名称:quad

输入格式:

  • 第1行:一个单独的整数:N

输入样例(file quad.in):

6

输入说明:这个板子的长度是6。

输出格式:

  • 第1行:一个单独的整数表示切割方案数。

输出样例:

6

输出说明:

农夫约翰有10种方法切割木板:(1, 1, 1, 3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); (3, 1, 1, 1).但是其中的4种--(1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), (3,1, 1, 1)是不能构成篱笆的。