Solução de Roger Benet, comentários de Rogério Júnior
Clique aqui para ver o problema original.
Vamos criar uma $$struct$$ de nome $$piloto$$ para representarmos cada um dos pilotos.Ela guardará dois inteiros: $$pontos$$ e $$id$$ que deverão representar quantos pontos o piloto fez em um determinado sistema e seu número de identificação, respectivamente. Além disso, ela também guardará um vetor de $$100$$ inteiros de nome $$pos$$, que guardará, na posição $$i$$, quantas vezes o piloto foi o $$i$$-ésimo colocado.
Agora, vamos declarar um vetor de $$piloto$$ de nome $$vet$$, onde $$vet[i]$$ representa o piloto de identificação $$i$$. Primeiramente, percorreremos este vetor, atribuindo o valor correto de identificação ao elemento $$id$$ de cada posição e zerando os valores de $$pontos$$ e $$pos$$.
Para cada corrida, se o piloto $$j$$ ficou na posição $$x$$, aumentaremos o valor de $$vet[j].pos[x]$$ em uma unidade. Agora, para cada sistema de pontuação, atribuiremos o número de pontos feito pelo piloto $$i$$ ao elemento $$pontos$$ da posição $$i$$ de $$vet$$, da seguinte forma: para cada posição $$i$$ que dá pontos a um piloto, veremos quantos pontos ela ganha no sistema em que estamos olhando, chamaremos esse valor de $$x$$ e, para cada piloto $$j$$, adicionaremos a seus pontos (salvos no elemento $$pontos$$ de $$vet[j]$$) a quantidade de vezes que ele ficou na posição $$i$$ (salva no elemento $$pos[i]$$ de $$vet[j]$$) multiplicada pelos $$x$$ pontos que essa posição dá.
Após atribuirmos a posição correta para cada piloto, basta ordenarmos o vetor $$vet$$ usando uma função que ordene pela maior quantidade de pontos, usando o menor índice como critério de desempate. Feito isso, imprimimos o identificador do piloto na primeira posição do vetor ordenado ($$vet[1].id$$, se indexarmos de $$1$$ a $$p$$) e de todos os outros, a partir da segunda posição, que têm pontuação igual à do primeiro, sempre com um espaço em branco antes do número. Feito isso, basta imprimir uma quebra de linha, zerarmos as pontuações de todos os pilotos e analisarmos o próximo sistema de pontuações. Segue o código comentado para melhor entendimento:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> // scanf e printf | |
| #include <algorithm> // sort | |
| #include <cstring> // memset | |
| using namespace std; | |
| // struct que representa um piloto | |
| struct piloto { | |
| int pontos, id, pos[110]; | |
| }; | |
| // função que compara pilotos | |
| bool cmp (piloto a, piloto b){ | |
| // ela dá prioridade à maior pontuação | |
| if(a.pontos > b.pontos) return true; | |
| if(a.pontos < b.pontos) return false; | |
| // e usa o menor valor de id como desempate | |
| return a.id < b.id; | |
| } | |
| // declaro as variáveis que vou usar | |
| int g, p, s, k; | |
| piloto vet[110]; | |
| int main(){ | |
| // para cada caso dado na entrada | |
| while(scanf("%d %d", &g, &p) and g != 0){ | |
| // para cada piloto | |
| for(int i = 1; i <= p; i++){ | |
| // atribuo o valor inicial correto a cada elemento seu | |
| vet[i].id = i; | |
| vet[i].pontos = 0; | |
| memset(vet[i].pos, 0, sizeof vet[i].pos); | |
| } | |
| // para cada GP | |
| for(int i = 0; i < g; i++) | |
| // olho a posição de cada piloto | |
| for(int j = 1; j <= p; j++){ | |
| // salvo-a em x | |
| int x; | |
| scanf("%d", &x); | |
| // e aumento, em vet[j], o número de vezes | |
| // que o piloto j chegou na posição x | |
| vet[j].pos[x]++; | |
| } | |
| // leio o número de sistemas de pontuação | |
| scanf("%d", &s); | |
| // e analiso cada sistema | |
| while(s–){ | |
| // leio quantas posições valem pontos | |
| scanf("%d", &k); | |
| // e para cada posição i que vale ponto | |
| for(int i = 1; i <= k; i++){ | |
| // salvo em x quantos ponto ela vale | |
| int x; | |
| scanf("%d", &x); | |
| // e adiciono no elemento pontos de cada piloto | |
| // os pontos que ele ganhou por cada vez que chegou na posição i | |
| for(int j = 1; j <= p; j++) vet[j].pontos += vet[j].pos[i] * x; | |
| } | |
| // ordeno o vetor de pilotos | |
| sort(vet+1, vet+1+p, cmp); | |
| // imprimo o id do primeiro piloto | |
| printf("%d",vet[1].id); | |
| // e de todos os seguintes que têm a mesa pontuação do primeiro | |
| int x = 2; | |
| while(vet[x].pontos == vet[1].pontos){ | |
| printf(" %d",vet[x].id); | |
| x++; | |
| } | |
| // imprimo a quebra de linha | |
| printf("\n"); | |
| // e zero os pontos de cada piloto | |
| // para analisar o próximo sistema | |
| for(int i = 1; i <= p; i++) vet[i].pontos = 0; | |
| } | |
| } | |
| return 0; | |
| } |
Comente