Pagini recente » Cod sursa (job #1460662) | Cod sursa (job #1893294) | Cod sursa (job #1121365) | Cod sursa (job #1486132) | Cod sursa (job #996518)
Cod sursa(job #996518)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;
#define mod 541
vector<vector<long> > H;
long c,L,A[1024];
inline void init() {
for(int i=0;i<mod;i++)
H.push_back(vector<long>());
};
inline void insert(long s) {
int h = s%mod;
H[h].push_back(s);
};
inline long find(long s) {
int h = s%mod;
int sz = H[h].size();
int count = 0;
for(int i=0;i<sz;i++) {
count += (H[h][i] == s);
};
return count;
};
int main() {
int C;
ifstream I("oite.in");
ofstream O("oite.out");
//long c,C,L, A[1024];
I >> C >> L;
c = 0;
int i,j,k,l;
while(c < C) {
long val;
I >> val;
if(val <= L-3) {
A[c] = val;
c++;
};
};
/*
* |----------- i -----------|
*
* |------j-----|
* |--find(s)---|
*
* |------------|
* |--insert(s)-|
*/
long S = 0;
init();
/*
*
* So first fix 2 of the numbers, so far you have A[i]+A[j]
* then try to find how many pairs in the hash add up to L-(A[i]+A[j]), that's
* the remainder which is needed to reach L.
*
* Inserting is only done with pairs behind the current i in order to assure that the pairs
* found(with find), are different than i,j.
*
* From this point of view I think i is a pivot of sorts.
*
*/
for(i=1;i<c;i++){
/* the last pair of two numbers A[i] and A[j] */
for(int j=i+1;j<c;j++) {
long lastTwo = L-(A[i]+A[j]);
if(lastTwo > 0)
S += find(lastTwo);
};
/* the first pair of two numbers */
for(int j=0;j<i;j++)
insert(A[i]+A[j]);
};
O << S;
};