Cod sursa(job #348396)

Utilizator serbanlupulupulescu serban serbanlupu Data 15 septembrie 2009 18:28:40
Problema Oite Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
//infoarena
//pb	:		oite
//O(n^2)

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define PRIM 666203

int nr_oi;
int sum;
int oi[1050];

struct node
{
	int i, j;
	node(int left, int right)
	{
		this->i=left;
		this->j=right;
	}
};

vector<node > H[PRIM];

int number;

void read()
{
	fstream f("oite.in", ios::in);
	f>>nr_oi;
	f>>sum;
	for (int i=1; i<=nr_oi; ++i)
		f>>oi[i];
	f.close();
}

void check(int temp, int left, int right)
{
	vector<node >::iterator it;
	for (it=H[temp%PRIM].begin(); it<H[temp%PRIM].end(); it++)
		if (temp == (oi[it->i]+oi[it->j]))
			if ( left!=it->i && left!=it->j && right!=it->i && right!=it->j && it->j < left)
			{
				++number;
				break;
			}
}

void solve()
{
	for (int i=1; i<=nr_oi; ++i)
		for (int j=i+1; j<=nr_oi; ++j)
		{
			node nou(i, j);
			H[(oi[i]+oi[j])%PRIM].push_back(nou);
		}

	for (int i=1; i<=nr_oi; ++i)
		for (int j=i+1; j<=nr_oi; ++j)
		{
			check(sum-oi[i]-oi[j], i, j);
		}

	fstream g("oite.out", ios::out);
	g<<number<<"\n";
	g.close();
}

int main()
{
	read();
	solve();
	return 0;
}