Solução OBI 2016

falta.cpp

// Ivan Carvalho
// Falta uma - Fase 2 Programação Nível 2 - OBI 2016
// O(n!)
#include <bits/stdc++.h>
int matriz[10][10];
int main(){
	int n,total,subtotal=1;
	scanf("%d",&n);
	// calculamos (n-1)!
	for(int i=1;i<n;i++) subtotal *= i;
	// calculamos n!
	total = subtotal * n;
	// recebemos as n! - 1 linhas
	for(int i=1;i<total;i++){
		// para cada número na linha
		// aumento sua presença no indice j em 1
		for(int j=1;j<=n;j++){
			int x;
			scanf("%d",&x);
			matriz[j][x]++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			// se o número não aparece (n-1)! vezes
			// no índice, entao ele está faltando
			if (matriz[i][j]!=subtotal){
				printf("%d ",j);
				break;
			}
		}
	}
	printf("\n");
	return 0;
}