Skip to Content
CTRL K

Searching for Soulmates

Análisis oficial (Java) 

Explicación

Para transformar aa en bb, procedemos de forma voraz. Si a>ba > b, se puede mostrar que nunca es óptimo sumar más de una vez de forma consecutiva antes de dividir aa por 2. Para verlo, consideremos sumar dos veces antes de la división. Aunque esto lleva a tres operaciones en total, en su lugar podemos primero dividir y luego solo sumar uno, lo que tiene el mismo efecto pero requiere solo dos operaciones.

Luego, si a<ba < b, como ya se mostró la optimalidad de la estrategia de arriba, la reutilizamos y trabajamos sobre bb permitiendo multiplicación, división y resta de uno. Por tanto, o bien dividimos bb por dos (y primero restamos uno si bb es impar) o restamos bb b−ab - a veces para llegar directamente a aa. Se puede ver que estas operaciones aplicadas sobre bb son equivalentes a lo que se hace sobre aa en orden inverso.

Implementación

Complejidad temporal: O(Nlog⁡max⁡(A,B))\mathcal{O}(N \log{\max(A, B)})

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll solve(ll a, ll b) {
	if (a == b) {
		return 0;
	} else if (a > b) {
		/*
		 * Dividir a de forma voraz hasta que a <= b, sumar 1 si a es impar
		 * para poder dividir.
		 */
		ll is_odd = a % 2;
		return 1 + is_odd + solve((a + is_odd) / 2, b);
	} else {
		/*
		 * En caso contrario, trabajar sobre b para llegar a a por división.
		 * Como alternativa, si es mejor, restar hasta llegar a a.
		 */
		ll is_odd = b % 2;
		return min(b - a, 1 + is_odd + solve(a, b / 2));
	}
}
 
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		cout << solve(a, b) << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class Soulmates {
	public static long solve(long a, long b) {
		if (a == b) {
			return 0;
		} else if (a > b) {
			/*
			 * Dividir a de forma voraz hasta que a <= b, sumar 1 si a es impar
			 * para poder dividir.
			 */
			long isOdd = a % 2;
			return 1 + isOdd + solve((a + isOdd) / 2, b);
		} else {
			/*
			 * En caso contrario, trabajar sobre b para llegar a a por división.
			 * Como alternativa, si es mejor, restar hasta llegar a a.
			 */
			long isOdd = b % 2;
			return Math.min(b - a, 1 + isOdd + solve(a, b / 2));
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
 
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long a = Long.parseLong(st.nextToken());
			long b = Long.parseLong(st.nextToken());
 
			System.out.println(solve(a, b));
		}
	}
}
def solve(a, b):
	if a == b:
		return 0
	elif a > b:
		"""
		Dividir a de forma voraz hasta que a <= b, sumar 1 si a es impar
		para poder dividir.
		"""
		is_odd = a % 2
		return 1 + is_odd + solve((a + is_odd) // 2, b)
	else:
		"""
		En caso contrario, trabajar sobre b para llegar a a por división.
		Como alternativa, si es mejor, restar hasta llegar a a.
		"""
		is_odd = b % 2
		return min(b - a, 1 + is_odd + solve(a, b // 2))
 
 
for _ in range(int(input())):
	a, b = map(int, input().split())
	print(solve(a, b))
Fundamentos