Editorial da Competição Canadense de Computação 2016 - Divisão Junior

Exercícios
Texto por
User Image
Abacate

Segue abaixo o editorial da competição.


A - Seleção de torneios

Explicação:

Passo 1: Ler os Resultados das Partidas

Primeiro, vamos ler os resultados das seis partidas para o jogador. Utilizaremos um loop for para ler cada resultado, onde 'W' indica uma vitória e 'L' indica uma derrota. Armazenaremos o número de vitórias em uma variável chamada wins.

Passo 2: Determinar o Grupo do Jogador

Agora que temos o número de vitórias do jogador (armazenado em wins), podemos determinar em qual grupo ele será colocado com base nas regras fornecidas. Vamos usar instruções condicionais para verificar essas condições e imprimir o grupo correspondente ou "-1" se o jogador for eliminado.

Exemplo de solução em C++:

#include <iostream>

using namespace std;

int main() {
    char result;
    int wins = 0;

    // Lê os resultados das seis partidas
    for (int i = 0; i < 6; i++) {
        cin >> result;
        if (result == 'W') {
            wins++;
        }
    }

    // Determina o grupo com base no número de vitórias
    if (wins >= 5) {
        cout << "1" << endl;
    } else if (wins >= 3) {
        cout << "2" << endl;
    } else if (wins >= 1) {
        cout << "3" << endl;
    } else {
        cout << "-1" << endl; // Jogador eliminado
    }

    return 0;
}

Exemplo de solução em Python 3:

wins = 0

# Lê os resultados das seis partidas
for i in range(6):
    result = input()
    if result == 'W':
        wins += 1

# Determina o grupo com base no número de vitórias
if wins >= 5:
    print("1")
elif wins >= 3:
    print("2")
elif wins >= 1:
    print("3")
else:
    print("-1")  # Jogador eliminado

B - Quadrados mágicos

Explicação:

Passo 1: Leitura da Entrada

O primeiro passo é ler a entrada do usuário. No problema, a entrada consiste em quatro linhas, cada uma contendo quatro inteiros separados por espaços. Vamos usar uma matriz para armazenar esses números e duas matrizes adicionais para calcular as somas das linhas e das colunas. Usamos um loop duplo para percorrer todas as células da matriz quadrado. Ao mesmo tempo, estamos calculando as somas das linhas em somaLinha e as somas das colunas em somaColuna.

Passo 2: Verificação de Quadrado Mágico

Após a leitura da entrada, precisamos verificar se o quadrado é mágico. Isso envolve duas etapas: verificar se as somas das linhas são iguais e se as somas das colunas são iguais. Começamos definindo uma variável booleana eMagico como verdadeira. Em seguida, comparamos as somas das linhas e das colunas com a soma da primeira linha. Se encontrarmos uma soma que não seja igual ao alvo, definimos eMagico como falso e saímos do loop.

Passo 3: Impressão do Resultado

Por fim, precisamos imprimir o resultado com base no valor de eMagico. Se eMagico for verdadeiro, o quadrado é mágico e imprimimos "magic". Caso contrário, imprimimos "not magic".

Exemplo de solução em C++:

#include <iostream>

using namespace std;

int main() {
    int quadrado[4][4];
    int somaLinha[4] = {0};
    int somaColuna[4] = {0};

    // Ler a entrada
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> quadrado[i][j];
            somaLinha[i] += quadrado[i][j];
            somaColuna[j] += quadrado[i][j];
        }
    }

    // Verificar se é um quadrado mágico
    bool eMagico = true;
    int somaAlvo = somaLinha[0]; // O alvo é a soma da primeira linha

    // Verificar se as somas das linhas são iguais ao alvo
    for (int i = 1; i < 4; i++) {
        if (somaLinha[i] != somaAlvo) {
            eMagico = false;
            break;
        }
    }

    // Verificar se as somas das colunas são iguais ao alvo
    for (int j = 0; j < 4; j++) {
        if (somaColuna[j] != somaAlvo) {
            eMagico = false;
            break;
        }
    }

    // Imprimir o resultado
    if (eMagico) {
        cout << "magic" << endl;
    } else {
        cout << "not magic" << endl;
    }

    return 0;
}

Exemplo de solução em Python 3:

def main():
    quadrado = [[0] * 4 for _ in range(4)]
    soma_linha = [0] * 4
    soma_coluna = [0] * 4

    # Ler a entrada
    for i in range(4):
        linha = input().split()
        for j in range(4):
            quadrado[i][j] = int(linha[j])
            soma_linha[i] += quadrado[i][j]
            soma_coluna[j] += quadrado[i][j]

    # Verificar se é um quadrado mágico
    e_magico = True
    soma_alvo = soma_linha[0]  # O alvo é a soma da primeira linha

    # Verificar se as somas das linhas são iguais ao alvo
    for i in range(1, 4):
        if soma_linha[i] != soma_alvo:
            e_magico = False
            break

    # Verificar se as somas das colunas são iguais ao alvo
    for j in range(4):
        if soma_coluna[j] != soma_alvo:
            e_magico = False
            break

    # Imprimir o resultado
    if e_magico:
        print("magic")
    else:
        print("not magic")

if __name__ == "__main__":
    main()

C - Palíndromo Oculto

Explicação:
Passo 1: Leitura da Entrada

O primeiro passo é ler a entrada que consiste em uma única linha contendo uma sequência de letras minúsculas, com tamanho mínimo de 1 e máximo de 40.

Lemos a palavra de entrada, determinamos o tamanho da palavra e inicializamos a variável maxPalindromo como 1, uma vez que um palíndromo individual de uma única letra é válido.

Passo 2: Verificação de Palíndromos

A abordagem para encontrar o palíndromo mais longo é percorrer a palavra e verificar palíndromos centrados em cada posição da palavra, bem como palíndromos com centro entre caracteres.

Vamos usar loops que percorrem a palavra e expandem a partir de cada posição para verificar se um palíndromo pode ser formado. O comprimento do palíndromo é calculado e comparado com o maxPalindromo atual. Se for maior, atualizamos maxPalindromo.

Passo 3: Impressão do Resultado
Por fim, imprimimos o valor de maxPalindromo, que representa o comprimento do palíndromo mais longo contido na palavra.

Exemplo de solução em C++:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string palavra;
    cin >> palavra;
    int tamanho = palavra.size();
    int maxPalindromo = 1;  // Inicialmente, o maior palíndromo é uma única letra

    // Loop para verificar palíndromos centrados em cada posição da palavra
    for (int centro = 0; centro < tamanho; centro++) {
        int i = centro;
        int j = centro;
        while (i >= 0 && j < tamanho && palavra[i] == palavra[j]) {
            int comprimento = j - i + 1;
            if (comprimento > maxPalindromo) {
                maxPalindromo = comprimento;
            }
            i--;
            j++;
        }
    }

    // Loop para verificar palíndromos com centro entre caracteres
    for (int centro = 0; centro < tamanho - 1; centro++) {
        int i = centro;
        int j = centro + 1;
        while (i >= 0 && j < tamanho && palavra[i] == palavra[j]) {
            int comprimento = j - i + 1;
            if (comprimento > maxPalindromo) {
                maxPalindromo = comprimento;
            }
            i--;
            j++;
        }
    }

    cout << maxPalindromo << endl;

    return 0;
}

Exemplo de solução em Python 3:

def encontra_palindromo_mais_longo(palavra):
    tamanho = len(palavra)
    max_palindromo = 1  # Inicialmente, o maior palíndromo é uma única letra

    # Loop para verificar palíndromos centrados em cada posição da palavra
    for centro in range(tamanho):
        i = centro
        j = centro
        while i >= 0 and j < tamanho and palavra[i] == palavra[j]:
            comprimento = j - i + 1
            if comprimento > max_palindromo:
                max_palindromo = comprimento
            i -= 1
            j += 1

    # Loop para verificar palíndromos com centro entre caracteres
    for centro in range(tamanho - 1):
        i = centro
        j = centro + 1
        while i >= 0 and j < tamanho and palavra[i] == palavra[j]:
            comprimento = j - i + 1
            if comprimento > max_palindromo:
                max_palindromo = comprimento
            i -= 1
            j += 1

    return max_palindromo

