URI (BEECROWD) - 1022 - TDA Rational (TDA Racional) - Estruturas e Bibliotecas - Haskell

Fala, pessoal!

Nesse post resolvo um problema da categoria "Estruturas e Bibliotecas". Esses problemas costumam ser um pouco mais difíceis em relação aos da categoria Iniciante, e costumam envolver o uso de alguma estrutura de dados ou biblioteca diferente das padrão. Não é exatamente o caso para resolver ele em Haskell, já que conseguimos definir nossas funções e usar algumas outras que estão disponíveis no módulo padrão 😎

Abaixo você tem acesso a uma das possíveis soluções.

Ah, não esqueça de ajudar o blog!!!

Plataforma: URI (BEECROWD)

Problema: 1022

Enunciado:
In english:

You were invited to do a little job for your Mathematic teacher. The job is to read a Mathematic expression in format of two rational numbers (numerator / denominator) and present the result of the operation. Each operand or operator is separated by a blank space. The input sequence (each line) must respect the following format: number, (‘/’ char), number, operation char (‘/’, ‘*’, ‘+’, ‘-‘), number, (‘/’ char), number. The answer must be presented followed by ‘=’ operator and the simplified answer. If the answer can’t be simplified, it must be repeated after a ‘=’ operator. Considering N1 and D1 as numerator and denominator of the first fraction, follow the orientation about how to do each one of these 4 operations: Sum: (N1*D2 + N2*D1) / (D1*D2) Subtraction: (N1*D2 - N2*D1) / (D1*D2) Multiplication: (N1*N2) / (D1*D2) Division: (N1/D1) / (N2/D2), that means (N1*D2)/(N2*D1)

Linguagem: Haskell

Solução: 

A ideia do exercício é realizar os cálculos desejados pelo usuário, que resultarão em uma fração, e então exibir a fração também em formato simplificado. Para isso é necessário saber qual é o maior valor que pode dividir numerador e denominador, ou seja, o máximo divisor comum (mdc).

A estratégia utilizada foi criar várias funções para auxiliar a encontrar a resposta.

A função main apenas lê o valor de n e o passa como parâmetro para a função reading.

Na função reading as expressões são lidas linha a linha e então os números informados são extraídos e colocados em uma lista. Na linha, todas as "palavras" (expressões separadas por espaço) pares são números. Entre os números (palavras ímpares) estão os operadores, sendo que o único operador que importa neste exercício é o do meio, pois o primeiro e o último são sempre "/", garantindo que as entradas são frações.

Para pegar o n-ésimo elemento de uma lista, usa-se nome-lista!!n.

Criei duas funções, getNum e getDen para obter o numerador e o denominador a depender da operação realizada, seguindo as fórmulas do enunciado.

Após obter numerador e denominador, o primeiro valor pode ser impresso. Depois disso, para calcular o número simplificado, basta obter o mdc dos valores e dividir os números obtidos após o primeiro cálculo pelo mdc.

A única condição antes de exibir o valor simplificado é identificar se o numerador obtido no primeiro passo é zero. Isso deve ser feito porque zero no numerador com qualquer denominador (que só não pode ser zero) pode ser simplificado para 0/1.

Veja como ficou o código:

main :: IO ()
main = do
   n <- readLn :: IO Int
   reading n

mdc :: Int -> Int -> Int
mdc 0 _ = 0
mdc a b
   | a == b = a
   | a < b = mdc a (b-a)
   | otherwise = mdc b (a-b)

getNum :: String -> Int -> Int -> Int -> Int -> Int
getNum op n1 d1 n2 d2
   | op == "+" = n1 * d2 + n2 * d1
   | op == "-" = n1 * d2 - n2 * d1
   | op == "*" = n1 * n2
   | otherwise = n1 * d2

getDen :: String -> Int -> Int -> Int -> Int
getDen op n2 d1 d2
   | op == "/" = n2 * d1
   | otherwise = d1 * d2

