Решение задачи "Сумма слагаемых одинаковой четности" с Codeforces

С пояснением   Просмотров: 32


Заданы два целых положительных числа n (1≤n≤109) и k (1≤k≤100). Представьте число n в виде суммы k положительных целых чисел одинаковой четности (с одинаковыми остатками от деления на 2).

Иными словами, найдите такие a1,a2,…,ak, что все ai>0, n=a1+a2+…+ak и либо все ai одновременно четные, либо все ai одновременно нечетные. Если такого представления не существует, то сообщите об этом.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t, n, k;
    cin >> t;
    for(int i = 0; i < t; ++i){
        cin >> n >> k;

        if((n - (k - 1)) % 2 && n - (k - 1) > 0){
            cout << "YES" << endl;
            for(int j = 0; j < k - 1; ++j)
                cout << 1 << " ";
            cout << n - (k - 1);
        }

        else if((n - (2 * (k - 1))) % 2 == 0 && n - (2 * (k - 1)) > 0){
            cout << "YES" << endl;
            for(int j = 0; j < k - 1; ++j)
                cout << 2 << " ";
            cout << n - (2 * (k - 1));
        }
        else
            cout << "NO";
        cout << endl;
    }

    return 0;
}

         

 Администратор Photo Автор: Администратор


Рассмотрим два случая: когда мы выбираем все нечетные числа и все четные числа. В обоих случаях давайте попробуем максимизировать максимум. Таким образом, если мы выбираем нечетные числа, давайте попробуем взять k−1 единицу и остаток n−(k−1). Но нам необходимо убедиться, что n−k+1 больше нуля и нечетно. И в случае четных чисел давайте попробуем взять k−1 двойку и остаток n−2(k−1). Нам также надо проверить, что остаток больше нуля и является четным. Если ни один из случаев не подошел, надо вывести «NO».

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться