Editorial da Competição Canadense de Computação 2016 - Divisão Junior
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
usandoprintf
. 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çãomax
para calcular a velocidade da bicicleta em cada par. A cada iteração, somamos o resultado à variávelvelocidade_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ávelvelocidade_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