GUARDCOS - Guarda costeira

Olá meus amigos nerds! Hoje nós vamos ajudar a guarda costeira a pegar um ladrão de bolsas, já que é isso que o problema GUARDCOS - Guarda costeira pede para fazer. Mais especificamente, dadas as velocidades dos barcos da guarda costeira e do ladão determinar se ele será pego.

Solução

Esse é um problema bem fácil. Como o barco do bandido se desloca perpendicularmente a costa, em direção ao limite que a guarda costeira pode prende-lo, os guardas podem simplesmente chegar lá primeiro e prender o bandido. Assim basta saber se a guarda chega nesse ponto antes do bandido ou não.

A distância que o barco da guarda costeira percorre (hipotenusa do triângulo) pode ser calculada com o teorema de Pitágoras. Como a velocidade dos barcos é constante e conhecida temos:

Se tempo_guarda < tempo_bandido responda sim, ou seja

dist_guarda = sqrt(12^2 + d^2)
velocidade = distância / tempo => tempo = distancia / velocidade
dist_guarda/v_guarda < 12/v_bandido
dist_guarda * v_bandido < 12*v_guarda

Implementação

 

TRANSP11 - Transporte

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.

Implementação

 

Mais um pouco de Go ai :)

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

8781. Floresta

Olá meus amigos nerds. Como não podemos fazer muito para tirar a lama la do rio Doce, hoje vamos, pelo menos, ajudar a plantar algumas árvores. Já que é isso que o problema 8781. Floresta nos pede para fazer. Mais especificamente, dado o número de árvores que se deseja plantar, queremos saber de quantas formas elas podem ser plantadas, respeitando-se as restrições do problema.

Solução

Esse é essencialmente um problema de matemática. Queremos plantar carvalhos formando um quadriculado (um retângulo cheio de carvalhos dentro). Sejam a e b os lados desse retângulo. Então:

# de carvalhos dentro do retângulo = a*b

Como no centro de cada quadradinho de carvalhos temos que plantar um encalipto. O número de encaliptos plantados será:

# de encaliptos plantados = (a-1)*(b-1)

Assim o número total de árvores plantadas será:

n = ab + (a-1)*(b-1)
= 2ab -a -b + 1

resolvendo em relação a b temos:

2ab - b = n + a - 1
b = (n + a - 1)/(2a - 1)

Ou seja, todos os pares de números inteiros da forma [a, (n+a-1)/(2a-1)] satisfazem as condições do problema. Então é só contar quantos pares desses números existem.

Como retângulos axb e bxa não são considerados como elementos distintos, podemos supor que a <= b, assim:

a <= (n + a - 1)/(2a - 1)

donde tiramos a condição de parada do for: 2*a^2 - 2*a + 1 <= n

Implementação

18542. Tiro ao Alvo

Olá meus amigos nerds. Hoje vamos brincar de tiro ao alvo. Já que é isso que o problema 18542. Tiro ao Alvo nos pede para fazer. Mais especificamente, dadas as posições onde acertamos o alvo, e o tamanho de cada círculo do alvo, determinar quantos pontos nós fizemos. O número de pontos que um tiro alcança é igual ao número de círculos que ele ficou dentro.

Solução

O segredo desse problema é como contar o número de círculos que um tiro está dentro de forma eficiente. E isso não é muito difícil de fazer se lembrarmos que um ponto é interior a circunfência se:

x^2 + y^2 <= r^2

onde x e y são as coordenadas do ponto e r é o raio do círculo.

Testar essa relação para cada ponto e cada raio é ineficiente (O(C*T)). Entretanto, note que, se um ponto é interior a um círculo ele o será a todos os círculos com raios maiores. Então se ordenarmos os círculos pelos seus raios podemos utilizar busca binária para achar a posição em que o ponto deveria estar no array e dessa forma achar quantos círculos tem raio maior que o ponto. Assim:

pontos_ganhos(x,y) = C - posição de (x,y) no array de raios

onde C é o número de círculos.

Implementação

