【Codeforces Round #639 (Div. 2) B】Card Constructions

题目链接

点我呀

翻译

给你 (n) 张卡, 问你最多能叠成多少个金字塔卡组。

题解

找找规律会发现。

高度为 (h) 的三角形, 一共有 (0+1+2+...+h-1) 个横着放的卡。

然后一共有 (2 imes (1+2+3+...+h)) 个竖着放的卡。

所以高度为 (h) 的三角形一共有 $ frac{ (0 + h-1) imes h}{2} + 2 imes frac{ (1+h) imes h}{2}$ 张卡片

能在 (mathcal{O}(sqrt{n})) 的时间复杂度下算出来 (1) ~ (maxh) 高度的三角形需要多少张卡片, 其中 (maxh) 是

(10^9) 规模的 (n) 能够堆成的最高高度的三角形。

预处理出来之后, 每个询问从大到小把所有高度的三角形试一下能不能用 (n) 张卡片堆出来, 能堆出来就

减去就行 (别真一个一个减啊, 直接用除法和取模表示扣掉卡片)

代码

#include<bits/stdc++.h>
#define ll long long
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;

const int N = 26e3;
const int MOD = 998244353;

int n,m;
int a[N+10];

int main(){
    #ifdef LOCAL_DEFINE
        freopen("D:\rush.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    //an = 2*n + 3*n*(n-1)/2
    rep1(i, 1, N){
        a[i] = 2 * i + 3 * i * (i - 1) / 2;
    }
    int T;
    for (cin >> T;T > 0;T--){
        cin >> n;
        int cnt = 0;
        rep2(i, N, 1){
            cnt += n / a[i];
            n = n % a[i];
        }
        cout << cnt << endl;
    }
    return 0;
}