URI (BEECROWD) - 2951 - O Retorno do Rei - Iniciante - C e C++

Buenas! Nesse post trazemos a solução do problema O retorno do Rei, disponível na plataforma URI (BEECROWD). Esse exercício foi bem fácil de resolver! Achei que daria mais trabalho pelo número de jogadores que o resolveram, mas pode ser porque ele é novo na plataforma. Resolvi ele em duas linguagens, aplicando mais ou menos a mesma lógica. As explicações estão abaixo. Espero que consigam compreender!

Antes de resolver qualquer algoritmo do URI (BEECROWD agora), recomendamos seguir os seguintes passos:

1. Ler todo enunciado do problema.
2. Ler os tópicos do fórum em caso de dúvidas
3. Preparar arquivos de entrada para teste, considerando as entradas de exemplo do URI, do udebug e outros valores limite;
4. Preparar o ambiente de desenvolvimento e utilizar os mesmos parâmetros dos compiladores do URI
5. Preparar um código-fonte padrão, já contendo a chamada às bibliotecas padrão, pré-processadores, retorno de função e um comando de escrita com "\n", pois no URI a grande maioria dos problemas exige a quebra de linha final.

Plataforma: URI (BEECROWD)

Problema: 2951

Enunciado:

Frodo e Sam estão prestes a conseguir jogar o anel na Montanha da Perdição, porém Gollum os atrapalha.

Uma pequena pausa na história. Senhor dos Anéis, além de ser um dos maiores clássicos literários e cinematográficos da humanidade, é uma história que deixa evidente o valor da amizade. Dê valor às boas amizades :) Despause.

Gollum é um ser infeliz e que não suporta a amizade. Para que Frodo e Sam consigam passar por ele, eles precisam recitar runas que entoam amizade. Cada runa é representada por uma letra do alfabeto, e indica uma quantidade de amizade que ela emite, podendo ser positiva ou negativa (sim, existem as runas que representam as más amizades). 

Dada a quantidade de amizade necessária para derrotar Gollum, uma lista de runas e seus respectivos valores de amizade e as runas que Sam e Frodo recitaram, dê o valor final de amizade que Frodo e Sam conseguiram e se foi possível ou não derrotar Gollum.

Linguagens: C e C++

Solução em C:

A solução utilizada faz uma espécie de mapeamento de dicionário em um array de 26 posições, onde cada letra (Ri) pode ser usada como índice para ser associada a um valor (Vi). Nesse caso, aproveita-se que o enunciado restringe a letra às letras maiúsculas, o que significa que a letra A será a primeira posição do array. Como o array sempre começa no índice zero e A é representado pelo número 65 na tabela ASCII, sempre utilizaremos Ri - 65 para calcular o índice correto. Sabendo isso, basta acumular os valores dos índices respectivos na variável acum e realizar os testes para ver se o valor é maior ou igual a g, caso em que Gollum é derrotado.

Código em C:

#include <stdio.h>

#define ALPHABET_SIZE 26

#define START_ALPHABET 65

int main() {

    

    short int n;

    short int g;

    short int runaValues[ALPHABET_SIZE];

    short int runaQuant;

    int acum = 0;

    char ri;

    char runaRecited;

    

    scanf("%hd %hd ", &n, &g);

    

    while (n-- > 0) {

        scanf("%c ", &ri);

        scanf("%hd ", &runaValues[ri - START_ALPHABET]);

    }

    

    scanf("%hd ", &runaQuant);

    while (runaQuant-- > 0) {

        scanf("%c ", &runaRecited);

        acum += runaValues[runaRecited - START_ALPHABET];

    }

    

    printf("%d\n", acum);

    if (acum >= g)

        printf("You shall pass!\n");

    else

        printf("My precioooous\n");

    return 0;

}

Solução em C++:

A solução utilizada é semelhante a de C, mas com a diferença de fazer o mapeamento char - short int utilizando a estrutura map. Com isso não é necessário fazer o controle do índice (o map já cuida disso), mas é necessário criar os pares no mapa utilizando make_pair. O restante da solução segue a mesma lógica aplicada na solução em C.

Código em C++:

#include <iostream>

#include <map>

using namespace std;

int main() {

    

    short int n;

    short int g;

    short int vi;

    short int runaQuant;

    int acum = 0;

    char ri;

    char runaRecited;

    map<char, short int> runaValues;

    

    cin >> n >> g;

    

    while (n-- > 0) {

        cin >> ri >> vi;

        runaValues.insert(make_pair(ri, vi));

    }

    

    cin >> runaQuant;

    while (runaQuant-- > 0) {

        cin >> runaRecited;

        acum += runaValues[runaRecited];

    }

    

    cout << acum << endl;

    if (acum >= g)

        cout << "You shall pass!" << endl;

    else

        cout << "My precioooous" << endl;

    return 0;

}