G - MUH and House of Cards

数论 规律

题目大意

两个棍子可以组成一个屋子，两个屋子之间要有一个棍子作为天花板，现给定棍子的个数n，问在棍子全部利用完的情况下，可以有的最大高度。

解题思路

很容易发现，每层的牌数为3t+2，先对x=n%3，当x=1时，最少有两个2，即最少有两层，当x=2时，最少有一层，x=3时最少有两层，刚好是x=3-x，现在假设有k层，最少为（3*0+2）+（3*1+2）+（3*2+2）+.......+（3*（k-1）+2<=n，整理得（k*（k+1)/2*3<=(n+k),然后再对层数加3，直到不满足上面的条件。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    long long n;
    scanf("%I64d",&n);
    long long x=n%3;
    x=3-x;
    long long cou=0;
    for(long long i=x;i*(i+1)/2*3<=(n+i);i=i+3)
    {
        cou++;
    }
    printf("%I64d\n",cou);
    return 0;
}