URI (BEECROWD) - 2845 - Festa no Polo Norte - Iniciante - C e C++

E aí? Conseguiram resolver esse? Vejam a solução postada no blog. Ficou igual a sua? Comenta aí pra nós!

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: 2845

Enunciado:

Giovana ficou muito feliz por conseguir mandar sua carta para o papai Noel e receber ótimos presentes. A alegria foi tanta que ela resolveu até convidar todos os duendes do bom velhinho para sua festa de aniversário, que é pouco depois do Natal, em Janeiro. Porém, ela não quer que o Grinch apareça na sua festinha para estragar tudo, então ela bolou um plano.

Para esconder do malvado Grinch onde será a festa, ela resolveu ultilizar o sistema de reuniões dos Duendes, que funciona assim: cada duende tem um identificador numérico único e, quando haverá uma reunião, é escolhida a casa de um dos duendes para sediar o encontro. Mas ao invés de escrever o número do duende anfitrião no mural da fábrica do Papai Noel, onde todos podem ver, é escrito o identificador de exatamente todos os duendes com números menores que o dele e que são coprimos ao dele. Esse método é também uma forma de dizer que esses duendes do mural devem levar as comidas e bebidas para a reunião.

Como o Grinch é tão ruim com números a ponto de nem saber que dois números só são chamados de coprimos se o MDC (máximo divisor comum) entre eles é 1, Giovana simplesmente envia uma carta para o polo norte com os números dos duendes que devem levar as comidas, e com isso, os duendes já conseguem descobrir onde será a festa de aniversário, mas o Grinch não.

Dada a carta que os duendes receberam, determine na casa de qual Duende será a festa de aniversário de Giovana.

Linguagens: C e C++

Soluções em C e C++:

A lógica das duas soluções apresentadas é a mesma. É necessário saber quem é o maior número e somar 1, assim sabemos a partir de qual duende devemos testar. Sabendo isso, verificamos o MDC entre o duende atual (iniciando em maior+1 e crescendo até que se satisfaça a condição) e todos os duendes informados. É necessário que o MDC entre este duende e todos os duendes informados seja 1. Se for, foi encontrado o duende no qual o evento será realizado.

Em C:

#include <stdio.h>

int mdc(int num1, int num2) {

    int resto;

    do {
        resto = num1 % num2;
        num1 = num2;
        num2 = resto;
    } while (resto);

    return num1;
}

int main() {
    
    int n, i, proximo = 1, j, k, c = 0;
    scanf("%d", &n);
    int duendes[n];
    
    for (i = 0; i < n; i++) {
        scanf("%d", &duendes[i]);
        if (duendes[i] >= proximo)
            proximo = duendes[i] + 1;
    }
    
    int achou = 0;
    for (j = proximo; !achou; j++) {
        for (k = 0; k < n; k++) {
            if (mdc(j, duendes[k]))
                continue;
        }
        if (k == n)
            achou = 1;
    }
    
    printf("%d\n", proximo);
    
    return 0;
}

Em C++:

#include <iostream>

using namespace std;

int mdc(int num1, int num2) {

    int resto;

    do {
        resto = num1 % num2;
        num1 = num2;
        num2 = resto;
    } while (resto);

    return num1;
}

int main() {
    
    int n, i, proximo = 1, j, k, c = 0;
    cin >> n;
    int duendes[n];
    
    for (i = 0; i < n; i++) {
        cin >> duendes[i];
        if (duendes[i] >= proximo)
            proximo = duendes[i] + 1;
    }
    
    bool achou = false;
    for (j = proximo; !achou; j++) {
        for (k = 0; k < n; k++) {
            if (mdc(j, duendes[k]))
                continue;
        }
        if (k == n)
            achou = true;
    }
    
    cout << proximo << endl;
    
    return 0;
}