palavra = input()
resultado = encontra_palindromo_mais_longo(palavra)
print(resultado)

D - Hora de Chegada

Explicação do código:
Passo 1: Ler o Horário de Partida

  • Neste passo, o código lê o horário de partida de Fiona no formato HH:MM.
  • A função stoi é usada para converter os dois primeiros caracteres da entrada em um número inteiro, que representa as horas, e os dois últimos caracteres em outro número inteiro, que representa os minutos.
  • Agora temos as informações de horas e minutos separadamente para usar nos cálculos subsequentes.

Passo 2: Verificar o Horário de Pico

  • O código verifica se Fiona está viajando durante o horário de pico da manhã ou tarde.

Passo 3: Calcular a Hora de Chegada

  • A lógica do código calcula o tempo de viagem com base nas seguintes situações:

    • Durante o horário de pico da manhã:

      • Calcula a duração até o final do horário de pico da manhã, levando em consideração a redução de velocidade.
      • Em seguida, calcula o tempo restante até o total de 2 horas de viagem.
      • Ajusta as horas e minutos de chegada com base nos cálculos.
    • Antes do horário de pico da manhã:

      • Calcula a duração até o início do horário de pico da manhã (7:00).
      • Calcula o tempo restante da viagem, que é dobrado (devido à ausência de tráfego) ou reduzido após 90 minutos, dependendo do caso.
      • Ajusta as horas e minutos de chegada com base nos cálculos.
    • Antes do horário de pico da tarde:

      • Calcula a duração até o início do horário de pico da tarde (15:00).
      • Calcula o tempo restante da viagem, que é dobrado.
      • Ajusta as horas e minutos de chegada com base nos cálculos.
    • Outros horários:

      • Para horários fora do pico, adiciona 2 horas ao horário de partida, representando uma viagem normal sem redução de velocidade.
      • Ajusta as horas de chegada e garante que não ultrapassem 24 horas no formato de relógio.

Passo 4: Imprimir o Resultado

  • Após os cálculos, o código imprime a hora de chegada no formato HH:MM usando printf. Isso garante que a hora de chegada seja apresentada de maneira formatada.

Exemplo de solução em C++:

#include <iostream>
#include <string>

using namespace std;

const int DURACAO_TOTAL_MINUTOS = 120;

int main() {
    string horario_partida;
    cin >> horario_partida;

    int horas = stoi(horario_partida.substr(0, 2));
    int minutos = stoi(horario_partida.substr(3, 2));

    // Verifica se Fiona está viajando durante o horário de pico da manhã ou tarde
    if ((7 <= horas && horas < 10) || (15 <= horas && horas < 19)) {
        int duracao_metade;
        if (7 <= horas && horas < 10) {
            // Calcula a duração reduzida pela metade durante o horário de pico da manhã
            duracao_metade = ((10 - horas) * 60 - minutos) / 2;
        } else {
            // Calcula a duração reduzida pela metade durante o horário de pico da tarde
            duracao_metade = ((19 - horas) * 60 - minutos) / 2;
        }
        // Calcula a duração restante da viagem
        int duracao_restante = DURACAO_TOTAL_MINUTOS - duracao_metade;
        minutos = duracao_restante % 60;
        if (7 <= horas && horas < 10) {
            // Calcula as horas de chegada para o horário de pico da manhã
            horas = 10 + (duracao_restante / 60);
        } else {
            // Calcula as horas de chegada para o horário de pico da tarde
            horas = 19 + (duracao_restante / 60);
        }
        horas %= 24; // Garante que as horas não ultrapassem 24 horas
    } else if (5 <= horas && horas < 7) {
        int duracao_restante = (7 - horas) * 60 - minutos;
        int duracao_dobrada = DURACAO_TOTAL_MINUTOS - duracao_restante;
        if (duracao_dobrada < 90) {
            // Calcula a duração dobrada da viagem de manhã
            duracao_dobrada *= 2;
            horas = 7 + (duracao_dobrada / 60);
            minutos = duracao_dobrada % 60;
        } else {
            // Calcula a duração após o horário de pico da manhã
            duracao_restante = duracao_dobrada - 90;
            horas = 10 + (duracao_restante / 60);
            minutos = duracao_restante % 60;
        }
    } else if (13 <= horas && horas < 15) {
        int duracao_restante = (15 - horas) * 60 - minutos;
        // Calcula a duração dobrada da viagem de tarde
        int duracao_dobrada = (DURACAO_TOTAL_MINUTOS - duracao_restante) * 2;
        horas = 15 + (duracao_dobrada / 60);
        minutos = duracao_dobrada % 60;
    } else {
        // Calcula a hora de chegada para horários fora do pico
        horas = (horas + 2) % 24;
    }

    printf("%02d:%02d\n", horas, minutos);
    
    return 0;
}

