Решение задачи Сумма произведений с Меньшиков

Без пояснения   Просмотров: 33


Дан набор переменных x1, x2, ..., xN. Каждая переменная xi может принимать значение только -1, 0 или +1. Для данного целого числа S требуется определить количество способов присвоить переменным xi значения так, чтобы сумма всех возможных произведений xi * xj была равна S, где i < j и i, j = 1, 2, ..., N. Два способа считаются различными, если они содержат различное число xi = 0.

Ограничения: 2 <= N <= 10 000, -10 000 < S < 10 000.

Код

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int n,s;
void input()
{
    cin>>n>>s;
}
int F(int n)
{
    return n*(n-1)>>1;
}
void solve()
{
    int amount = 0;
    for (int nz = 0; nz<=n; nz++)
    {
        for (int minus = 0; minus<=nz; minus++)
        {
            int plus = nz - minus;
            if (F(minus) + F(plus) - plus*minus == s)
            {
                amount++;
                // break нужен для того, чтобы не считать
                // одинаковые комбинации, содержащие
                // одинаковое количество нулей
                break;
            }
        }
    }
    cout<<amount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}
 

         

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



Комментарии

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