Solução Informática - Nível Iniciante - Semana 33

Solução escrita por Vitor Veiga

Conhecimento prévio necessário:

• Loops

Resumindo o problema, temos duas posições $(a, b)$ e $(c, d)$ representadas em um eixo cartesiano e queremos o menor número possível de movimentos dos tipos $(x, y) \rightarrow (x + 1, y + 1)$ ou $(x, y) \rightarrow (x - 1, y)$ (vai uma casa para nordeste ou para oeste) para ir da primeira até a segunda posição.

Dessa forma, vamos dividir o problema em duas partes. Primeiro temos que garantir que, no eixo y, Andremfq não está acima da medalha, pois é impossível ir para baixo no eixo y. Cumprindo essa condição, vamos calcular quantos movimentos do tipo 1 $(x + 1, y+1)$ são necessários para chegar na ordenada da medalha, $d - b$.

Depois, Andremfq estará na posição $(a + (d - b), d)$ que, para que seja possível chegar no destino, não pode estar à esquerda da medalha, pois caso ele realizasse um movimento do tipo 1, indo para a direita, ele também estaria saindo da ordenada da medalha, sem possibilidade de voltar. Então calculamos quantos movimentos $(x - 1, y)$ ele deve fazer para chegar na medalha, $a + (d - b) - c$.

Retornamos então o número total de movimentos $(d - b) + a + (d - b) - c = a - 2b - c + 2d$. Segue o passo a passo do segundo caso teste:

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.