1533 - Detetive Watson
A constatação de que esse problema é uma versão menos geral do problema 2381 - Lista de Chamada é elementar, meu caro Sherlock...
Descrição
Solução
Vide 2381 - Lista de Chamada para conferir o raciocínio usado para resolver esse problema. Único detalhe é que é importante guardar o índice original de cada elemento, então ordenar pares de números em vez de ordenar o vetor como está é o caminho. O problema é que você vai precisar usar funções customizadas de ordenação, mas é bom para treinar isso também.
Na linguagem C, eu usei um artifício para guardar o número e o respectivo índice original no mesmo número de forma a não afetar a ordenação, baseado no princípio de que todos os números estão sendo multiplicados pelo mesmo valor e sendo somados sempre por valores menores que 1000. Essa tática pode ser utilizada em qualquer linguagem, mas as outras já possuem artifícios melhores e mais legíveis para se lidar com a ordenação.
#include <stdlib.h>
#include <stdio.h>
int comp(const void *a, const void *b){
return *((int*)b) - *((int*)a);
}
int main(void) {
int N;
int suspeitos[1000];
while(scanf("%d", &N)){
if(!N) break;
for(int i = 0; i < N; ++i){
scanf("%d", &suspeitos[i]);
suspeitos[i] = (suspeitos[i] * 1000) + i;
}
qsort(suspeitos, N, sizeof(int), comp);
printf("%d\n", (suspeitos[1] % 1000) + 1);
}
return 0;
}
Last updated
Was this helpful?