Cod sursa(job #1009012)

Utilizator jul123Iulia Duta jul123 Data 12 octombrie 2013 13:10:05
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
using namespace std;
int s[1000000],a[1000000],b[1000000];
int pivot(int left, int right)
{
    int p1,p2,p3,p,mini,maxi;
    p1=s[left + rand() % (right-left+1)];
    p2=s[left + rand() % (right-left+1)];
    p3=s[left + rand() % (right-left+1)];
    if(p1<=p2&&p1<=p3)
        mini=p1;
    if(p2<=p1&&p2<=p3)
        mini=p2;
    if(p3<=p1&&p3<=p2)
        mini=p3;
    if(p1>=p2&&p1>=p3)
        maxi=p1;
    if(p2>=p1&&p2>=p3)
        maxi=p2;
    if(p3>=p1&&p3>=p2)
        maxi=p3;
    p=p1+p2+p3-maxi-mini;
    return p;

}
void quicksort(int left, int right)
{
    int i=left, j=right, tmp, piv;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(s[i]<piv)
            i++;
        while(s[j]>piv)
            j--;
        if(i<=j)
        {
            tmp=s[i];
            s[i]=s[j];
            s[j]=tmp;
            tmp=a[i];
            a[i]=a[j];
            a[j]=tmp;
            tmp=b[i];
            b[i]=b[j];
            b[j]=tmp;
            i++;
            j--;
        }
    }
    if(left<j)
        quicksort(left,j);
    if(i<right)
        quicksort(i,right);

}
int cautam(int i,int j, int x)
{
if(x==s[(i+j)/2])
    return (i+j)/2;
else
if(i<j)
if(x<s[(i+j)/2])
return cautam(i,(i+j)/2 -1, x);
else return cautam((i+j)/2+1,j, x);
else return -1;
}

int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");
    int n, v[100], i, su, j, k, t=0, ok, x;
    f>>n>>su;
for(i=0;i<=n-1;i++)
    f>>v[i];
    for(i=0;i<=n-1;i++)
        for(j=i;j<=n-1;j++)
            for(k=j;k<=n-1;k++)
                {s[t]=v[i]+v[j]+v[k];
                a[t]=v[i];
                b[t]=v[j];
                t++;
            }
    quicksort(0,t-1);
    ok=1;
    i=0;
i=0;
while(i<=t-1 && ok==1)
    {
     x=s[i];
     j=cautam(i,t-1,su-x);
     if(j!=-1)
        {
            ok=0;
            g<<a[i]<<" "<<b[i]<<" "<<s[i]-a[i]-b[i]<<" "<<a[j]<<" "<<b[j]<<" "<<s[j]-a[j]-b[j];
        }
    i++;
    }
    f.close();
    g.close();
    return 0;




}