Solicitação de algoritmo 7

A solicitação foi realizada por Bruna Vitória Chaga, que faz uso de uma plataforma que achei bastante interessante para treinar a resolução de algoritmos.

Segue o enunciado na plataforma: https://thehuxley.com/problem/5?quizId=6719

Enunciado: no Banco do Brasilo, existem apenas dois caixas para atender as pessoas. Porém, toda hora do almoço é um problema, pois existem duas filas de pessoas e um dos funcionários precisa ir comer. Então, as duas filas precisam ser integradas. Sempre dá confusão. Para minimizar o problema, o gerente do banco, muito sovina, ao invés de contratar mais um funcionário, propôs a seguinte solução. As pessoas da fila do funcionário que foi almoçar devem ser intercaladas com as pessoas da fila do funcionário que ficou trabalhando, a partir da segunda posição.

Consiste dos inteiros n, m e k (0<=n <=10000, 0<=m <=10000, 1<=k<=2) correspondendo, respectivamente, a quantidade de pessoas que existem em cada fila e qual foi à fila que o funcionário foi almoçar, sendo k=1 para a primeira fila e k=2 para a segunda fila. Seguidos de n inteiros representando as pessoas da primeira file e m inteiros representando as pessoas da segunda fila. Os inteiros nunca se repetem.

A tentativa de resolução enviada pela Bruna segue abaixo.

#include <stdio.h>

int main() {
    int i=0, k=0;
    int cont, cont2;

    //leitura dos valores
    scanf("%d %d %d", &cont, &cont2, &k);
    int vet1[cont], vet2[cont2], vet3[cont+cont2];
    for (i=0; i<cont; i++){
        scanf("%d", &vet1[i]);
    }
    for (i=0; i<cont2; i++){
        scanf("%d", &vet2[i]);
    }
    
    int p=0;
    for (i=0; i<cont; i++){
       vet3[p] = vet1[i];
       p = p + 2;
    }
    p=1;
    for (i=0; i<cont2; i++){
       vet3[p] = vet1[i];
       p = p +2;
    }
    
    //escrita da saída
    for (i=0; i<cont+cont2; i++){
       printf("%d\n", vet3[i]);
    }

    return 0;
}

A leitura de valores e escrita da saída estão corretas. Veja que os vetores foram definidos na linha 9 e apenas depois de ler os valores que são necessários para definir o tamanho dos vetores.

Entre as linhas 17 e 26 é que se encontra a solução para o problema, sendo realizada a intercalação dos dois vetores com os dados, para um terceiro vetor.

A ideia aplicada está correta, mas um pequeno equívoco atrapalhou demais entender o problema. Na linha 24, possivelmente por causa do copia e cola, está sendo utilizado novamente o primeiro vetor, ao invés do segundo vetor. Ou seja, a linha 24 deveria ser vet3[p] = vet1[i];

Mesmo com essa correção, o problema ainda não está resolvido. Se ambas as filas tivessem o mesmo tamanho esse exercício seria simples e estaria concluído, mas como as filas possuem tamanho diferente, é necessário considerar isso, uma vez que o incremento não será sempre de duas em duas unidades.

Observando os dados de entrada de exemplo, onde a segunda fila é maior do que a primeira, isso me leva a alterar o trecho de código entre as linhas 22-26, substituindo/complementando com o trecho a seguir. Ou seja, com a minha especificação, se a primeira fila já terminou, então somente serão colocadas as pessoas da segunda fila e por isso o incremento deve ser unitário, não mais de dois em dois.

    p=1;
    for (i=0; i<cont2; i++){
       vet3[p] = vet2[i];
       if (i < cont-1) {
    	 p = p + 2;
       } else {
       	 p++;
       }
    }

Veja que algo similar deve ser feito para o trecho entre as linhas 17-21, para caso a primeira fila seja maior do que a segunda.

Além de levar em consideração se uma fila é maior do que a outra, o código da Bruna também não levou em consideração de qual fila saiu o funcionário. Veja que a informação do k não é levada em consideração na avaliação. Essa informação é importante para determinar o valor inicial da variável p nas linhas 17 e 22 do código inicial da Bruna.

#include <stdio.h>

int main() {
    int i=0, k=0, p;
    int cont, cont2;

	//leitura dos valores
    scanf("%d %d %d", &cont, &cont2, &k);
    int vet1[cont], vet2[cont2], vet3[cont+cont2];
    for (i=0; i<cont; i++){
        scanf("%d", &vet1[i]);
    }
    for (i=0; i<cont2; i++){
        scanf("%d", &vet2[i]);
    }
    
    if (k == 2) {
        p=0;
    } else {
        p=1;
    }
    for (i=0; i<cont; i++){
       vet3[p] = vet1[i];
       if (i < cont2-1) {
    	 p = p + 2;
       } else {
       	 p++;
       }
    }
    if (k == 2) {
        p=1;
    } else {
        p=0;
    }
    for (i=0; i<cont2; i++){
       vet3[p] = vet2[i];
       if (i < cont) {
    	 p = p + 2;
       } else {
       	 p++;
       }
    }
    
    //escrita da saída
    for (i=0; i<cont+cont2; i++){
       printf("%d\n", vet3[i]);
    }

    return 0;
}

Nesse problema é preciso considerar 2 itens: (1) a primeira fila deve se juntar a segunda, ou a segunda fila deve se juntar com a primeira; (2) a primeira fila é maior do que segunda, ou a segunda fila é maior do que a primeira. A combinação desses itens geram quatro possibilidades. Meu código ainda não está completamente correto, sendo que ele não funciona corretamente na condição na qual: a segunda fila deve se juntar com a primeira, sendo que a segunda fila é a maior.

Não vou alterar o algoritmo para deixar ele 100% para não atrapalhar a proposta pedagógica do ambiente Thehuxley. Mas acho interessante observar que, se for retirado o -1 da condição da linha 24, isso altera em que condições o código irá funcionar, assim como se adicionar o -1 na condição da linha 37, o código funcionará em outra condição.