Cod sursa(job #850093)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 7 ianuarie 2013 23:28:55
Problema Oite Scor 100
Compilator cpp Status done
Runda 23dezile_5 Marime 0.89 kb
#include<fstream>
using namespace std;
typedef struct celula{
            int v,nr;
            celula *next;
            }*lista;
lista hash[666013];
int n,s,i,j,a[1050],sol,mm=666013;

void baga(int v){
     bool ok=1; lista p; int poz=v%mm;
     for (p=hash[poz]; p; p=p->next)
      if (p->v==v) { ++p->nr; ok=0; break; }
     if (ok) { p=new celula; p->v=v; p->nr=1; p->next=hash[poz]; hash[poz]=p; }
}

int cauta(int v){
    int rez=0,poz=v%mm;
     for (lista p=hash[poz]; p; p=p->next)
      if (p->v==v) { rez=p->nr; break; }
     return(rez);
}

int main(void){
    ifstream fin("oite.in");
    ofstream fout("oite.out");
    fin>>n>>s;
    for (i=1; i<=n; ++i) fin>>a[i];
    for (i=1; i<n; ++i) {
        for (j=i+1; j<=n; ++j)
         if (s-a[i]-a[j]>0) sol+=cauta(s-a[i]-a[j]);
        for (j=1; j<i; ++j) baga(a[i]+a[j]);
     }
     fout<<sol;
 return(0);
}