#include using namespace std; using LL = long long; const LL LIMIT = 4500; // 上限を, 4500 * 4501 / 2 = 10127250 に 変更. int main() { // 1. 入力情報取得. LL N; cin >> N; // 2. 硬貨準備. map m; for(int i = 0; i < LIMIT; i++){ LL c = (i + 1) * (i + 2) / 2; m[c]++; } // for(auto &p : m) cout << p.first << endl; // 3. 支払う硬貨をカウント. // i円以下の最小支払い回数を計算していく. // -> 10000まで調べると, 1 or 2 or 3 のいずれかだった. // なので, 以下のようにロジック変更. // ① map に ある … 1回. // ② map を巡回しペアが見つかった … 2回. // ③ 上記以外 … 3回. // 3-1. 条件③ を 設定. int ans = 3; // 3-2. 条件② の チェック. for(auto &p : m){ LL a = p.first; LL b = N - a; // ex. // N = 10001 ならば, 3回. (4[ms]) // N = 10000000 ならば, a=1719585 b=8280415 の 2回. (5[ms]) // // ex. // N = 8 // -> 2回??? // -> WA(6 + 1 + 1 の 3枚が最小). // -> a=5 b=3 の 謎出力 が 見つかった(a=5 は, map の要素でない筈). // if(m[b] > 0){ if(m[a] > 0 && m[b] > 0){ // cout << "a=" << a << " b=" << b << endl; ans = 2; break; } } // 3-3. 条件① の チェック. if(m[N] > 0) ans = 1; // 4. 出力. cout << ans << endl; return 0; }