reading :: Int -> IO ()
reading n = do
   if n == 0
      then return ()
      else do
         line <- getLine
         let list = words line
         let [n1, d1, n2, d2] = [read x | (x, i) <- zip list [0..], even i]
         let op = list!!3
         let numFinal = getNum op n1 d1 n2 d2
         let denFinal = getDen op n2 d1 d2
         if numFinal == 0
            then putStrLn ("0/" ++ show (denFinal) ++ " = 0/1")
            else do
               let divisor = mdc (abs numFinal) denFinal
               let numSim = div numFinal divisor
               let denSim = div denFinal divisor
               putStrLn (show (numFinal) ++ "/" ++ show (denFinal) ++ " = " ++ show (numSim) ++ "/" ++ show (denSim))
         reading (n-1)

URI (BEECROWD) - 1162 - Organizador de Vagões - Estruturas e Bibliotecas - C e C++

Opa! Tudo numa boa? Resolvendo agora aqui um exercício da categoria "Estruturas e Bibliotecas". Esses exercícios são um pouco mais complicados, mas deu pra resolver de boa. A solução foi baseada na implementação do Merge Sort, aí fluiu! Quem mais conseguiu resolver? Alguém fez diferente?

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

Enunciado:

Na estação de trem você ainda pode encontrar o último dos “organizadores de vagões”. Um Organizador de vagões um empregado cujo trabalho é apenas reordenar os vagões do trem, trocando-os de posição. Uma vez que os vagões são organizados em uma ordem considerada ótima, o condutor pode desconectar cada vagão e colocá-los na estação.

O título “organizador de vagões” é dado à pessoa que realiza esta tarefa, cuja estação fica perto de uma ponte. Ao invés da ponte poder subir ou descer, ela roda sobre um pilar que fica no centro do rio. Após rodar 90 graus, os barcos podem passar na esquerda ou direita dela. O Primeiro organizador de vagões descobriu que girando a ponte 180 graus com dois vagões em cima dela, é possível a troca de lugar entre os dois vagões. Obviamente a ponte pode operar no máximo com dois vagões sobre ela.

Agora que quase todos os organizadores de vagões já faleceram, a estação gostaria de automatizar esta operação. Parte do programa a ser desenvolvido é uma rotina que decide para um dado trem com um determinado número de vagões, o número de trocas entre trens adjacentes que são necessárias para que o  trem fique ordenado. Sua tarefa é criar tal rotina.

Linguagens: C e C++

Solução em C:

Para a ordenação dos vagões, nesta solução implementou-se o algoritmo merge sort.

Outro ponto importante é nunca esquecer da quebra de linha no fim do comando de escrita, o popular "\n".

#include <stdio.h>
int aux[50];
 
int merge(int v[], int left, int mid, int right) {
    int swaps = 0, i = left, j = mid, k = left;
    
    for (; i < mid && j <= right; k++) {
        if (v[i] > v[j]) {
            aux[k] = v[j++];
            swaps += mid - i;
        }
        else
            aux[k] = v[i++];
    }
    
    for (; i < mid; k++, i++)
        aux[k] = v[i];
    for (; j <= right; k++, j++)
        aux[k] = v[j];
    for (; left <= right; left++)
        v[left] = aux[left];
        
    return swaps;
}
 
int mergeInsertionSwap(int v[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2 + 1;
        return mergeInsertionSwap(v, left, mid - 1) + mergeInsertionSwap(v, mid, right) + merge(v, left, mid, right);
    }
    return 0;
}
 
int main() {
    int n, l, i;
    scanf("%d", &n);
    
    while (n--) {
        scanf("%d", &l);
        int vagoes[l];

        for (i = 0; i < l; i++)
            scanf("%d", &vagoes[i]);

        printf("Optimal train swapping takes %d swaps.\n", mergeInsertionSwap(vagoes, 0, l - 1));
    }
    
    return 0;
}

Solução em C++:

Para a ordenação dos vagões em C++ utilizou-se também o merge sort. A solução ficou muito parecida com a de C, mas utilizando comandos de entrada e saída da biblioteca iostream. Outro ponto de diferença é declarar variáveis locais no escopo de estrutura de seleção, o que compiladores C não costumam aceitar. Tirando isso é basicamente a mesma solução.

#include <iostream>
using namespace std;

int aux[50];
 
