11638. Maratona

Olá meus amigos nerds! Esses dias notei que parte dos leitores do blog são iniciantes, então decidi voltar a postar soluções de problemas mais fáceis, afinal não queremos assustá-los! Não é mesmo?

Hoje vamos ver se nossos amigos corredores conseguem terminar uma maratona, já que é isso que o problema 11638. Maratona pede para fazer. Mais especificamente, dada a distância máxima que um corredor consegue percorrer, sem tomar água e a posição dos pontos onde é possível conseguir água. Determinar se ele consegue terminar a prova.

Solução

Basta ir verificando se a distância entre dois pontos de água consecutivos não é maior que a distância que o corredor consegue percorrer sem se hidratar. Após o último ponto de água também é necessário ver se o corredor consegue chegar até o final da prova. Lembrando que uma maratona tem um percurso de 42195 metros.

Implementação

814. Macaco-prego

Olá meus amigos nerds! Hoje vamos achar o melhor lugar para uma reserva ambiental de macacos prego, já que é isso que o problema 814. Macaco-prego pede para fazer. Mais especificamente, dadas as coordenadas de várias zonas retangulares de um mapa determinar a interseção de todas elas.

Solução

No caso geral esse problema seria bem difícil, mas como só temos retângulos com os lados paralelos aos eixos ele fica mais fácil. Só saber que os retângulos se interceptam também é muito fácil, mas não basta para resolvermos o problema! Precisamos ser capazes de calcular a interseção.

Sejam A e B os dois retângulos que queremos interceptar. Construa um retângulo que contenha A e B e que tenha como pontos extremos os pontos mais distantes de cada retângulo (ou seja, ordena as coordenadas de A e B e pegue o primeiro e último elementos do vetor). Os pontos restantes da ordenação formam um segundo retângulo C que está contido no super retângulo. Esses pontos formam a interseção de A e B, caso ela exista. Para saber se a interseção existe, veja se tanto A quanto B contém o centro de C.

Implementação

11013. Quadrado mágico

Olá meus amigos nerds! Hoje vamos brincar de escrever quadrados mágicos, já que é isso que o problema 11013. Quadrado mágico pede para fazer. Mais especificamente, dada uma matriz verificar se a soma de todas as suas linhas, colunas e diagonais é igual e que ela contém todos os números de 1 a n^2, sendo n a ordem da matriz.

Solução

Basta somar as linhas e colunas e ver se tem o mesmo resultado. Além disso, também é preciso verificar se todos os números de 1 a n^2 estão na matriz.

Implementação

Note que, dado o tamanho dos números da entrada, o resultado da soma pode não caber em um int.

8314. Fórmula 1

Olá meus amigos nerds! Hoje vamos descobrir quem ganhou o mundial de Formula 1, já que é isso que o problema 8314. Fórmula 1 pede para fazer. Mais especificamente, dadas as ordens de chegada dos pilotos em diversas corridas e o sistema de pontuação determinar quem foi o campeão ao fim da temporada.

Solução

Esse é um simples problema de ordenação. Some as pontuações de cada piloto ordene o resultado e imprima aqueles que tiverem mais pontos.

Implementação

Quando olho para um código feio como esse meu de muitos anos atráz fico feliz de ver que eu melhorei pelo menos um pouquinho :P

11631. Número de Envelopes

Olá meus amigos nerds! Para terminar o ano de boas, nada melhor do que resolver um probleminha fácil! Não é? Por isso, hoje vamos contar rotulos de produtos, já que é isso que o problema 11631. Número de Envelopes pede. Mais especificamente, a partir de uma lista de rótulos, queremos calcular o número máximo de envelopes que podemos formar, sendo que cada envelope tem que ter um rótulo de cada produto distinto.

Solução

Obviamente o número máximo de envelopes que podemos ter é igual ao número de rótulos do produto que temos menos rótulos.

Implementação

1850. Conte os Fatores

Olá meus amigos nerds! Hoje vamos brincar de fatoração, já que é isso que o problema 1850. Conte os Fatores pede. Mais especificamente, dado um número n, calcular o número de diferentes fatores primos que ele tem.

Solução

Esse é um problema fácil, bom para resolver depois da ressaca de Natal. Um algoritmo simples de fatoração é a solução.

Implementação

11675. Olimpíadas

Olá meus amigos nerds! Hoje vamos falar de olimpíadas, já que o problema 11675. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas overall. Se houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.

Solução

Esse problema é quase uma cópia do 11646 Olimpíadas. Um problema simples de ordenação. Basta ordenar os países de acordo com a regra dada e pronto. 

Implementação

Para tornar o problema mais interessante, implementei eu mesmo o quicksort. No outro post eu expliquei um pouco de como é a implementação dele.