Note que o número de pontos pode não caber em uma variável do tipo int. Temos que usar um long long int (que tem pelo menos 64bits) para conseguir resolver o problema.

Observe, também, o uso da função lower_bound, que indica a posição do array que o valor passado como parâmetro deveria ocupar. lower_bound internamente implementa uma busca binária.

Por fim observe que a diferença entre dois ponteiros (pos - raios) resulta no número de elementos entre eles e não um endereço de memória.

19958. Detectando Colisões

Olá meus amigos nerds. Hoje vamos fazer um algoritmo para detectar se dois retângulos se interceptam ou não. Já que é isso que o problema 19958. Detectando Colisões nos pede para fazer. Mais especificamente, dados dois retângulos, que tem seus lados paralelos aos eixos, determinar se há alguma interseção entre eles.

Solução

O caso geral desse problema, que é determinar se dois polígonos tem pontos de interseção é bem complexo. Para nos ajudar, o problema trata apenas de retângulos e ainda fixa que seus lados são paralelos aos eixos. Ai fica fácil né!

O problema nos fornece os cantos inferior esquerdo e superior direito de cada retângulo. Vamos tentar estabelecer as condições para que os dois retângulos não possam se interceptar.

Caso o canto superior direito de um dos retângulos esteja 'atráz' do canto inferior esquerdo do outro não há como haver interseção pois nesse caso um retângulo 'termina' antes que o outro comece. Da mesma forma, se o canto superior direito de um dos retângulos estiver 'abaixo' do canto inferior esquerdo do outro um dos retângulos terá 'terminado' antes do outro começar. Pensando nas coordenadas x,y desses pontos teríamos (sendo a e b os retângulos):

if (a_sup_dir_x < b_inf_esq_x ||
     a_sup_dir_y < b_inf_esq_y ||
     b_sup_dir_x < a_inf_esq_x ||
     b_sup_dir_y < a_inf_esq_y )
        responda não

A condição acima é necessária. Agora vou mostrar que ela é suficiente. Observe que na situação dos dois cantos superiores da direita estarem no sub espaço acima e a direita dos cantos inferiores, os seguimentos  (a_inf_esq, a_sup_dir) e (b_inf_esq, b_sup_dir) seriam tanto diagonais do retângulo formado pelos pontos (a_inf_esq, b_sup_dir, a_sup_dir, b_inf_esq) quanto dos retângulos originais, mas como as diagonais de um retângulo sempre se interseptam, resulta que esse ponto pertencerá a uma diagonal de cada um dos retângulos a e b e assim eles também se interceptam.

Implementação

18536. Capital

Olá meus amigos nerds. Hoje vamos brincar de arquitetos e ajudar o senhor Bloggs a planejar uma cidade. Já que é isso que o problema 18536. Capital nos pede para fazer. Mais especificamente, nossa tarefa é determinar, se dados quatro valores de área (a1, a2, a3 e a4) determinar se é possível formar um retângulo que tenha area igual a soma das quatro áreas.

Solução

Problemas de geometria costumam ser bastante complexos, mas esse não é muito difícil. Para começar sabemos de duas coisas: o valor de cada uma das quatro áreas e que elas são necessariamente retangulares. Entretanto não conhecemos os lados de cada retângulo (é isso que queremos determinar).

Note que juntar, quatro áreas (retangulares) e formar um retângulo é equivalente a dado um retângulo dividí-lo em quatro outros retângulos. Vamos, então resolver esse problema. Observe a figura abaixo:

Onde temos um retângulo de lados a e b. Observe que:

a = x1 + x2
b = y1 + y2

Sejam A1, A2, A3 e A4 as quatro áreas dadas. Da figura, podemos escrever as áreas como:

x1*y1 = A1
x2*y1 = A2
x1*y2 = A3
x2*y2 = A4

Note que temos quatro variáveis e quatro equações, mas infelizmente esse não é um sistema linear. Mesmo assim podemos isolar y1 nas duas primeiras equações (supondo x1 e x2 diferentes de 0):

y1 = A1/x1
y1 = A2/x2

