URI (BEECROWD) - 3059 - Pares de Números - Ad-Hoc - C, C++ e Haskell

Hoje, mais uma vez, resolvo um problema Ad-Hoc! É o problema "Pares de Números".

Plataforma: Beecrowd (antiga URI)

Problema: 3059

Enunciado:

Temos um vetor de N inteiros distintos e dois inteiros I e F. Precisamos computar quantos pares desses inteiros do vetor somam pelo menos I e no máximo F. Por exemplo, se o vetor for [45, 12, 11, 7, 83, 29, 5] e I = 19 e F = 52, temos exatamente 8 pares cuja soma está entre 19 e 52: {5, 29}, {5, 45}, {7, 12}, {7, 29}, {7, 45}, {11, 12}, {11, 29} e {12, 29}.

Linguagens: C, C++ e Haskell

Solução:

Nesta solução, fiz um array para ler os valores e verifiquei os pares por uma variável de soma, que somava v[j] e v[k]. Sempre que esse valor fosse >= i e <= f eu incrementava a variável de resposta.

Código em C++:

#include <iostream>
int main() {
   int n, i, f, soma;
   std::cin >> n >> i >> f;
   int v[n];
   for (int j = 0; j < n; j++)
      std::cin >> v[j];

   int resposta = 0;
   for (int j = 0; j < n - 1; j++)
      for (int k = j + 1; k < n; k++) {
         soma = v[j] + v[k];
         if (soma >= i and soma <= f)
            resposta++;
      }

   std::cout << resposta << std::endl;

   return 0;
}

Código em C:

#include <stdio.h>

int main() {
   int n, i, f, j, k, soma, resposta = 0;
   scanf("%d %d %d", &n, &i, &f);
   int v[n];
   for (j = 0; j < n; j++)
      scanf("%d ", &v[j]);
   for (j = 0; j < n - 1; j++)
      for (k = j + 1; k < n; k++) {
         soma = v[j] + v[k];
         if (soma >= i && soma <= f)
            resposta++;
      }

   printf("%d\n", resposta);
   return 0;
}

Código em Haskell:

Aqui usei uma compreensão de lista (list comprehension) para definir os pares x,y, onde x tem que ser diferente de y e a soma deles precisa satisfazer as condições em relação a i e f. Assim ficou fácil, pois a lista de pares resultantes tem tamanho igual ao dobro da resposta! Isso acontece porque ela vai pegar os pares x,y e y,x, ou seja, vai repetir porque em a tupla (x,y) e a tupla (y,x) são diferentes. Assim, a partir da lista gerada, basta obter o tamanho dela dividido por dois.

main :: IO ()
main = do
   linha <- getLine
   let [n, i, f] = map read (words linha) :: [Int]
   linha <- getLine
   let valores = map read (words linha) :: [Int]
   let comb = [(x, y) | x <- valores, y <- valores, x /= y, x + y >= i, x + y <= f]
   let qtdResultados = length comb
   print (div qtdResultados 2)

Chave PIX para doações: 6d8bc7a8-5d74-493a-ab7a-3515baf35956

Ajude o blog!