int merge(int v[], int left, int mid, int right) {
    int swaps = 0, i = left, j = mid, k = left;
    
    for (; i < mid && j <= right; k++) {
        if (v[i] > v[j]) {
            aux[k] = v[j++];
            swaps += mid - i;
        }
        else
            aux[k] = v[i++];
    }
    
    for (; i < mid; k++, i++)
        aux[k] = v[i];
    for (; j <= right; k++, j++)
        aux[k] = v[j];
    for (; left <= right; left++)
        v[left] = aux[left];
        
    return swaps;
}
 
int mergeInsertionSwap(int v[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2 + 1;
        return mergeInsertionSwap(v, left, mid - 1) + mergeInsertionSwap(v, mid, right) + merge(v, left, mid, right);
    }
    return 0;
}
 
int main() {
    int n, l;
    cin >> n;
    
    while (n--) {
        cin >> l;
        int vagoes[l];

        for (int i = 0; i < l; i++)
            cin >> vagoes[i];

        cout << "Optimal train swapping takes " << mergeInsertionSwap(vagoes, 0, l - 1) << " swaps." << endl;
    }
    
    return 0;
}

URI (BEECROWD) - 3176 - Time de Duendes - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 3176

Linguagens: C e C++

Enunciado:

No ano de 2020 o Papai Noel não poderá sair de casa para entregar presentes por conta da pandemia do Coronavirus. Então ele ordenou que seus duendes fossem entregar no lugar dele no dia do natal. Como eles são bastante inexperientes, irão se dividir em vários times compostos de três membros: Um líder, um entregador e um piloto de trenó. O plano do Papai Noel é que os líderes das equipes seja sempre os duendes mais velhos, por esse motivo ele pediu para todos escreverem seus nomes e idades em uma lista. Como você é um duende programador, resolveu ajudar o Papai Noel a organizar a lista e montar os times a partir dela.

Segue abaixo algumas regras e fatos:

- A lista deve ser organizada em ordem descendente de idade;

- Caso dois duendes possuírem a mesma idade, deve se organizar por ordem ascendente de nome;

- Não existe dois duendes de mesmo nome;

- Nenhum duende tem mais de 20 caracteres em seu nome;

- Os duendes da lista tem idade entre 10 e 100 anos;

- Os primeiros 1/3 dos duendes (os mais velhos), serão os líderes dos times;

- A ordem dos duendes entregadores e pilotos seguem a mesma lógica dos líderes. Ex) Se há 6 duendes na lista, haverá dois times, onde o duende mais velho é líder do time 1, e o segundo mais velho é líder do time 2. O terceiro mais velho é entregador do time 1 e o quarto mais velho é entregador do time 2. O quinto é piloto de trenó do time 1 e o último é piloto do time 2;

Solução:

Neste exercício, na solução em C, criei uma estrutura (struct) para os dados dos duendes, que são idade e nome. A ordenação foi feita com o qsort (Quick Sort), disponível na biblioteca stdlib. A comparação entre os doentes (função compara) foi feita pela idade primeiramente, e o desempate pelo nome, em ordem alfabética. A comparação entre idades é feita diretamente acessando a variável age de cada ponteiro comparado (a e b). A comparação entre os nomes foi feita com a função strcmp, disponível na biblioteca string. Acredito que essa era a parte mais difícil da solução. Outro ponto que merece destaque é que a leitura do nome do duende foi feito para o array de char "nome". Este valor foi copiado para a estrutura Duende criada (hue[indice].name) através da função strcpy, também disponível na biblioteca string.

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

typedef struct {
    int age;
    char name[22];
} Duende;

int compara(const void *a, const void *b) {
    Duende *a2 = (Duende *)a;
    Duende *b2 = (Duende *)b;    
    if (a2->age == b2-> age)
        return strcmp(a2->name, b2->name);
    return a2->age < b2->age;
}

int main() {
    int n, i, idade, times, k;
    char nome[22];
    Duende hue[30];
    scanf("%d ", &n);
    times = n/3;
    for (i = 0; i < n; i++) {
        scanf("%s %d", nome, &idade);
        strcpy(hue[i].name, nome);
        hue[i].age = idade;
    }
    qsort ((void *)&hue, n, sizeof(Duende), compara);
    for (i = 0; i < times; i++) {
        printf("Time %d\n", i + 1);
        for (k = i; k < n; k += times)
            printf("%s %d\n", hue[k].name, hue[k].age);
        printf("\n");
    }
    return 0;
}

