//Superprime Rib - USACO Training Gateway - 2005

/*
ID: contato1
PROG: sprime
LANG: C
*/

#include <stdio.h>
#define NMAX 9
#define INFINITO 100000

int primos[NMAX][INFINITO], cont[NMAX];

int eh_primo(long int num) {
	int i;

	if (num==1||(!(num%2)&&num!=2)) {
		return 0;
	}

	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}

	return 1;
}

void funcao(int n) {
	int i, j, num;

	cont[n]=0;

	if (n>1) {
		funcao(n-1);

		for (i=0; i<cont[n-1]; i++) {
			for (j=1; j<=9; j+=2) {
				num=primos[n-1][i]*10+j;
				if (eh_primo(num)) {
					primos[n][cont[n]++]=num;
				}
			}
		}
	} else {
		primos[1][0]=2;
		primos[1][1]=3;
		primos[1][2]=5;
		primos[1][3]=7;
		cont[1]=4;
	}
}

int main() {
	int n, i;

	FILE *in=fopen("sprime.in", "r");
	FILE *out=fopen("sprime.out", "w");
	fscanf(in, "%d", &n);
	fclose(in);

	funcao(n);

	for (i=0; i<cont[n]; i++) {
		fprintf(out, "%d\n", primos[n][i]);
	}
	fclose(out);

	return 0;
}

//LCS - Longest Common Subsequence
//Programação Dinâmica - MSC - Maior Subcadeia Comum

#include <stdio.h>
#define SMAX 1001
#define DIAGONAL 1
#define LADO 2
#define CIMA 3


//n = tamanho de x
//m = tamanho de y

int c[SMAX][SMAX], b[SMAX][SMAX], n, m;
char x[SMAX], y[SMAX];

int lcs_recupera(int i, int j) {
	if (i==0||j==0) {
		return 0;
	}
	if (b[i][j]==DIAGONAL) {
		lcs_recupera(i-1, j-1);
		printf("%c", x[i]);
	} else if (b[i][j]==CIMA) {
		lcs_recupera(i-1, j);
	} else {
		lcs_recupera(i, j-1);
	}
}

int main() {
	int i, j;


	printf("LCS - Longest Common Subsequence\nPor Tiago Madeira\n\n");
	printf("Digite o tamanho da string X: ");
	scanf("%d", &m);
	printf("Digite o tamanho da string Y: ");
	scanf("%d", &n);

	scanf("%*c");
	printf("Digite a string X: ");
	for (i=1; i<=m; i++) {
		scanf("%c", &x[i]);
		c[i][0]=0;
	}
	scanf("%*c");
	printf("Digite a string Y: ");
	for (i=1; i<=n; i++) {
		scanf("%c", &y[i]);
		c[0][i]=0;
	}

	printf("\nPrograma raciocinando...\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			if (x[i]==y[j]) {
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=DIAGONAL;
			} else {
				if (c[i][j-1]>c[i-1][j]) {
					c[i][j]=c[i][j-1];
					b[i][j]=LADO;
				} else {
					c[i][j]=c[i-1][j];
					b[i][j]=CIMA;
				}
			}
		}
	}

/*	printf("\nMATRIX C\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", c[i][j]);
		}
		printf("\n");
	}

	printf("\nMATRIX B\n");
	for (i=1; i<=m; i++) {
		for (j=1; j<=n; j++) {
			printf("%d ", b[i][j]);
		}
		printf("\n");
	}
*/

	lcs_recupera(m, n);
	printf("\n");
}

//Aplicar as fórmulas das PAs

//Progressão Aritmética
//Programa desenvolvido por Tiago Madeira (c) 2005.

#include <stdio.h>
#define MAX 1000001

long double a[MAX], s[MAX];

