Cod sursa(job #129629)

Utilizator damaDamaschin Mihai dama Data 29 ianuarie 2008 20:15:09
Problema Puteri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>

const int prime[32] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 128};
int a[100001], b[100001], c[100001], n, d[128][128][128], nr = 0, s = 1;
long long v[128], sol;

void bkt(int);

int main()
{
    freopen("puteri.in", "r", stdin);
    freopen("puteri.out", "w", stdout);

    int i, p;

    scanf("%d", &n);

    for(i = 1; i <= n; ++i)
    {
        scanf("%d %d %d", &a[i], &b[i], &c[i]);
    }

    bkt(0);

    printf("%lld\n", sol);

    return 0;
}

void bkt(int k)
{
    if(k == 31)
    {
        int i, j, l;
        long long temp = 0;
        if(nr == 0)
            return;
        for(i = 1; i <= n; ++i)
        {
            ++d[a[i] % s][b[i] % s][c[i] % s];
        }
        for(i = 0; i < s; ++i)
        {
            for(j = 0; j < s; ++j)
            {
                for(l = 0; l <= s / 2; ++l)
                {
                    int newi = (s - i), newj = s - j, newl = s - l;
                    if(newi == s)newi = 0;
                    if(newj == s)newj = 0;
                    if(newl == s) newl = 0;
                    if(i == newi && j == newj && l == newl)
                    {
                        temp += (long long) d[i][j][l] * (d[i][j][l] - 1) / 2;
                        d[i][j][l] = 0;
                    }
                    else
                    {
                        temp += (long long) d[i][j][l] * d[newi][newj][newl];
                        d[i][j][l] = d[newi][newj][newl] = 0;
                    }
                }
            }
        }
        //printf("%d\n", temp);
        if(nr % 2 == 0)
        {
            sol -= temp;
        }
        else
        {
            sol += temp;
        }
    }
    else
    {
        bkt(k + 1);
        ++nr;
        s *= prime[k];
        if(s < 128)
            bkt(k + 1);
        --nr;
        s /= prime[k];
\
    }
}