A solução em C++ usa lógica semelhante, mas aqui não usei qsort, e sim sort, disponível na biblioteca algorithm. Também não foi necessário utilizar strcpy e strcmp, sendo possível fazer atribuição diretamente com o sinal de = e comparação diretamente com <=, o que facilita um pouco, pelo menos na minha opinião.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Duende {
    int age;
    string name;
};
bool compara(Duende a, Duende b) {
    if (a.age == b.age)
        return a.name <= b.name;
    return a.age > b.age;
}
int main() {
    int n, i, idade, times, k;
    string nome;
    Duende hue[30];
    cin >> n;
    times = n/3;
    cin.ignore();
    for (i = 0; i < n; i++) {
        cin >> nome >> idade;
        hue[i].name = nome;
        hue[i].age = idade;
    }
    sort(hue, hue + n, compara);
    for (i = 0; i < times; i++) {
        cout << "Time " << i + 1 << endl;
        for (k = i; k < n; k+=times) {
            cout << hue[k].name << " " << hue[k].age << endl;
        }
        cout << endl;
    }
    return 0;
}

URI (BEECROWD) - 2633 - Churras no Yuri - Estruturas e Bibliotecas - C e C++

Essas são as soluções em C e C++ para o exercício Churras no Yuri, do URI/BEECROWD! Espero que curtam!

Plataforma: URI (BEECROWD)

Problema: 2633

Enunciado:

Yuri é um bom companheiro. Sempre fazemos o churras dos “manos ;)” na casa dele! Desta vez, o motivo do churrasco é que os manos estão finalmente começando a passar em bons concursos! Então, hoje teremos aquela edição especial do churras, with alcohol and futebol de sabão!

A empresa do futebol de sabão está demorando para encher o campo e Yuri, já entendiado, começou a viajar na seguinte pergunta: se assássemos as carnes por ordem da data de validade, qual seria a sequência de peças de carne resultante? Como o MacBook de Yuri está muito longe (e a preguiça está muito perto), ele pediu a sua ajuda para responder esta pergunta.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct par {
    char s[22];
    int d;
};
int compara(const void *a, const void *b) {
    struct par *aa = (struct par *)a;
    struct par *bb = (struct par *)b;
    return aa->d - bb->d;
}
int main() { 
    int n, data, i;
    struct par p[10];
    char rango[22];
    while (scanf("%i ", &n) != EOF) { 
        for (i = 0; i < n; i++) {
            scanf("%s %i ", rango, &data);
            strcpy(p[i].s, rango);
            p[i].d = data;
        }
        qsort(p, n, sizeof(struct par), compara);
        for (i = 0; i < n; i++) {
            if (i)
                printf(" ");
            printf("%s", p[i].s);
        }
        
        printf("\n");
        memset(p, 0, n*sizeof(p[0]));
    }
    return 0; 
}

Código em C++:

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std; 

bool compara(pair<string, int>& a, pair<string, int>& b) {
    return a.second < b.second;
}
 
int main() { 
    
    int n;
    
    while (cin >> n) {
        
        map<string, int> linhas;
        vector<pair<string, int> > vet; 
        string rango;
        int data;
        
        while (n--) {
            cin >> rango >> data;
            linhas.insert({rango, data});
        }

        for (auto& it : linhas)
            vet.push_back(it); 
      
        sort(vet.begin(), vet.end(), compara); 
        
        for (auto& it : vet) {
            if (&it == &vet.front())
                cout << it.first;
            else
                cout << ' ' << it.first; 
        }
        
        cout << endl;
    }
    
    return 0; 
}

URI (BEECROWD) - 2482 - Etiquetas de Noel - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 2482

Enunciado:

Como de costume, neste ano Noel recebeu muitos pedidos de presentes. Só que em função de alguns imprevistos, não terá como entregar todos os presentes pessoalmente neste ano. Daí então decidiu utilizar o velho e bom correio tradicional, para alguns pedidos que podem ser entregues por carta.