int main() {
	long double r;
	int n;

	printf("Primeiro termo da PA: ");
	scanf("%Lf", &a[1]);
	printf("Razão da PA: ");
	scanf("%Lf", &r);

	//Eu podia fazer só pros que vão ser usados, mas não sei porquê, deu vontade de fazer assim... =)
	printf("\nAguarde o problema raciocinar tudo que ele tem para raciocinar...\n");
	for (n=2; n<MAX; n++) {
		a[n]=a[1]+r*(n-1);
		s[n]=(a[1]+a[n])*n/2;
	}

	printf("\nE agora, digite números para o programa dizer A e S dele.\n");
	do {
		printf("Número: ");
		scanf("%d", &n);
		if (!n) {
			break;
		}
		printf("Número na posição N = %.Lf\nSoma de 1 a N = %.Lf\n\n", a[n], s[n]);
	} while (n);

}

//Prime Palindromes - USACO Training Gateway
//Tiago Madeira (c)

//Agora eu sei que dá pra fazer com custo bem menor,
//mas esse aí rolou na boa com 0.05 segundos.

/*
ID: contato1
PROG: pprime
LANG: C
*/

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

int eh_primo(long int num) {
	int i;

	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}

	return 1;
}

int main() {
	int i, j, k, l, cont=0;
	long int numero, min, max, v[10000];

	FILE *in=fopen("pprime.in", "r");
	FILE *out=fopen("pprime.out", "w");
	fscanf(in, "%d %d", &min, &max);
	fclose(in);

	v[cont++]=5;
	v[cont++]=7;
	for (i=1; i<=9; i+=2) {
		numero=i*10+i;
		if (eh_primo(numero)) {
			v[cont++]=numero;
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			numero=i*100+j*10+i;
			if (eh_primo(numero)) {
				v[cont++]=numero;
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				numero=i*10000+j*1000+k*100+j*10+i;
				if (eh_primo(numero)) {
					v[cont++]=numero;
				}
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		if (i==5) {
			i=7;
		}
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				for (l=0; l<=9; l++) {
					numero=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i;
					if (eh_primo(numero)) {
						v[cont++]=numero;
					}
				}
			}
		}
	}
	for (i=0; i<cont; i++) {
		if (v[i]>=min&&v[i]<=max) {
			fprintf(out, "%d\n", v[i]);
		} else if (v[i]>max) {
			fclose(out);
			return 0;
		}
	}
	fclose(out);
	return 0;
}

//Bafo - OBI2005
#include <stdio.h>

int main() {
	int n, j1, j2, t1=0, t2=0, i, teste=1;

	while (scanf("%d", &n)&&n) {
		printf("Teste %d\n", teste++);
		t1=0;
		t2=0;
		for (i=1; i<=n; i++) {
			scanf("%d %d", &j1, &j2);
			t1+=j1;
			t2+=j2;
		}
		if (t1>t2) {
			printf("Aldo");
		} else {
			printf("Beto");
		}
		printf("\n\n");
	}
	return 0;
}

//Transmissão de Energia - OBI2005
#include <stdio.h>
#define NMAX 101

int g[NMAX][NMAX], achou[NMAX], n, achados;

void acha(int x) {
	int i;

	achou[x]=1;
	achados++;
	for (i=1; i<=n; i++) {
		if (g[x][i]&&!achou[i]) {
			g[x][i]=0;
			g[i][x]=0;
			acha(i);
		}
	}
}

int main() {
	int e, i, j, x, y, teste=1;

	while (scanf("%d %d", &n, &e)&&n) {
		achados=0;
		for (i=1; i<=n; i++) {
			achou[i]=0;
			for (j=1; j<=n; j++) {
				g[i][j]=0;
			}
		}

		for (i=1; i<=e; i++) {
			scanf("%d %d", &x, &y);
			g[x][y]=1;
			g[y][x]=1;
		}

		acha(1);

		printf("Teste %d\n", teste++);
		if (achados==n) {
			printf("normal");
		} else {
			printf("falha");
		}
		printf("\n\n");
	}

	return 0;
}

//Vivo ou Morto - OBI2005
#include <stdio.h>
//Não sei qual o número máximo de jogadores!
#define NMAX 101

