URI (BEECROWD) - 2381 - Lista de Chamada - Ad-Hoc - C e C++

Plataforma: URI (BEECROWD)

Problema: 2381

Enunciado:

Tia Joana é uma respeitada professora e tem vários alunos. Em sua última aula, ela prometeu que iria sortear um aluno para ganhar um bônus especial na nota final: ela colocou N pedaços de papel numerados de 1 a N em um saquinho e sorteou um determinado número K; o aluno premiado foi o K-ésimo aluno na lista de chamada.

O problema é que a Tia Joana esqueceu o diário de classe, então ela não tem como saber qual número corresponde a qual aluno. Ela sabe os nomes de todos os alunos, e que os números deles, de 1 até N, são atribuídos de acordo com a ordem alfabética, mas os alunos dela estão muito ansiosos e querem logo saber quem foi o vencedor.

Dado os nomes dos alunos da Tia Joana e o número sorteado, determine o nome do aluno que deve receber o bônus.

Linguagens: C e C++

Solução:

Basicamente era necessário ordenar os nomes dos alunos. Para isso, usa-se alguma função de ordenação.

Código em C:

Criei uma struct chamada Aluno, e a ordenação eu fiz com o strcmp, comparando os nomes dois a dois. Esta comparação foi feita na função de comparação (compara), que foi utilizada como parâmetro pelo algoritmo de ordenação QuickSort (qsort). Ao final da ordenação, imprime-se o nome da posição k-1.

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

typedef struct { 
    char nome[21];
} Aluno;

int compara(const void *a, const void *b) {
	Aluno *i = (Aluno *)a, *j = (Aluno *)b;
	
	return strcmp(i->nome, j->nome);
}

int main(){
		
	Aluno nomes[100];
	int n, k, i;
	
	scanf("%d %d ", &n, &k);
	
	for(i = 0; i < n; i++)
		scanf("%s", nomes[i].nome);
	
	qsort(nomes, n, sizeof(Aluno), compara);
	
	printf("%s\n", nomes[k-1].nome);
	
	return 0;
}

Código em C++:

Em C++ a solução pode ficar mais simples, pois basta chamar a função sort. No fim, imprime-se o nome da posição k-1.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    
    int n, k, i, tamanho;
    cin >> n >> k;
    
    string nomes[n];
    for (i = 0; i < n; i++)
        cin >> nomes[i];
    
    tamanho = sizeof(nomes)/sizeof(nomes[0]); 
    sort(nomes, nomes+tamanho);
    
    cout << nomes[k-1] << endl;

    return 0;
}