Cod sursa(job #122645)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 13 ianuarie 2008 13:03:38
Problema Puteri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <string.h>

const int N_MAX = 100010;

struct putere {
	char a, b, c;
} v[N_MAX];

int nr[130][130][130];

char step[130][130][130], mod[130][130];

int kkt[] = {2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,
82,83,85,86,87,89,91,93,94,95,97,101,102,103,105,106,107,109,110,111,113,114,115,118,119,122,123,127};

int kkt2[] = {0,0,0,2,0,2,0,0,2,2,0,0,2,2,0,2,0,3,0,2,2,2,0,2,2,0,3,0,2,0,2,0,2,2,2,0,0,2,2,3,0,2,3,0,0,2,2,3,0,2,0,2,2,2,0,2,2,2,2,0,0,3,0,3,2,0,0,3,2,0,3,
2,2,2,2,2,0};

int is[130];

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

	int N, i, j;
	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) scanf("%d %d %d\n", &v[i].a, &v[i].b, &v[i].c);

	for (i = 1; i <= 128; i ++) {
		for (j = 1; j <= 128; j ++) {
			mod[i][j] = i % j;
		}
	}

	int nrdiv, x, y, z, stp = 1, p, a, b, c;
	long long fin = 0, rez;

	for (p = 0; p < 77; p ++) {
		nrdiv = kkt2[p];
		i = kkt[p];

		if (nrdiv == 0) nrdiv ++;
	
		for (j = 1; j <= N; j ++) {
			x = mod[v[j].a][i], y = mod[v[j].b][i], z = mod[v[j].c][i];
			if (step[x][y][z] < stp) {
				step[x][y][z] = stp;
				nr[x][y][z] = 1;
			} else nr[x][y][z] ++;
		}

		rez = 0;
		for (j = 1; j <= N; j ++) {
			x = mod[v[j].a][i], y = mod[v[j].b][i], z = mod[v[j].c][i];
			a = mod[(i - x)][i], b = mod[(i - y)][i], c = mod[(i - z)][i];

			if  (nr[x][y][z]) {

				if (mod[(2 * x)][i] == 0 && mod[(2 * y)][i] == 0 && mod[(2 * z)][i] == 0) {
					rez += (long long) nr[x][y][z] * (nr[x][y][z] - 1) / 2;
				} else {
					if (nr[a][b][c]) {
						rez += (long long) nr[x][y][z] * nr[a][b][c];
						nr[a][b][c] = 0;
					}
				}
	
				nr[x][y][z] = 0;
			}
		}

		if (mod[nrdiv][2] == 1) fin += rez;
		else fin -= rez;

		stp ++;
	}

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

	return 0;
}