Solução Informática Iniciante - Semana 52 - Problema 1

Solução por Lúcio Cardoso

A resposta para o problema é simplesmente $max(|x_1-x_2|, |y_1-y_2|)$ .

Primeiro, note que a distância de $(x_1, y_1)$ para $(x_2, y_2)$ é $|x_1-x_2|$ $+$ $|y_1-y_2|$ . Porém, como há a opção de mudar o valor de ambas as coordenadas do robô ao mesmo tempo, podemos fazer isto no máximo $min(|x_1-x_2|, |y_1-y_2|)$ vezes. Depois disso, teremos que mudar apenas o valor da primeira ou da segunda coordenada do robô, pois alguma das coordenadas do robô já será a mesma que a do destino. Isto é equivalente a andar $max(|x_1-x_2|, |y_1-y_2|)$ vezes.

A complexidade final é, então $O(1)$ . Confira o código para melhor entendimento:

	// Noic - Iniciante - Semana 52 - Problema 1
	// O(1)

	#include <bits/stdc++.h>

	using namespace std;

	int main(void)
	{
	int x1, y1, x2, y2;

	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

	printf("%d\n", max(abs(x1-x2), abs(y1-y2)));
	}

view raw

noic-iniciante-s52-p1.cpp

hosted with ❤ by GitHub