eolymp
bolt
Try our new interface for solving problems
Problems

The number of ones

published at 2/19/20, 7:21:13 pm

how can i solve it easily

published at 1/29/23, 12:31:55 pm

that was so tasty //CrazzyCat

published at 3/28/24, 5:40:34 am

int main() { int n; cin >> n;

vector<int> vec(n + 1);
vec[1] = 1;

for (int i = 2; i <= n; ++i) {
    vec[i] = i;
    for (int j = 1; 2 * j < i; ++j)
        if (vec[j] + vec[i - j] < vec[i])
            vec[i] = vec[j] + vec[i - j];

    for (int j = 2; j * j <= i; ++j)
        if (i % j == 0)
            if (vec[j] + vec[i / j] < vec[i])
                vec[i] = vec[j] + vec[i / j];
}

cout << vec[n] << endl;

return 0;

}