Para esta tarefa, pediu ajuda ao elfo Evergreen Xadada, para que ele imprimisse etiquetas a todos os envelopes que serão destinados a algumas destas crianças, cujo pedido pode ser entregue por carta. Cada uma destas etiquetas deverá conter apenas o nome da criança e a saudação "Feliz Natal" no respectivo idioma desta criança. Para auxiliar nesta tarefa, Noel disponibilizou uma tabela com vários idiomas e o nome e o país de cada uma das crianças selecionadas, de acordo com o exemplo abaixo. Você deve ajudar Evergreen fazendo um programa que imprima estas etiquetas.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>
#include <string.h>
int main() {
    int n, m, i, pos;
    char a[200];
    char b[200];
    char felizNatal[200][200];
    char linguagem[200][200];
    scanf("%d ", &n);
    for (i = 0; i < n; i++) {
        scanf ("%[^\n]%*c", linguagem[i]);
        scanf ("%[^\n]%*c", felizNatal[i]);
    }
    scanf("%d ", &m);
    while (m--) {
        scanf ("%[^\n]%*c", a);
        scanf ("%[^\n]%*c", b);
        printf("%s\n", a);
        for (i = 0; i < n; i++) {
            if (!strcmp(b, linguagem[i])) {
                pos = i;
                break;
            }
        }
        printf("%s\n\n", felizNatal[pos]);
    }
    memset(felizNatal, 0, sizeof(felizNatal));
    memset(linguagem, 0, sizeof(linguagem));
    return 0;
}

Código em C++:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, i, pos;
    string a, b;
    vector<string> felizNatal, linguagem;
    cin >> n;
    cin.ignore();
    for (i = 0; i < n; i++) {
        getline(cin, a);
        linguagem.push_back(a);
        getline(cin, b);
        felizNatal.push_back(b);
    }
    cin >> m;
    cin.ignore();
    while (m--) {
        getline(cin, a);
        getline(cin, b);
        cout << a << endl;
        for (i = 0; i < n; i++) {
            if (!b.compare(linguagem.at(i))) {
                pos = i;
                break;
            }
        }
        cout << felizNatal.at(pos) << endl << endl;
    }
    felizNatal.clear();
    linguagem.clear();
    return 0;
}

URI (BEECROWD) - 2290 - Números Apaixornados - Estruturas e Bibliotecas - C e C++

Plataforma: URI (BEECROWD)

Problema: 2290

Enunciado:

Será dado a você um vetor com N números, onde todos estarão em pares. Porém somente dois desses números acabaram ficando sem par, esses números são ditos números apaixornados, você consegue identificar quais são esses números?

Por exemplo, A = {1, 1, 3, 3, 5, 5, 5, 7}, os números apaixornados são 5 e 7.

Linguagens: C e C++

Solução:

Código em C:

#include <stdio.h>

void merge(long long int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    long long int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(long long int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
int main() {
    long long int resposta[2], numeros[100001], atual, proximo;
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        mergeSort(numeros, 0, n-1);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2; indice++) {
		    
		    atual = numeros[indice];
		    proximo = numeros[indice + 1];

			if (atual == proximo && indice < n - 1)
				indice++;
			else if (contador++ == 1)
			    printf("%lld\n", atual);
			else
			    printf("%lld ", atual);
		}
    }
    return 0;
}

Código em C++:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int compara (const void *a, const void *b) {
    
    long long int *a2 = (long long *)a;
    long long int *b2 = (long long *)b;

	if (*a2 == *b2)
		return 0;
	else if (*a2 > *b2)
		return 1;
	else
		return -1;

}

int main() {
    long long int resposta[2], numeros[100001];
    int n, contador, indice;
    
    while (scanf("%i", &n) != EOF) {
        
        memset(numeros, 0, sizeof(numeros));
            
        for (indice = 0; indice < n; indice++)
            scanf("%lld", &numeros[indice]);
        
        qsort(numeros, n, sizeof(long long int), compara);
        
        contador = 0;
		for (indice = 0; indice < n && contador < 2;) {

			if (numeros[indice] == numeros[indice + 1] && indice < n - 1)
				indice += 2;
				
			else {
				cout << numeros[indice++];
				
				if (contador++ == 1)
					cout << endl;
					
				else
					cout << " ";
			}
		}
    }
    return 0;
}