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）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 typedef __int64 LL;
 8 
 9 inline LL cal(LL x)
10 {
11     return x*(3*x+1) / 2;
12 }
13 
14 int main()
15 {
16     LL n;
17  // freopen("input.txt", "r", stdin);
18     while (scanf("%I64d", &n) != EOF)
19     {
20         LL ans = 0;
21         for (LL i = 1; cal(i) <= n; i++)
22         {
23             if ((n-cal(i)) % 3 == 0)
24                 ans++;
25         }
26         printf("%I64d
", ans);
27     }
28     return 0;
29 }

版本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 = 2;
        ans = 0, sum = 0;

        for ( ; sum + cal <= n; )    
        {
            sum += cal;
            LL remain = n - sum;
            if (remain % 3 == 0)
                ans++;
            cal += 3;
        }
        printf("%I64d
", ans);
    }
    return 0;
}