O que implica:

A1/x1 = A2/x2 => A1*x2 = A2*x1 => A1*x2 - A2*x1 = 0

Fazendo o mesmo para y2:

y2 = A3/x1
y2 = A4/x2

O que implica:
A3/x1 = A4/x2 => A3*x2 = A4*x1 => A3*x2 - A4*x1 = 0

O que resulta no seguinte sistema homogêneo:
A1*x2 - A2*x1 = 0
A3*x2 - A4*x1 = 0

Se o sistema possuir solução única ela será trivial (x1=x2=0). Essa solução não nos serve! Já que supusemos que x1, x2, x3 e x4 eram diferentes de 0 no inicio de nossa dedução. Ou melhor, essa solução indica que não é possível construir o retângulo com as quatro áreas dadas.

Nos resta ainda a possibilidade de esse sistema ter infinitas soluções (lembre-se, um sistema homogêneo nunca é impossível). Nesse caso podemos escolher algum x1, x2, diferentes de 0 (e maiores que 0, já que se tratam de lados de um retângulo). Para isso, o determinante da equação deve ser nulo, ou seja:

A1*A4 == A2*A3

Eu queria dizer que já está resolvido, mas falta ainda uma parte importante. Em nossa discussão supusemos que conhecíamos A1, A2, A3 e A4, mas na realidade não conhecemos a ordem em que as áreas devem ser testadas na equação acima, sendo assim temos que testar todas as permutações para ter certeza que alguma satisfaz a equação.

Implementação

Quem vê esse código até pensa que o problema é muito fácil! Ledo engano...

11009. O mar não está para peixe

Olá meus amigos nerds, hoje vamos ajudar nossos queridos amigos pescadores a saber qual é a área do mar que suas redes são capazes de cobrir. Já que é isso que o problema 11009. O mar não está para peixe nos pede.

Mais especificamente dadas as dimensões de cada rede e o local onde cada uma delas é jogada desejamos determinar a área do mar que essas redes cobrem.

Solução

Esse é um problema que considero interessante, já que o caso geral dele, que é calcular a área da sobreposição de figuras geométricas arbitrárias, é um problema bastante complexo. Entretanto o problema 11009 é fácil devido a duas restrições:

• As redes são retangulares
• As dimensões das redes são números inteiros

Assim, podemos tratar o mar como um grid, onde cada célula tem área 1. Após isso basta marcar as posições ocupadas pelas redes e depois contar quantos quadradinho de área 1 temos no grid. Essa abordagem tem custo quadrático, mas o tamanho da entrada é pequeno (100) isso é suficiente para que o problema seja aceito.

Implementação

817. Dobradura

Olá meus amigos nerds, não se preocupem que eu ainda não esqueci que estou devendo a vocês um post explicando melhor o funcionamento de uma segtree. Como ainda não consegui fazer um post que me agradasse isso vai ficar na minha todo list por mais um tempo.

Enquanto isso, vamos brincar de dobraduras? Hoje vamos ajudar os amigos de Zezinho a resolver o desafio proposto por ele. Como Zezinho gosta muito de matemática, resolveu inventar um quebra-cabeça envolvendo dobraduras. Zezinho definiu uma operação de dobradura D que consiste em dobrar duas vezes uma folha de papel quadrada de forma a conseguir um quadrado com 1/4 do tamanho original. Depois de repetir N vezes esta operação de dobradura D sobre o papel, Zezinho cortou o quadrado resultante com um corte vertical e um corte horizontal e desafiou seus colegas a dizer em quantos pedaços o papel ficou dividido.

Solução

Nesse tipo de problema, geralmente, é possível deduzir uma fórmula fechada para a resposta. E é precisamente isso que vamos fazer agora. Para isso, vamos usar uma técnica que você, provavelmente, já ouviu falar em suas aulas de algoritmos: indução finita.

para N = 0  =>  4   pedaços (o papel não é dobrado)

para N = 1  =>  9   pedaços
para N = 2  =>  25 pedaços

...

