Cod sursa(job #1724232)

Utilizator denniscrevusDennis Curti denniscrevus Data 2 iulie 2016 16:17:12
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.29 kb
#include <fstream>
#define NMAX 520

using namespace std;

long long int patratele[10],sum[NMAX][NMAX],casuta1,casuta2,casuta3,casuta4,casuta5,casuta6,casuta7,casuta8,casuta9;
int v[NMAX][NMAX],i,j,n,col1,col2,lin1,lin2,x5,x6,test,x7,da,x8;

void suma()
{
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+v[i][j];
}
bool check2(long long a)
{
    if(sum[lin1][a]<casuta1)
        return 0;
    else
        return 1;
}
bool check1(long long a)
{
    if(sum[lin1][a]-casuta1<casuta2)
        return 0;
    return 1;
}
bool check(long long a)
{
    if(sum[a][col1]-casuta1<casuta4)
        return 0;
    return 1;
}
bool verificare()
{
    int b1=1,b2=1,b3=1,b4=1,b5=1,b6=1;

    casuta3=sum[lin1][n]-casuta1-casuta2;
    for(i=1;i<=9;i++)
        if(casuta3==patratele[i])
            b1=0;

    casuta5=sum[lin2][col2]-casuta1-casuta2-casuta4;
    for(i=1;i<=9;i++)
        if(casuta5==patratele[i])
            b2=0;

    casuta6=sum[lin2][n]-casuta1-casuta2-casuta3-casuta5-casuta4;
    for(i=1;i<=9;i++)
        if(casuta6==patratele[i])
            b3=0;

    casuta7=sum[n][col1]-casuta1-casuta4;
    for(i=1;i<=9;i++)
        if(casuta7==patratele[i])
            b4=0;

    casuta8=sum[n][col2]-casuta1-casuta2-casuta4-casuta5-casuta7;
    for(i=1;i<=9;i++)
        if(casuta8==patratele[i])
            b6=0;

    casuta9=sum[n][n]-casuta1-casuta2-casuta3-casuta4-casuta5-casuta6-casuta7-casuta8;
    for(i=1;i<=9;i++)
        if(casuta9==patratele[i])
            b5=0;

    if(b1==0 && b2==0 && b3==0 && b4==0 && b5==0 && b6==0)
        return 1;
    else
        return 0;
}

int cautbinlin2()
{
    int start=0;
    int step=1;
    for(;step<=n;step<<=1);
    for(;step;step>>=1)
    {
        int index=start+step;
        if(index>=n)
            continue;
        if(check(index)==0)
            start=index;
    }
    return start;

}int cautbincol2()
{
    int start=0;
    int step=1;
    for(;step<=n;step<<=1);
    for(;step;step>>=1)
    {
        int index=start+step;
        if(index>=n)
            continue;
        if(check1(index)==0)
            start=index;
    }
    return start;
}
int cautbincol1()
{
    int start=0;
    int step=1;
    for(;step<=n;step<<=1);
    for(;step;step>>=1)
    {
        int index=start+step;
        if(index>=n)
            continue;
        if(check2(index)==0)
            start=index;
    }
    return start;
}

int main()
{
    ifstream f("zone.in");
    ofstream g("zone.out");

    f>>n;

    for(i=1;i<=9;i++)
        f>>patratele[i];

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            {
                f>>v[i][j];
            }

    suma();

    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            g<<sum[i][j]<<" ";
        g<<"\n";
    }
    */

    for(x5=1;x5<=n-2;x5++)
    {
    lin1=x5;
    for(x8=1;x8<=9;x8++)
    {
        casuta1=patratele[x8];
        test=cautbincol1()+1;
        if(sum[lin1][test]==casuta1)
        {
            col1=test;
        }
        else continue;

    for(x6=1;x6<=9;x6++)
    {
        casuta4=patratele[x6];
        test=cautbinlin2()+1;
        //g<<test<<" "<<casuta4<<" "<<lin1<<" "<<col1<<" "<<casuta1<<"\n";
        if(sum[test][col1]-casuta1==casuta4)
        {
            lin2=test;
            //g<<lin1<<" "<<lin2<<" "<<col1<<" "<<casuta1<<" "<<casuta4;
        }
        else continue;

    for(x7=1;x7<=9;x7++)
    {
        casuta2=patratele[x7];
        test=cautbincol2()+1;
        //g<<test<<" "<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
        if(sum[lin1][test]-casuta1==casuta2)
        {
            col2=test;
           // g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
        }
        else continue;
        //g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta2<<"\n";
        da=verificare();
        //g<<da<<"\n";
        //g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2<<" "<<casuta1<<" "<<casuta2<<" "<<casuta3<<" "<<casuta4<<" "<<casuta5<<" "<<casuta6<<" "<<casuta7<<" "<<casuta8<<" "<<casuta9<<"\n";
        if(da==1)
        {
            g<<lin1<<" "<<lin2<<" "<<col1<<" "<<col2;
            return 0;
        }
    }
    }
    }
    }
}