codeforces 471C.MUH and House of Cards 解题报告

题目链接：http://codeforces.com/problemset/problem/471/C

题目意思：有 n 张卡，问能做成多少种不同楼层（floor）的 house，注意这 n 张卡都要用光。每层 floor 都由一定的 room 构成，每两个相邻 room 规定要有一个公共的ceiling。规定从上到下看，每层 floor 的 room 的数量呈递增的形式排布。

好容易想到构成最高层时用的最少数量的card需要多少。可以发现，每层的需要用到的card 可以用这个表达式表示： 3n-1 （第一层是最高层）。例如要构成 3 层，那么最少需要用到的card 为 15，从上到下依次为 2， 5， 8。求和是有条式子的，对于前 k 层需要用到的最少card是： n*(3n+1) / 2。

具体推法可以参考：http://codeforces.com/blog/entry/13986

（作者写了这么详细的题解，确实要给一个大大的赞啊～～～）

不过，知道最少的 card 之后还未得到答案，因为 n 有可能大于构成最高层的最少card数。那么此时就有剩余了。其实问题最关键的地方，就是如何利用这个剩余数来统计结果。

对于排到第 k 层的时候，求出当前剩余数remain =  n - sum_cardk（表示第k层需要的最少card），如果remain % 3 == 0 就表示该层是可以构建的，即可以够建高度为 k 的house。因为除了最高的一层（只需要两张card），下面每层如果要增加一个room，就需要3张card，ceiling需要一张嘛～～

版本 1 （利用求和公式，时间为 31ms）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 typedef __int64 LL;

 inline LL cal(LL x)

 {

     return x*(*x+) / ;

 }

 int main()

 {

     LL n;

  // freopen("input.txt", "r", stdin);

     while (scanf("%I64d", &n) != EOF)

     {

         LL ans = ;

         for (LL i = ; cal(i) <= n; i++)

         {

             if ((n-cal(i)) %  == )

                 ans++;

         }

         printf("%I64d\n", ans);

     }

     return ;

 }

版本2（暴力求和，不用公式，时间是 30ms）

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

typedef __int64 LL;

int main()

{

    LL n;

    while (scanf("%I64d", &n) != EOF)

    {

        LL cal, sum, ans;

        cal = ;

        ans = , sum = ;

        for ( ; sum + cal <= n; )

        {

            sum += cal;

            LL remain = n - sum;

            if (remain %  == )

                ans++;

            cal += ;

        }

        printf("%I64d\n", ans);

    }

    return ;

}