Solucion a 110108 Australian Voting [http://wwwprogramming-challenges.com]

Solucion a 110108 Australian Voting [http://wwwprogramming-challenges.com]
El enunciado esta en el siguiente link enunciado

/* * 110108 - Votacion australiana [http://www.programming-challenges.com] * Main.cpp * Created on: 13/11/2011 * Author: BreakDark * version 7.1,1 C++ beta basado en el algoritmo de Alexandre Martins */ // ACEPTADO!!! xD #include #include #include "Main.h" using namespace std; short numCandidatos; char candidatos[20][80]; int numVotos; short votacion[1000][20]; int n; // variable temporal /** * proceso que hace todo el trabajo */ void procesar() { short indice_de_los_primeros[numVotos]; // para ubicarse en // el primer lugar int i, min; int votos[numCandidatos]; bool eliminados[numCandidatos]; /* candidatos eliminados */ bool ultimos_eliminados[numCandidatos]; double cincuentaPorCiento = (double) numVotos * 0.5; // para obtener el // 50% for (i = 0; i < numCandidatos; i++) // inicializamos eliminados eliminados[i] = false; for (i = 0; i < numVotos; i++) indice_de_los_primeros[i] = 0; while (true) { // inicializamos for (i = 0; i < numCandidatos; i++) { ultimos_eliminados[i] = false; votos[i] = 0; } /* verifica se alguien tiene mas que el 50% de los votos */ for (i = 0; i < numVotos; i++) votos[votacion[i][indice_de_los_primeros[i]] - 1]++; for (i = 0; i < numCandidatos; i++) if (votos[i] > cincuentaPorCiento) { cout << candidatos[i] << endl; return; } /* identificando candidatos empatados con o menor numero de votos */ min = 99999; for (i = 0; i < numCandidatos; i++) if (votos[i] < min && !eliminados[i]) min = votos[i]; for (i = 0; i < numCandidatos; i++) { if (votos[i] == min && !eliminados[i]) { eliminados[i] = true; ultimos_eliminados[i] = true; } } /* excluyendo candidatos eliminados de las celdas de votacion */ for (i = 0; i < numVotos; i++) while (eliminados[votacion[i][indice_de_los_primeros[i]] - 1]) { indice_de_los_primeros[i]++; // si se removio a todos los candidatos if (indice_de_los_primeros[i] >= numCandidatos) { for (short j = 0; j < numCandidatos; j++) { if (ultimos_eliminados[j]) cout << candidatos[j] << endl; } return; } } } } /** Funcion Principal */ int main() { long numCasos; // para el numero de casos de prueba int i; // para los bubles char linea[256], *p; // para poder procesar una linea, y un puntero short votos[20]; // AQUI INICIA EL PROGRAMA gets(linea); sscanf(linea, "%ld", &numCasos); gets(linea); // linea en blanco while (numCasos--) { gets(linea); sscanf(linea, "%d", &numCandidatos); // leemos la lista de candidatos for (i = 0; i < numCandidatos; i++) gets(candidatos[i]); // leemos los votos numVotos = 0; while (gets(linea) && linea[0] != '\0') { for (i = 0, p = linea; sscanf(p, "%d%n", &votacion[numVotos][i++], &n) > 0; p += n) ; numVotos++; } procesar(); // para separar las respuestas por una linea en blanco if (numCasos > 0) cout << endl; } return 0; }