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

19949. Fechadura

Olá meus amigos nerds. Hoje vamos brincar de abrir fechaduras. Já que é isso que o problema 19949. Fechadura nos pede para fazer. Mais especificamente, dados uma serie de números (que representam a altura dos pinos da fechadura) e uma posição em que os pinos tem que ser colocados para que a fechadura se abra, determinar qual o número mínimo de movimentos de elevar ou abaixar os pinos para que a fechadura se abra.

Solução

Quando li esse problema pela primeira vez, achei que sua solução envolveria programação dinâmica, já que ele pedia o menor número de movimentos. Entretanto se observarmos bem, o problema afirma que quando um pino é mexido o da frente também o é. Assim, não há o que otimizar, basta percorrer o vetor com as alturas (armazenando o número de movimentos gastos para mover o pino anterior) e ir somando o número de movimentos necessários.

Seja 'altura' o vetor com as alturas dos pinos
Seja m a altura que devemos colocar os pinos
soma_mov = 0
acum = 0
for altura in alturas
        diff = m - (altura + acum)
        soma_mov += abs(diff)
        acum = diff

Implementação

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

18543. Vende-se

Olá meus amigos nerds. Esse mês demorei um pouco a dar as caras por aqui, mas foi por uma boa causa, estava escrevendo um paper :P algo que eu não fazia há muito tempo. E não seria um paper se eu não tivesse que ficar escrevendo e reescrevendo tudo até de madrugada. Vocês não acham? kkk.

Hoje ajudar vamos ajudar nossos amigos da obi a vender algumas casas. Já que é isso que o problema 18543. Vende-se nos pede para fazer. Mais especificamente, (por culpa da Dilma) a obi precisa vender alguns de seus imóveis e quer que os que restarem estejam  o mais próximos possível, ou seja, que a distância entre o primeiro e o último prédios restantes deve ser a menor possível.

Solução

Devo dizer que esse é um problema fácil e quase não tive vontade de escrever sobre ele. Mas esse foi o único problema que eu resolvi essa semana. Então vai ter que servir.

Devemos perceber que as casas restantes serão necessariamente consecutivas (pensando na distância para o início da rua). É só você pensar que para vender uma casa no 'meio' das que restaram, uma casa fora da sequência não poderia ser vendida, mas a distância dessa casa para a casa do canto oposto das que sobraram aumentaria.

Assim basta ordenar as casas pela distância. E percorrer a lista de casas computando a distância pedida.

Implementação

Me desculpem pelo código feio, mas é que eu o fiz enquanto assistia uma palestra chata sobre devops :P