Exemplo de solução em Python 3:

horario_partida = input()

horas = int(horario_partida[:2])
minutos = int(horario_partida[3:])

DURACAO_TOTAL_MINUTOS = 120

# Verifica se Fiona está viajando durante o horário de pico da manhã ou tarde
if (7 <= horas < 10) or (15 <= horas < 19):
    if 7 <= horas < 10:
        # Calcula a duração reduzida pela metade durante o horário de pico da manhã
        duracao_metade = ((10 - horas) * 60 - minutos) // 2
    else:
        # Calcula a duração reduzida pela metade durante o horário de pico da tarde
        duracao_metade = ((19 - horas) * 60 - minutos) // 2
    # Calcula a duração restante da viagem
    duracao_restante = DURACAO_TOTAL_MINUTOS - duracao_metade
    minutos = duracao_restante % 60
    if 7 <= horas < 10:
        # Calcula as horas de chegada para o horário de pico da manhã
        horas = 10 + (duracao_restante // 60)
    else:
        # Calcula as horas de chegada para o horário de pico da tarde
        horas = 19 + (duracao_restante // 60)
    horas %= 24
elif 5 <= horas < 7:
    duracao_restante = (7 - horas) * 60 - minutos
    duracao_dobrada = DURACAO_TOTAL_MINUTOS - duracao_restante
    if duracao_dobrada < 90:
        # Calcula a duração dobrada da viagem de manhã
        duracao_dobrada *= 2
        horas = 7 + (duracao_dobrada // 60)
        minutos = duracao_dobrada % 60
    else:
        # Calcula a duração após o horário de pico da manhã
        duracao_restante = duracao_dobrada - 90
        horas = 10 + (duracao_restante // 60)
        minutos = duracao_restante % 60
elif 13 <= horas < 15:
    duracao_restante = (15 - horas) * 60 - minutos
    # Calcula a duração dobrada da viagem de tarde
    duracao_dobrada = (DURACAO_TOTAL_MINUTOS - duracao_restante) * 2
    horas = 15 + (duracao_dobrada // 60)
    minutos = duracao_dobrada % 60
else:
    # Calcula a hora de chegada para horários fora do pico
    horas = (horas + 2) % 24

print(f"{horas:02d}:{minutos:02d}")

E - Bicicleta Tandem

Explicação:

Passo 1: Leitura da Entrada

O primeiro passo é ler a entrada do problema. Vamos usar as variáveis tipo_de_pergunta, N, velocidades_cidadaos_Dmojistan e velocidades_cidadaos_Pegland para armazenar as informações.

Passo 2: Ordenação das Velocidades

Para otimizar a atribuição dos cidadãos em pares, vamos ordenar as velocidades em ordem decrescente. Isso facilitará o emparelhamento, pois a pessoa mais rápida sempre operará a bicicleta tandem.

Usamos a função sort da biblioteca <algorithm> para fazer a ordenação em ordem decrescente para ambas as listas de velocidades, ou seja, velocidades_cidadaos_Dmojistan e velocidades_cidadaos_Pegland.

Passo 3: Cálculo da Velocidade Total

A próxima etapa é calcular a velocidade total com base na pergunta feita (mínima ou máxima).

  • Se a pergunta for do tipo 1 (mínima), iteramos sobre as velocidades ordenadas de ambas as listas e somamos o máximo de cada par de velocidades. Isso é feito usando um loop for e a função max para calcular a velocidade da bicicleta em cada par. A cada iteração, somamos o resultado à variável velocidade_total.

  • Se a pergunta for do tipo 2 (máxima), também usamos um loop for, mas desta vez iteramos sobre as velocidades de Pegland em ordem decrescente. Isso nos permite emparelhar a pessoa mais rápida de Dmojistan com a pessoa mais lenta de Pegland em cada par, maximizando a velocidade da bicicleta. Novamente, a cada iteração, somamos o resultado à variável velocidade_total.

Passo 4: Impressão do Resultado

Por fim, imprimimos o valor da velocidade_total, que representa a velocidade total mínima ou máxima, dependendo da pergunta feita.

Exemplo de solução em C++:

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

using namespace std;

int main() {
    int tipo_de_pergunta;
    cin >> tipo_de_pergunta;

    int N;
    cin >> N;

    // Leitura das velocidades dos cidadãos de Dmojistan e Pegland
    vector<int> velocidades_cidadaos_Dmojistan(N);
    vector<int> velocidades_cidadaos_Pegland(N);

    for (int i = 0; i < N; i++) {
        cin >> velocidades_cidadaos_Dmojistan[i];
    }

    for (int i = 0; i < N; i++) {
        cin >> velocidades_cidadaos_Pegland[i];
    }

    // Ordena as velocidades em ordem decrescente para facilitar o emparelhamento
    sort(velocidades_cidadaos_Dmojistan.begin(), velocidades_cidadaos_Dmojistan.end(), greater<int>());
    sort(velocidades_cidadaos_Pegland.begin(), velocidades_cidadaos_Pegland.end(), greater<int>());

    int velocidade_total = 0;

    // Calcula a velocidade total com base na pergunta (mínima ou máxima)
    if (tipo_de_pergunta == 1) { // Pergunta 1: mínimo
        for (int i = 0; i < N; i++) {
            velocidade_total += max(velocidades_cidadaos_Dmojistan[i], velocidades_cidadaos_Pegland[i]);
        }
    } else { // Pergunta 2: máximo
        for (int i = 0; i < N; i++) {
            velocidade_total += max(velocidades_cidadaos_Dmojistan[i], velocidades_cidadaos_Pegland[N - i - 1]);
        }
    }

    cout << velocidade_total << endl;

    return 0;
}

Exemplo de solução em Python 3:

tipo_de_pergunta = int(input())

N = int(input())

# Leitura das velocidades dos cidadãos de Dmojistan e Pegland
velocidades_dos_cidadaos_de_Dmojistan = list(map(int, input().split()))
velocidades_dos_cidadaos_de_Pegland = list(map(int, input().split()))

# Ordena as velocidades em ordem decrescente para facilitar o emparelhamento
velocidades_dos_cidadaos_de_Dmojistan.sort(reverse=True)
velocidades_dos_cidadaos_de_Pegland.sort(reverse=True)

velocidade_total = 0

# Calcula a velocidade total com base na pergunta (mínima ou máxima)
if tipo_de_pergunta == 1:  # Pergunta 1: mínimo
    for i in range(N):
        velocidade_total += max(velocidades_dos_cidadaos_de_Dmojistan[i], velocidades_dos_cidadaos_de_Pegland[i])
else:  # Pergunta 2: máximo
    for i in range(N):
        velocidade_total += max(velocidades_dos_cidadaos_de_Dmojistan[i], velocidades_dos_cidadaos_de_Pegland[N - i - 1])

print(velocidade_total)

Comentários

Flag Icon