Agora vem a parte difícil, que é sacar qual é o padrão oculto nessa sequência de números. A pergunta é: o que 4, 9 e 25 tem em comum. Bem em primeiro lugar eles são quadrados perfeitos. Ok, mas qual a relação deles com n? Ou melhor, qual seria a relação de 2, 3 e 5 com 0, 1 e 2?

Observe que a cada dobra do papel o número de pedaços de papel dobra. Isso sugere que a relação existente tem que ser uma relação exponencial. Depois de pensar um pouco (ou melhor, depois de esperimentar muito) a gente chega a seguinte relação:

f(n) = (2^n + 1)^2

Agora é que começa a aplicação da indução finita. Observe que a fórmula acima vale para N = 0, pois:

f(0) = 4 = (2^0 + 1)^2

... Poderíamos continuar supondo que a fórmula vale para N e tentando a partir disso resolver a fórmula para N+1. Entretanto, nesse problema isso é bem difícil e eu vou deixar isso para vocês pensarem (dica: comece pensando em quantos pedaços o papel fica dividido após as dobras e depois pense me quantos pedaços cada dobra é dividida quando cortamos o papel). Em uma maratona de programação, o que você faria se tivesse boa confiança na sua fórmula mas não conseguisse prova-la formalmente? Sim, isso mesmo, você implementaria o problema já que ele não é difícil de implementar e submeteria. Nesse caso, se você fizer o mesmo, você será recompensado com uma resposta certa.

Implementação

Observe que, como a entrada é pequena, podemos pré calcular todos os valores e armazena-los em um vetor. Nesse problema isso não faz diferença, mas em outros problemas com tempo de execução mais apertado isso pode ser a diferença entre seu problema passar ou tomar TLE.

1824. Monitorando a Amazônia

Olá meus amigos nerds, vocês acharam que essa semana não ia ter um probleminha? Se sim, se enganaram! Eu queria ter postado esse probleminha na quarta, mas vocês hão de convir comigo que seria uma pena perder os jogos dos dois melhores times do Brasil da atualidade... Deixando de papo furado, que a diversão comece!

Hoje vamos resolver o problema 1824. Monitorando a Amazônia, que nos pede para verificar se é possível enviar uma mensagem de uma estação de comunicação central para todas as outras estações de comunicação espalhadas pela amazônia. Sendo que, cada estação se comunica apenas com as duas estações mais próximas a ela.

Solução

Conceitualmente esse não é um problema difícil. Se pensarmos a rede de comunicação como sendo um grafo (direcionado), basta verificarmos se todos os vértices são alcançáveis, a partir do vértice que representa a estação central. Isso pode ser feito, facilmente, usando-se uma busca em profundidade. 

Note que, o problema pede apenas para verificar se é possível enviar uma mensagem a partir da estação central. Caso se pedisse para verificar a viabilidade da comunicação entre qualquer par de estações, o problema seria um pouco mais complexo. Nesse caso teríamos que verificar se o grafo possuía apenas um componente fortemente conectado, o que poderia ser feito usando-se o algoritmo de Tarjan.

O seguinte algoritmo resolve o problema

calcule a distância entre cada par de estações
Seja G um grafo onde os vértices representam as estações
para cada estação
    Sejam a e b as estações mais próximas a est
    adicione a aresta est -> a a G
    adicione a aresta est -> b a G
faça uma busca em profundidade a partir do vértice que representa a estação principal marcando todos os vertices visitados
if todos os vértices foram marcados
    print "All stations are reachable."
else
    print "There are stations that are unreachable."

Implementação

Observe que evitamos o uso de números de ponto flutuante trabalhando com o quadrado da distância. Em alguns problemas isso pode ser bem útil.

Observe ainda, que abrimos mão de alguma elegância no código em favor de não armazenar as distâncias entre cada par de estações. Sendo assim vou aproveitar e deixar um pequeno desafio para você: o código abaixo contém 2 bugs, quanto tempo você levaria para encontrá-los?

Obs: Caso você tenha dificuldade em encontrar os bugs use o diff :)