Решение задачи Феникс и баланс с Codeforces

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


У Феникса есть n монет с весами 21,22,…,2n. Он знает, что n — четное.

Он хочет сложить монеты в две кучки так, что в каждой кучке будет ровно n2 монет и разница суммарных весов между кучками будет минимальна. Формально, обозначим за a сумму весов в первой кучке, а за b — сумму весов во второй. Помогите Фениксу минимизировать |a−b|, то есть модуль числа a−b.

Код

#include <bits/stdc++.h>

using namespace std;
vector<long long > a;

int main()
{
    int t, n;
    cin >> t;
    for(int i = 0; i < t; ++i){
        cin >> n;
        int s1 = pow(2, n), s2 = 0;
        for(int i = 1; i < n/2; ++i)
            s1+=pow(2, i);
        for(int i = n/2; i < n; ++i)
            s2+=pow(2, i);
        cout << abs(s2 - s1) << endl;
    }
    return 0;
}

         

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


Объясню, приведя тест при n = 6:
2, 4, 8, 16, 32, 64 - числа, которые мы должны использовать.
s1 = 2 + 4 + 64
s2 = 8 + 16 + 32
при таком алгоритме мы найдем нужный нам результат
ОТВЕТ: s2 - s1


Комментарии

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