Proficient.
Put your skills to the test.

Problem summary

Choose an integer quantity for every price ai so that Σai·quantityi=N. Positive quantities sell that product, negative quantities buy it, and zero ignores it. Print each quantity as a product of at most100 integer factors, each with absolute value at most10^9, or report impossibility.

Source clarification. The original accepts factor products rather than machine-sized coefficients. This implementation uses the sequential gcd refinement described after the official divide-and-conquer solution: https://infos.infosbg.com/files/Contests/ETI/2017/B/analyses/B1_shopping_analysis.docx

Constraints

1 ≤ T ≤2; 2 ≤ K ≤100000; 1 ≤ ai,N ≤10^9.

Worked example

Original statement sample input; one valid output from the implementation below.

1
2
3 5
11

2*11 -1*11

Solution analysis

1. An integer linear combination of all prices can produce exactly the multiples of their gcd g. Thus g must divide N. Extended Euclid produces x,y with x·oldGcd+y·nextPrice=newGcd, allowing a solution for a prefix to be extended by one price.
2. Only process a price when it strictly decreases the current gcd. Then multiply all currently used coefficient products by x and give the new price coefficient y. Other prices receive0. A proper divisor is at most half its previous value, so at most29 such decreases occur for prices≤10^9. Consequently no coefficient needs anywhere near100 factors.
3. After processing prices, multiply all nonzero coefficients by N/g. Keep factors separate instead of evaluating their possibly enormous product. For3,5, Euclid gives2·3−1·5=1. Multiplying by11 gives quantities22 and−11, printed as2*11 and−1*11. They yield66−55=11.

Why it works

Initially coefficient1 on the first price represents its gcd. Each Euclidean update substitutes an exact identity for the current gcd, so the maintained factored coefficients always represent the new gcd. Every price skipped is a multiple of the current gcd and cannot change it. Finally scaling by N/g gives exactly N. Conversely every integer combination is divisible by the final gcd, proving that the rejection criterion is necessary and sufficient.

Watch out. Do not multiply the full coefficient products in a machine integer. Factors can be negative, and 0 is a valid quantity. All emitted individual factors fit the required range. A solution may sell only, as the source allows postponing shopping.

An independently written complete program with standard headers.

#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
long long extendedGcd(long long a,long long b,long long&x,long long&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    long long nextX,nextY;
    long long result=extendedGcd(b,a%b,nextX,nextY);
    x=nextY;
    y=nextX-(a/b)*nextY;
    return result;
}
void multiply(vector<long long>&factors,long long value){
    if(value==1){
        return;
    }
    if(factors.size()==1&&factors[0]==1){
        factors.clear();
    }
    factors.push_back(value);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        int count;
        cin>>count;
        vector<long long>prices(count);
        for(long long&price:prices){
            cin>>price;
        }
        long long target;
        cin>>target;
        vector<vector<long long>>factors(count);
        factors[0].push_back(1);
        vector<int>active{0};
        long long currentGcd=prices[0];
        for(int i=1;i<count&&currentGcd!=1;++i){
            long long nextGcd=gcd(currentGcd,prices[i]);
            if(nextGcd==currentGcd){
                continue;
            }
            long long x,y;
            extendedGcd(currentGcd,prices[i],x,y);
            // Record factors without ever evaluating their huge products.
            if(x==0){
                for(int index:active){
                    factors[index].clear();
                }
                active.clear();
            }
            else{
                for(int index:active){
                    multiply(factors[index],x);
                }
            }
            factors[i].push_back(y);
            active.push_back(i);
            currentGcd=nextGcd;
        }
        if(target%currentGcd!=0){
            cout<<"No solutions\n";
            continue;
        }
        for(int index:active){
            multiply(factors[index],target/currentGcd);
        }
        for(int i=0;i<count;++i){
            if(i>0){
                cout<<' ';
            }
            if(factors[i].empty()){
                cout<<0;
            }
            else{
                for(int j=0;j<static_cast<int>(factors[i].size());++j){
                    if(j>0){
                        cout<<'*';
                    }
                    cout<<factors[i][j];
                }
            }
        }
        cout<<'\n';
    }
}