Cod sursa(job #7544)

Utilizator filipbFilip Cristian Buruiana filipb Data 21 ianuarie 2007 17:02:55
Problema Triplete Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define NMax 15

int N, M, nr_bit[1<<NMax], D[4098][300], x[65537], y[65537], cnt = 0, rst[4098];

int main(void)
{
    int i, j, octet, p;
    
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    
    for (i = 0; i < (1<<NMax); i++)
        for (j = 0; j < NMax; j++)
            if (i & (1<<j))
               nr_bit[i]++;
                                           
    scanf("%d %d", &N, &M);
    for (i = 0; i < N; i++) rst[i] = i % NMax;
    

    for (p = 1; p <= M; p++)
    {
        scanf("%d %d", &i, &j);        
        i--; j--;    
        octet = j/NMax; D[i][octet] += (1<<rst[j]);           
        octet = i/NMax; D[j][octet] += (1<<rst[i]);
        
        x[p] = i; y[p] = j;
    }
    

    p = N/NMax;
    for (i = 1; i <= M; i++)
        for (j = 0; j <= p; j++)
            cnt += nr_bit[ D[x[i]][j] & D[y[i]][j] ];        
                
    printf("%d\n", cnt/3);
    
    return 0;
}