TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1535
  • Problem
  • P1535【Usaco Oct08 Gold】建造栅栏(Building A Fence)
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    勤奋的Farmer John想要建造一个由四面围成的栅栏来关住那些奶牛。他现在有一块长度为N(4 <= N <=100000)的长木板,他需要把这块长木板切成边长均为正整数的四块,使得他能建造一个栅栏。请问他有多少种不同的切割方式能使切割出来的木板围成一个四面的栅栏。
    注意:
    1.    四边形即可,不一定是矩形。
    2.    栅栏围成的面积必须大于0且木板必须用完
    3.    结果可以用64位整数存储, 只要大木板的切割点不同就当成是不同的方案

    Input Format

    仅一行,整数N

    Output Format

    仅一行,Farmer John能将木板分割开来并能围成四边形的方案数。

    Sample Input

    6

    Sample Output

    6

    Hint

    样例解释:
    Farmer John有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).

    其中有四种情况是不能围成一个四边形的:(1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), (3,1, 1, 1)

    原题数据较弱,此题数据已加强


    Source  Usaco October 2008 Gold