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

 

SOMA13 - Soma de Frações

Olá meus amigos nerds! Enquanto eu não consigo resolver dois problemas que vocês me pediram, para não ficar muito tempo sem escrever vamos resolver um probleminha fácil.

Hoje nós vamos brincar de somar frações, já que é isso que o problema SOMA13 - Soma de Frações pede para fazer. Mais especificamente, dadas duas frações, imprimir a soma delas.

Solução

A soma de duas frações é algo trivial. O único detalhe é que o problema pede para imprimir as frações na forma irredutível (simplificada), isto é, o numerador e o denominador do resultado devem ser primos entre si. Para simplificar uma fração basta dividir o numerador e o denominador da mesma pelo máximo divisor comum de ambos.

Implementação

 

PECA7 - Peça Perdida

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.

Implementação

 

Go, go, go :)

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

MERCADO - Mercado do seu João

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

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

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

3742. Feynman

Olá meus amigos nerds. Hoje vamos resolver um probleminha de matemática, já que é isso que o problema 3742. Feynman pede para fazer. Mais especificamente, quantos quadrados diferentes existem em um quadriculado de N x N quadrados?

Solução

Para responder essa pergunta basta somar quantos quadrados de 1, 2, ..., N existem no quadriculado.

Para descrever um quadrado em um quadriculado é preciso apenas de um ponto: o ponto de início do quadrado, a partir desse ponto todos os outros quadradinhos do quadriculado que o quadrado ocupa ficam determinados.

Dito isso, como o quadriculado tem N x N existem N^2 quadrados de tamanho 1.

Posso começar um quadrado de tamanho 2 em qualquer uma das N linhas e N colunas com excessão da última linha e coluna. Assim existem (N-1)*(N-1) = (N-1)^2 quadrados de tamanho 2.

Já quadrados de tamanho 3 não podem começar nas duas últimas linhas e colunas. Assim teríamos (N-2)*(N-2)=(N-2)^2 quadradinhos de tamanho 3.

...

Por fim existe apenas 1 quadrado de tamanho N.

Em outras palavras:

1 -> N^2
2 -> (N-1)^2
3 -> (N-2)^2
...
N -> 1

Então a resposta é a soma dos quadrados dos números de 1 a N.

Implementação

11629. Competição de chocolate

Olá meus amigos nerds. Hoje vamos brincar (literalmente) de comer bolinhas de chocolate. Já que é isso que o problema 11629. Competiçăo de chocolate nos pede para fazer. Mais especificamente, dado o jogo em que dois jogadores comem bolinhas de chocolate de modo alternado, com a restrição de que há n bolinhas e que um jogador pode comer no máximo m delas de cada vez. Determinar quem ganha o jogo, se o jogador que começou ou o que jogou em segundo lugar. 

Solução

Para quem já conhece, esse jogo é uma variação d Nim. A ideia para resolver esse problema é simples:

a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.

1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).

Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:

n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.

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

20860. Vôo

Olá meus amigos nerds. Hoje vamos ver como fusos horários podem ser problemáticos. Já que é isso que o problema 20860. Voo nos pede para fazer. Mais especificamente, dados os horários de partida e chegada de um voo de ida e de um vôo volta entre duas cidades; determinar o tempo real de vôo bem como a diferença de fusos entre as cidades.

Solução

Quando li o problema achei que ele seria fácil, mas não é bem assim, ele impõe algum desafio. O segredo do problema está em perceber que: se em um trecho a diferença de fusos horários aumenta o tempo de viagem, no outro ela diminui o tempo. Assim se tirarmos a média entre os tempos totais de ida e volta teremos o tempo real de viajem, já que o fuso se cancela.

tempo_real = (tempo_ida + tempo_volta) / 2

Para encontrarmos o fuso bastaria subtrair o tempo real do tempo de ida ou de volta, isto é:

fuso = tempo_ida - tempo_real

Mas isso não resolve completamente o problema, já que, como o próprio problema afirma, as datas não estão completas. Ou seja, não sabemos se a data de chegada é a mesma da de saída ou se refere ao próximo dia. Assim para uma mesma entrada teríamos várias respostas, para desambiguar essas respostas o problema nos garante que a viajem durou menos de 12 horas.

Mas como poderíamos usar esse dado? Se pensarmos bem os tempos de viajem considerando que o avião chegou no mesmo dia e no dia seguinte diferem de no máximo 12 horas. Assim se tomarmos o módulo teremos o tempo pedido. Assim:

tempo_real = (tempo_ida + tempo_volta) / 2 mod 12

Lembrando que o fuso tem que ficar no intervalo -12 < fuso < 12 teríamos:

fuso = tempo_ida - tempo_real mod 24
if fuso > 12
    fuso -= 24

Implementação

3242. Loop musical

Olá meus amigos nerds. Hoje vamos estudar um pouco sobre máximos e mínimos em um gráfico. Já que é isso que o problema 3242. Loop musical nos pede para fazer. Mais especificamente, dado um conjunto de pontos formando um gráfico, determinar quantos mínimos e máximos locais esse gráfico possúi.

Solução

Para quem se lembra das aulas de cálculo, esse é um problema fácil. Mínimos e máximos locais são pontos de inflexão do gráfico, isto é pontos em que a derivada é nula. Isso significa que, dados três pontos, existe pelo menos um mínimo (ou máximo) local entre esses pontos se o sinal da derivada se alterar entre eles. Para que isso ocorra, basta que o ponto do meio seja mais alto, ou mais baixo, que os outros dois pontos.

Então basta testar se isso ocorre e lembrar que no problema os pontos formam um loop, ou seja, o primeiro ponto segue o último ponto.

Implementação