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

 

AJUDE14 - Ajude Aparecido

Olá meus amigos nerds! Hoje nós vamos ajudar nossos amigos doutorandos a saber se eles acertaram a soma da conta do bar, já que é isso que o problema AJUDE14 - Ajude Aparecido pede para fazer. Mais especificamente, dada uma lista com n valores, verificar se os doutorandos acertaram a soma desses valores ou não.

Eu sei que esse problema é trivial, mas ele é só para eu praticar um pouquinho de Go.

Solução

Basta somar todos os números e ver se a soma bate com a soma fornecida. Mais fácil que isso, só mastigar água.

Implementação

 

Go, go, go :)

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

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

11638. Maratona

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.

Implementação

11013. Quadrado mágico

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.

8314. Fórmula 1

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

11631. Número de Envelopes

Olá meus amigos nerds! Para terminar o ano de boas, nada melhor do que resolver um probleminha fácil! Não é? Por isso, hoje vamos contar rotulos de produtos, já que é isso que o problema 11631. Número de Envelopes pede. Mais especificamente, a partir de uma lista de rótulos, queremos calcular o número máximo de envelopes que podemos formar, sendo que cada envelope tem que ter um rótulo de cada produto distinto.

Solução

Obviamente o número máximo de envelopes que podemos ter é igual ao número de rótulos do produto que temos menos rótulos.

Implementação

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

8699. Dentista

Olá meus amigos nerds. O circo político do Brasil está pegando fogo hoje. Por isso vou falar rapidinho, já que há coisas mais interessantes que resolver problemas agora.

Hoje vamos resolver conflitos na agenda do doutor Pedro, já que é isso que o problema 8699. Dentista pede para fazer. Mais especificamente, dada a agenda de Pedro, com todos os horários de consulta, determinar qual é o maior número de consultas que ele consegue atender.

Solução

Uma forma ótima de escolher qual a primeira consulta a atender (de modo a maximizar o número total de consultas atendidas) é escolher aquela que acabaria primeiro. Pois, nesse caso, Pedro ficaria disponível o mais cedo possível para atender uma nova consulta. Aplicando essa ideia recursivamente chegamos a solução do problema.

Dito de um modo mais algorítmico:

Ordene as consultas por tempo de término.
Enquanto a lista de consultas não estiver vazia
    Atenda a primeira consulta da lista.
   Remova da lista cada consulta que o tempo de início é menor que o tempo de término da consulta que Pedro está atendendo no momento (como ele esta ocupado, ele não pode atender essas consultas)

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

3826. Miojo

Olá meus amigos nerds. Quando se mora sozinho, cozinhar passa a ser um problema, principalmente se você não gosta de jogar comida fora e não tem muito tempo livre (eu que o diga kkk). Uma solução para isso é comer besteiras, tipo miojo. Como somos muito bonzinhos, hoje vamos ajudar o pobre do João a preparar miojos. Já que é isso que o problema 3826. Miojo nos pede para fazer. Mais especificamente, dadas duas ampulhetas (os únicos 'relógios' que ele tem), capazes de medir tempos a e b diferentes e o tempo T necessário para se fazer o miojo, determinar qual será o tempo total gasto para preparar o miojo, incluindo o tempo gasto esperando as ampulhetas estarem em um estado capaz de medir o tempo exato do cozimento do miojo.

Solução

Podemos pensar nesse problema como um problema de decisão. Qual das ampulhetas deve ser virada em seguida para que sejamos capazes de medir exatamente T minutos? Como não podemos inferir a resposta para essa questão, temos que tentar todas as possibilidades e ver qual delas resulta em um menor tempo total.

Os únicos instantes que nos interessam seriam os momentos em que viramos uma ampulheta. Podemos começar virando a ampulheta a, a ampulheta b, ou ambas ao mesmo tempo. Quando uma ampulheta acaba de contar, temos duas opções: (1) vira-la e deixar que ela recomece a contar ou (2) virar as duas ampulhetas, assim a outra ira contar o tempo correspondente a parte da areia que já caiu em seu compartimento inferior. Fazendo-se um backtracking, baseado nessas condições somos capazes de calcular o tempo total.

A condição de parada é que uma das ampulhetas seja capaz de medir exatamente T minutos com a areia remanescente em sua parte superior.

Possivelmente esse problema possui uma solução mais elaborada usando-se teoria dos números (mmc, mdc, etc), mas como a solução por força bruta não é difícil de implementar, resolvi testa-la primeiro e ela se mostrou suficientemente boa para o problema receber um acept.

Implementação

2608. Duende Perdido

Olá meus amigos nerds. Hoje vamos ajudar um duende a escapar de um complexo de cavernas. Já que é isso que o problema 2608. Duende Perdido nos pede para fazer. Mais especificamente, dado o mapa de um complexo de cavernas, onde estão marcadas as saídas e salões onde o duende não pode visitar, determinar o menor número de salões que o duende tem que passar para poder atingir uma das saídas.

Solução

Podemos resolver esse problema facilmente, se pensarmos nos salões que o duende pode entrar como sendo vértices de um grafo, de modo que os caminhos entre eles sejam as arestas. Assim, a solução do problema seria, simplesmente, computar o caminho mínimo entre a posição atual do duende e uma das saídas. Poderíamos computar o caminho mínimo usando o algoritmo de dijkstra, mas como o tamanho da entrada do problema é pequeno, uma busca em largura é suficiente.

Implementação

8709. Fusões

Olá meus amigos nerds. Hoje vamos verificar se dois códigos bancários pertencem a um mesmo banco ou não. Já que é isso que o problema 8709. Fusões nos pede para fazer. Mais especificamente, dados uma lista de bancos e uma série de fusões entre dois bancos, responder se dois bancos (identificados por seus códigos bancários) são o mesmo banco ou não.

Solução

Esse é um problema fácil. Já resolvemos alguns problemas bem parecidos aqui no blog. O único desafio aqui é fazer união de conjuntos de modo eficiente. Isso pode ser feito usando uma dijoint set forest que implementa tanto a operação de union quanto de find de forma eficiente (O(1)).

Implementação