URI (BEECROWD) - 3089 - Presentes de Natal - Iniciante - C e C++

Novo post! Esse é sobre o problema "Presentes de Natal", da plataforma URI/BEECROWD.  Resolvi ele em C e C++. Veja abaixo como isso foi feito!

Plataforma: URI (BEECROWD)

Problema: 3089

Linguagens: C e C++

Solução:

Utilizei basicamente a mesma solução, mas em cada linguagem ela usa estruturas e funções diferentes devido às particularidades de cada uma.

Após a declaração das variáveis, todo código fica em um laço infinito que tem como primeira instrução a leitura do valor n, um inteiro com sinal. A interrupção do laço só ocorre no caso do valor de n ser zero. Enquanto isso não acontece, todos os casos são válidos e sua lógica acontece na sequência.

Feita esta explicação inicial, o "núcleo da solução" é o seguinte: lê-se 2n valores (inteiros com sinal) e coloca-se estes valores em uma estrutura. Após todas as leituras é necessário ordenar os valores e gerar os pares de valores. Esses pares também são ordenados, assim fica fácil obter os pares mais caros e mais baratos. Nesse laço de repetição que soma os pares é necessário utilizar dois índices, um iniciando no primeiro elemento (índice 0) e outro no último (2n-1). A estrutura que armazena os pares deverá ser ordenada também, assim ela terá nas posições 0 e n-1 os valores mais alto e baixo, respectivamente. Basta imprimir os valores dessas posições.

Código em C:

Para cumprir a solução foi necessário declarar p e pares como arrays e utilizar qsort (da biblioteca stdlib.h) para ordená-los. Criou-se também uma função de comparação (cmpfunc), como pede a assinatura da qsort. 

A função memset foi utilizada para garantir que todas as posições de p e parese stejam com o valor padrão zero a cada iteração, evitando que as estruturas ainda tenham lixo da iteração anterior.

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

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

int main() {
    
    int n, i, j;
    int p[1000000], pares[1000000];
    
    while (1) {
        
        scanf("%d", &n);
        
        if (!n)
            break;
        
        for (i = 0; i < 2 * n; i++)
            scanf("%d", &p[i]);
        
        qsort(p, 2*n, sizeof(int), cmpfunc);
        
        for (i = 0, j = 2 * n - 1; i < n; i++, j--)
            pares[i] = p[i] + p[j];
        
        qsort(pares, n, sizeof(int), cmpfunc);
        printf("%d %d\n", pares[n-1], pares[0]);
        
        memset(p, 0, sizeof(p));
        memset(pares, 0, sizeof(pares));
    }

    return 0;
}

Código em C++:

Utilizando a estrutura vector o código em C++ fica bem mais simples em relação ao código em C. Não é necessário implementar um algoritmo de ordenação, podendo utilizar o algoritmo sort, disponível na biblioteca algorithm. Para remover todos os elementos dos vectors p e pares, utiliza-se a função clear. O acesso ao vector por índice também é diferente. Pode-se fazê-lo por meio do at(indice), mas há casos em que nem precisamos indicar o índice. Quando queremos o primeiro e o último elemento, podemos fazer o acesso por meio da função front e da função back, respectivamente.

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

using namespace std;

int main() {
    
    int n, meio, i, j, v;
    vector<int> p, pares;
    
    while (true) {
        
        cin >> n;
        
        if (!n)
            break;
        
        for (i = 0; i < 2 * n; i++) {
            cin >> v;
            p.push_back(v);
        }
        
        sort(p.begin(), p.end());
        
        meio = p.size() / 2;
        
        for (i = 0, j = p.size()-1; i < p.size()/2; i++, j--)
            pares.push_back(p.at(i) + p.at(j));
        
        sort(pares.begin(), pares.end());
        cout << pares.back() << " " << pares.front() << endl;
        
        p.clear();
        pares.clear();
    }

    return 0;
}