Cod sursa(job #996518)

Utilizator stefan.petreaStefan Petrea stefan.petrea Data 12 septembrie 2013 10:41:54
Problema Oite Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#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;
};