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;
}