eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Единицы

опубликовано 19.02.2020, 19:21:13

how can i solve it easily

опубликовано 29.01.2023, 12:31:55

that was so tasty //CrazzyCat

опубликовано 28.03.2024, 05:40:34

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;

}