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 nós vamos ajudar Joãozinho a descobrir qual peça de seu quebra cabeça está faltando, já que é isso que o problema PECA7 - Peça Perdida pede para fazer. Mais especificamente, dadas n - 1 peças do quebra cabeça, numeradas de 1 a N, determinar a peça faltante.
Solução
A numeração das peças do quebra cabeça forma uma progressão aritmética, de primeiro termo 1, último termo N e razão 1. Assim, a soma de todas as numerações é N * (1 + N) / 2.
Por outro lado podemos somar as numerações das N-1 peças dadas. E se da soma total subtrairmos esse valor encontraremos o valor da peça faltante.
Olá meus amigos nerds! Hoje vos escrevo humildemente do México, infelizmente trabalhando, mesmo assim vamos brincar um pouco de resolver um probleminha fácil. Hoje vamos calcular o número de contêineres que um navio de carga suporta, já que é isso que o problema TRANSP11 - Transporte pede para fazer. Mais especificamente, dadas as dimensões do navio e dos contêineres calcular qual é o número máximo deles que podem ser acomodados no navio.
Solução
A solução do problema é bem simples. Como não podemos mudar a posição dos contêineres o máximo que podemos acomodar em uma direção é a medida do navio naquela direção dividida pelo tamanho correspondente de um contêiner. Assim basta multiplicar os valores obtidos para cada uma das três dimensões que temos nosso número máximo de contêineres.
Olá meus amigos nerds! Depois de uma longa pausa, estou de volta a ativa. Hoje vamos brincar de arredondar o troco, já que é isso que o problema MERCADO - Mercado do seu João pede para fazer. Mais especificamente, dada uma lista contendo os valores das vendas determinar o total vendido, bem como a diferença entre esse total e o total arredondando-se o valor das vendas.
A solução desse problema foi um pedido do nosso leitor Henryque Santos.
Solução
A solução do problema é bem simples. Basta ir somando os valores das compras e somando o valor arredondado em uma outra variável (aplicando o critério de arredondamento do seu João). No final é só fazer a diferença dos dois valores.
Implementação
Resolvi estudar um pouco de Go para ver se é uma boa linguagem, então vocês vão começar a ver um pouco de Go por aqui :)
Olá meus amigos nerds! Hoje vamos brincar de caça ao tesouro, já que é isso que o problema TESOUR11 - Caça ao tesouro pede para fazer. Mais especificamente, dado um mapa com pistas da localização do tesouro, verificar se é possível encontrá-lo.
Solução
A bem da verdade o problema mais parece com um jogo de campo minado do que com uma caça ao tesouro.
Pense em cada pista como um conjunto de possíveis posições para o tesouro. Para que a posição do tesouro seja determinada de maneira única é necessário que a interseção desses conjuntos tenha tamanho 1. Assim, basta para cada pista calcular as possíveis posições do tesouro e fazer a interseção de todos os conjuntos.
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).
