Cod sursa(job #612680)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 9 septembrie 2011 15:57:24
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;

ifstream in("auto.in");
ofstream out("auto.out");

int n,x[9009],y[9009],divi[1000],nrdiv,sum,ssum;
queue<int> q;

inline void scoate(int k) {
    if(q.size()>=k) {
        ssum-=q.front();
        q.pop();
    }
}

void sol(int k) {
    int i;
    ssum=0;
    while(!q.empty())
        q.pop();

    for(i=1;i<=n;++i)
        y[i]=x[i];

    for(i=1;i<=n;++i) {

        scoate(k);

        y[i]-=ssum;

        if(y[i]<0)
            return;

        q.push(y[i]);
        ssum+=y[i];
        y[i]=0;

    }

    scoate(k);

    if(ssum!=0)
        return;

    for(i=1;i<=n;++i)
        if(y[i]!=0)
            return;

    out << k << " ";

}

int main() {
    int w,t,i;

    in >> t;

    for(w=1;w<=t;++w) {
        in >> n;

        sum=0;

        for(i=1;i<=n;++i) {
            in >> x[i];
            sum+=x[i];
        }

        out << "1 ";

        for(i=2;i<=sum && i<=n;++i)
            if(sum%i==0)
                sol(i);

        out << "\n";

    }

    return 0;
}