TESOUR11 - Caça ao tesouro

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.

Implementação

2281. Rumo aos 9s

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.

LUA - Temperatura Lunar

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.

Implementação

TAPETE14 - Tapetes

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:

argmax((l - b)^2 + b^2) = argmax(l^2 -2*l*b + 2*b^2)

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).