ядра

/*
 * main.cpp
 *
 *  Created on: Mar 18, 2018
 *      Author: vad
 */

#pragma comment(linker,"/STACK:64000000")

#include <iostream>
#include <fstream>
#include <ctime>

std::ifstream inp;
std::ofstream outp;

#define cin inp
#ifndef LC_GLOBAL_LOCALE
#define cout outp
#endif

void end();
void start(const char *ifname,const char *ofname);

using namespace std;

////////////////////////////////////////////
//                START CODE              //
////////////////////////////////////////////

#include <map>
#include <list>

typedef long int li;
typedef long long ll;

list<li> pirs;
li anses[300001];

void init_pirs(){
    li sum = 0;
    li c = 0;
    li x = 0;
    while(sum <= 300000){
        c++;
        x+=c;
        sum+=x;
        pirs.push_back(sum);
    }
}

void init_anses(){
    anses[0] = 0;
    for(li x = 1; x <= 300000; x++){
        auto pir = pirs.begin();
        anses[x] = anses[x-*pir]+1;
        while(*pir <= x)
            anses[x]=min(anses[x-*pir]+1, anses[x]),
            pir++;
    }
}

int main()
{
    start("king2.in", "king2.out");

    init_pirs();
    init_anses();

    li m;
    cin >> m;

    while(m--)
    {
        li a;
        cin >> a;
        cout << anses[a] << endl;
    }

    end();
    return 0;
}





void start(const char *ifname, const char *ofname){
#ifdef LC_GLOBAL_LOCALE
    inp.open("input.txt");
#else
    inp.open(ifname);
    outp.open(ofname);
#endif
}
void end(){
#ifdef LC_GLOBAL_LOCALE
    cout << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#else
    outp.close();
#endif
    inp.close();
}