Esse blog se destina a todos os nerds que não têm tempo para uma boa vida social, pois são atormentados por não conseguirem resolver os problemas do spoj. Aqui você poderá encontrar soluções comentadas para uma grande variedade de problemas relacionados a competições de programação.
Olá meus amigos nerds! Hoje vamos relembrar um pouquinho de critérios de divisibilidade, já que é isso que o problema 2281. Rumo aos 9s pede para fazer. Mais especificamente, dado um número, queremos determinar se ele é divisível por nove.
Solução
O problema é bem simples, inclusive nos lembrando qual é o critério de divisibilidade por 9 (a soma dos dígitos o ser). Basta então implementar o critério dado.
Implementação
O único cuidado a ser tomado nesse problema é que o número inicial é potencialmente bem grande, tendo que ser manipulado como uma string.
Olá meus amigos nerds! Agora que já conseguiram "escutar" ondas gravitacionais vamos brincar de ajudar a NASA a determinar a temperatura média em uma certa região da Lua, já que é isso que o problema LUA - Temperatura Lunar pede para fazer. Mais especificamente, dada uma sequência de temperaturas determinar a maior temperatura média em um intervalo de tamanho m.
Solução
O problema é bem simples, basta ir iterando sobre a entrada e computando a temperatura média. É só lembrar que cada ponto do vetor é potencialmente um início para a janela de tamanho m da temperatura média.
Olá meus amigos nerds! Um dos objetivos desse blog é ser útil a quem está aprendendo, assim, hoje vamos resolver um problema a pedido por vocês.
Hoje vamos embalar tapetes, já que é isso que o problema TAPETE14 - Tapetes pede para fazer. Mais especificamente, queremos maximizar o valor da carga de tapetes dado que temos que transportar exatamente n tapetes que somam exatos l metros.
Solução
Olhando por cima esse problema parece o clássico problema da mochila, cada tenho uma mochila de tamanho n e quero enche-la com o máximo valor possível. Mas não é, uma vez que eu tenho a restrição de ter exatamente n objetos dentro dela. A solução para esse problema no entanto é mais simples.
Dado que o valor do tapete aumenta com o quadrado de seu comprimento é sempre melhor eu aumentar o tamanho de apenas um tapete, ou seja, embalar n-1 tapetes de tamanho 1 e um tapete de tamanho l - (n - 1) (correspondente ao comprimento restante da embalagem). Vou provar essa afirmação para n=2, mas ela é válida para qualquer n.
Sejam a e b os comprimentos dos dois tapetes que eu quero embalar. Logo:
a + b = l
Sendo que eu quero maximizar:
argmax(a^2 + b^2) a < l (o tamanho de todos os tapetes tem que ser maior que 0) b < l
mas a = l - b, logo:
l é uma constante. Como o coeficiente de b^2 é positivo o polinômio tem apenas um ponto de mínimo, ou seja, para maximiza-lo basta aumentar b. O maior valor possível de b é l - 1.
Assim para n qualquer teríamos a fórmula para o valor máximo = (l-n+1)^2+ (n - 1) [comprimento do maior tapete ao quadrado mais soma do valor dos n-1 tapetes de tamanho 1].
Implementação
Há um erro na indicação do tamanho da entrada. n, l <= 10^6 e não 106. Assim n^2 não cabe em 32 bits, logo temos que usar um inteiro de 64 bits (long long).
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.
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.
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.
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
