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.

8699. Dentista

Olá meus amigos nerds. O circo político do Brasil está pegando fogo hoje. Por isso vou falar rapidinho, já que há coisas mais interessantes que resolver problemas agora.

Hoje vamos resolver conflitos na agenda do doutor Pedro, já que é isso que o problema 8699. Dentista pede para fazer. Mais especificamente, dada a agenda de Pedro, com todos os horários de consulta, determinar qual é o maior número de consultas que ele consegue atender.

Solução

Uma forma ótima de escolher qual a primeira consulta a atender (de modo a maximizar o número total de consultas atendidas) é escolher aquela que acabaria primeiro. Pois, nesse caso, Pedro ficaria disponível o mais cedo possível para atender uma nova consulta. Aplicando essa ideia recursivamente chegamos a solução do problema.

Dito de um modo mais algorítmico:

Ordene as consultas por tempo de término.
Enquanto a lista de consultas não estiver vazia
    Atenda a primeira consulta da lista.
   Remova da lista cada consulta que o tempo de início é menor que o tempo de término da consulta que Pedro está atendendo no momento (como ele esta ocupado, ele não pode atender essas consultas)

Implementação