int main() {
	int jogador[NMAX], njogadores, nrodadas, i, j, k, vivos, ordem, fez;

	scanf("%d %d", &njogadores, &nrodadas);
	for (i=1; i<=njogadores; i++) {
		scanf("%d", &jogador[i]);
	}
	for (i=1; i<=nrodadas; i++) {
		scanf("%d %d", &vivos, &ordem);
		for (j=1; j<=vivos; j++) {
			scanf("%d", &fez);
			if (fez!=ordem) {
				jogador[j]=0;
			}
		}
		for (j=1; j<=vivos; j++) {
			if (!jogador[j]) {
				for (k=j; k<vivos; k++) {
					jogador[k]=jogador[k+1];
				}
			}
		}
	}
	printf("%d\n", jogador[1]);
}

//Mini-poker - OBI2005
#include <stdio.h>

int pontuacao(int c[]) {
	//Regra I
	if (c[1]==c[2]-1&&c[2]==c[3]-1&&c[3]==c[4]-1&&c[4]==c[5]-1) {
		return 200+c[1];
	}

	//Regra II
	if (c[1]==c[4]||c[2]==c[5]) {
		return 180+c[2];
	}

	//Regra III
	if ((c[1]==c[3]&&c[4]==c[5])||(c[3]==c[5]&&c[1]==c[2])) {
		return 160+c[3];
	}

	//Regra IV
	if (c[1]==c[3]||c[2]==c[4]||c[3]==c[5]) {
		return 140+c[3];
	}

	//Regra V
	if ((c[1]==c[2]&&c[4]==c[5])) {
		if (c[1]>c[4]) {
			return 3*c[1]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[1]+20;
		}
	}
	if ((c[1]==c[2]&&c[3]==c[4])) {
		if (c[1]>c[3]) {
			return 3*c[1]+2*c[3]+20;
		} else {
			return 3*c[3]+2*c[1]+20;
		}
	}
	if ((c[2]==c[3]&&c[4]==c[5])) {
		if (c[2]>c[4]) {
			return 3*c[2]+2*c[4]+20;
		} else {
			return 3*c[4]+2*c[2]+20;
		}
	}

	//Regra VI
	if (c[1]==c[2]||c[2]==c[3]) {
		return c[2];
	}
	if (c[3]==c[4]||c[4]==c[5]) {
		return c[4];
	}

	//Regra VII
	return 0;
}

int main() {
	int n, teste, c[6], carta, i, j;

	scanf("%d", &n);
	for (teste=1; teste<=n; teste++) {
		//Pega os valores e faz um Insertion Sort
		for (i=1; i<=5; i++) {
			scanf("%d", &carta);
			for (j=i-1; j>0&&c[j]>carta; j--) {
				c[j+1]=c[j];
			}
			c[j+1]=carta;
		}

		printf("Teste %d\n%d\n\n", teste, pontuacao(c));
	}

	return 0;
}

//Frota de Taxi - OBI2005
#include <stdio.h>

int main() {
	float a, g, ra, rg, al, ga;

	scanf("%f %f %f %f", &a, &g, &ra, &rg);
	al=a/ra;
	ga=g/rg;

	if (al<ga) {
		printf("A\n");
	} else {
		printf("G\n");
	}

	return 0;
}

//Campo de Minhocas - OBI2005
#include <stdio.h>
#define NMAX 102
#define NMAX 102

int main() {
	int n, m, soma, i, j, matriz[NMAX][NMAX], maior=0;

	scanf("%d %d", &n, &m);

	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			scanf("%d", &matriz[i][j]);
		}
	}

	for (i=1; i<=n; i++) {
		soma=0;
		for (j=1; j<=m; j++) {
			soma+=matriz[i][j];
		}
		if (soma>maior) {
			maior=soma;
		}
	}

	for (i=1; i<=m; i++) {
		soma=0;
		for (j=1; j<=n; j++) {
			soma+=matriz[j][i];
		}
		if (soma>maior) {
			maior=soma;
		}
	}

	printf("%d\n", maior);

	return 0;
}

