URI (BEECROWD) - 2567 - Vírus - Ad-Hoc - C, C++ e Haskell

Aqui vai mais uma solução, pessoal! O problema Vírus ainda não tinha sido resolvido por mim.  Ele é bem simples, basicamente precisa usar ordenação. Fiz ele em três linguagens, aquelas três que eu mais uso por aqui... então, vamos ao que interessa!

Plataforma: Beecrowd (antiga URI)

Problema: 2567

Enunciado:

A secretaria de saúde pública da Nlogônia acabou de emitir um alerta. Um vírus está contagiando toda a população.

Após muitos estudos, os pesquisadores do país determinaram que, após infiltrarem o corpo hospedeiro, os virus se juntam dois a dois para tornarem-se letais. O nível de letalidade de uma infecção é determinado pela soma da diferença da idade, em dias, dos vírus pareados. Os vírus sem pares não influenciam no nível.

Desta forma, se existem 4 vírus no corpo hospedeiro com idades (em dias), iguais a

4, 10, 9, 43

E eles se paream da seguinte forma:

4 com 9, 43 com 10

Então nível de letalidade seria (9 - 4) + (43 - 10) = 38.

A secretaria de saúde pública da Nlogônia pediu para que você escrevesse um programa que, dado a contagem de vírus em um corpo e a idade de cada um deles, calcule o nível máximo de letalide que a infecção pode assumir.

Linguagens: C, C++ e Haskell

Solução:

Nesse exercício, portanto, bastava unir os valores dois a dois, sempre o maior com o menor e assim por diante, subtraindo e acumulando a resposta. É muito fácil! Pra isso, resolvi com ordenação, mas há outras formas de resolver. E você, como fez? Veja na sequência os três códigos disponíveis em C, C++ e Haskell.

Código em C++:

Aqui eu acabei usando uma estrutura vector para armazenar os valores e depois ordenei esses valores da estrutura com a função pronta sort, da biblioteca algorithm. Após essa ordenação, casei os valores inicial e final, depois o segundo e o penúltimo, e assim por diante, para fazer a subtração desejada no exercício, acumulando esses resultados e obtendo assim a resposta final.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main () {
   int n;
   while (cin >> n) {
      vector<int> valores;
      int v;
      for (int i = 0; i < n; i++) {
         cin >> v;
         valores.push_back(v);
      }
      sort(valores.begin(), valores.end());
      int metade = n / 2;
      int resposta = 0;
      for (int i = 0; i < metade; i++ )
         resposta += valores.at(n-i-1) - valores.at(i);
      cout << resposta << endl;
   }
   return 0;
}

Código em C:

Aqui eu usei a função pronta qsort, de stdlib.h, e só criei a função compara para dizer como deve ser a comparação entre os valores. Isso porque após ordenar, basta unir sempre os pares do primeiro com o último, o segundo com o penúltimo e assim por diante.

#include <stdio.h>
#include <stdlib.h>
int compara(const void *a, const void *b) {
   return (*(int*)a - *(int*)b);
}

int main () {
   int n;
   while (scanf("%d", &n) != EOF) {
      int valores[n];
      for (int i = 0; i < n; i++)
         scanf("%d", &valores[i]);
      qsort(valores, n, sizeof(int), compara);
      int metade = n / 2;
      int resposta = 0;
      for (int i = 0; i < metade; i++ )
         resposta += valores[n-i-1] - valores[i];
      printf("%d\n", resposta);
   }
   return 0;
}

Código em Haskell:

A lógica adotada no código Haskell foi a mesma. Aqui também há função pronta para ordenação, bem como há função pronta para obter o primeiro valor de uma lista (init) como o último valor (last), o que facilita nessa junção de valores.

import Data.List (sort)
import System.IO (isEOF)

obtemResposta :: [Int] -> Int
obtemResposta [] = 0
obtemResposta (x:[]) = 0
obtemResposta (x:xs) = last xs - x + obtemResposta (init xs)

main :: IO ()
main = do
   concluido <- isEOF
   if concluido
      then return ()
      else do
         n <- readLn :: IO Int
         linha <- getLine
         let valores = map read (words linha) :: [Int]
         let valoresOrdenados = sort valores
         let resposta = obtemResposta valoresOrdenados
         print resposta
         main

Apoie o blog colaborando com qualquer quantia. A chave pix (chave aleatória) é 6d8bc7a8-5d74-493a-ab7a-3515baf35956

Obrigado!