#include #include #include #include #include #include #include using namespace std; int main() { int n; cin >> n; int m = 155000; vector a(m); a[0] = 0; for (int i = 1; i < m; i++) { int x = 1 << 30; for (int k = 1;; k++) { int l = k * (k + 1) / 2; if (l > i) break; x = min(x, a[i - l] + 1); } a[i] = x; } int i = n; int x = 1 << 30; for (int k = 1;; k++) { int l = k * (k + 1) / 2; if (l > i) break; if (i - l >= m) continue; x = min(x, a[i - l] + 1); } cout << x << endl; return 0; }