//Duende Perdido - OBI2005
#include <stdio.h>
#include <values.h>
#define NMAX 102

int menor=MAXINT, p[NMAX][NMAX], custo[NMAX][NMAX];

int duende(int x, int y, int cus, int ox, int oy) {

	if (p[x][y]==1||p[x][y]==3) {
		if (cus<custo[x][y]) {
			custo[x][y]=cus;
			if ((x!=ox||y+1!=oy)&&p[x][y+1]!=-1) {
				duende(x, y+1, cus+1, x, y);
			}
			if ((x+1!=ox||y!=oy)&&p[x+1][y]!=-1) {
				duende(x+1, y, cus+1, x, y);
			}
			if ((x!=ox||y-1!=oy)&&p[x][y-1]!=-1) {
				duende(x, y-1, cus+1, x, y);
			}
			if ((x-1!=ox||y!=oy)&&p[x-1][y]!=-1) {
				duende(x-1, y, cus+1, x, y);
			}
		}
	}
	if (p[x][y]==0) {
		if (cus<custo[x][y]) {
			custo[x][y]=cus;
		}
		if (custo[x][y]<menor) {
			menor=custo[x][y];
		}
	}
}

int main() {
	int n, m, ix, iy, i, j;

	scanf("%d %d", &n, &m);

	for (i=0; i<=n+1; i++) {
		for (j=0; j<=m+1; j++) {
			p[i][j]=-1;
			custo[i][j]=MAXINT;
		}
	}

	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			scanf("%d", &p[i][j]);
			if (p[i][j]==3) {
				ix=i;
				iy=j;
			}
		}
	}

	duende(ix, iy, 0, 0, 0);

	printf("%d\n", menor);

	return 0;
}

//Trilhas - OBI2005
#include <stdio.h>
#include <values.h>
#define NMAX 102
#define MMAX 1001

int main() {
	int campeao, n, m[NMAX], a[NMAX][MMAX], saida=0, i, j, parou, subir[NMAX], descer[NMAX], menor=MAXINT;

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

	//Primeiro vamos ver se precisa haver esforço de subida
	for (i=1; i<=n; i++) {
		parou=0;
		for (j=1; j<=m[i]; j++) {
			//printf("%d %d\n", i, j);
			if (a[i][j]>a[i][j+1]&&j!=m[i]) {
				parou=1;
				//printf("parou!\n");
				j=m[i];
			}
		}
		if (!parou) {
			//Então vamos parar por aí...
			printf("%d\n", i);
			return 0;
		}
	}

	//A mesma coisa ao contrário
	for (i=1; i<=n; i++) {
		parou=0;
		for (j=m[i]; j>=1; j--) {
			//printf("%d %d\n", i, j);
			if (a[i][j]>a[i][j-1]&&j!=1) {
				parou=1;
				//printf("parou!\n");
				j=1;
			}
		}
		if (!parou) {
			//Então vamos parar por aí...
			printf("%d\n", i);
			return 0;
		}
	}

	//Não deu...
	//Vamos contar quantos metros vamos ter que subir (ou descer=subir ao contrário)
	for (i=1; i<=n; i++) {
		descer[i]=0;
		subir[i]=0;
		for (j=1; j<=m[i]; j++) {
			if (a[i][j]>a[i][j+1]) {
				descer[i]+=(a[i][j]-a[i][j+1]);
			} else {
				subir[i]+=(a[i][j+1]-a[i][j]);
			}
		}
	}

	//E quem sobe ou desce menos?
	for (i=1; i<=n; i++) {
		if (subir[i]<menor) {
			menor=subir[i];
		}
		if (descer[i]<menor) {
			menor=descer[i];
		}
	}

	//Mas peraí... Temos que ver o primeiro na ordem de identificação!
	for (i=1; i<=n; i++) {
		if (subir[i]==menor||descer[i]==menor) {
			printf("%d\n", i);
			return 0;
		}
	}

	return 0;
}