It's All About the Base

Pista 1

Definamos una función $\texttt{to\\_base\\_10}(b, n)$ que convierte nuestro número $n$ que está en base $b$ a base $10$ .

Esta función es monótona. Es decir, para un $b$ fijo y cualquier $n$ :

\texttt{to\\_base\\_10}(b + 1, n) > \texttt{to\\_base\\_10}(b, n)

Pista 2

El problema nos pide encontrar un par $x$ e $y$ que funcione. En lugar de fijar tanto $x$ como $y$ , intentemos fijar solo $x$ .

Solución

Explicación

Para ambos números de entrada $n_1$ y $n_2$ , precomputamos su valor en base $10$ para cada valor de base $i$ . Fijemos nuestro valor de $x$ .

Ahora, el objetivo es encontrar algún $y$ tal que:

\texttt{to\\_base\\_10}(x, n_1) = \texttt{to\\_base\\_10}(y, n_2)

¡Este problema es mucho más manejable! A partir de aquí, hay varias formas de implementar una solución rápida:

Usar dos punteros para llevar el valor de $y$ más relevante en cada paso
Usar una estructura de datos como un std::map para guardar todos los valores precomputados de $n_2$
Guardar los valores precomputados en base $10$ en un arreglo y usar búsqueda binaria para encontrar nuestro candidato posible de $y$

Todos estos enfoques se basan en la misma idea, solo que implementada de forma distinta.

Implementación 1

Complejidad temporal: $\mathcal{O}(KM)$ , donde $M$ es el valor máximo posible de la base.

C++JavaPython


#include <bits/stdc++.h>
 
constexpr int MAX_BASE = 15'000;
 
 
/** @return the given number in base 10 */
int to_base_10(int base, const std::string &num) {
	return (num[0] - '0') * base * base + (num[1] - '0') * base + (num[2] - '0');
}
 
int main() {
	std::freopen("whatbase.in", "r", stdin);
	std::freopen("whatbase.out", "w", stdout);
 
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		std::string in_x, in_y;
		std::cin >> in_x >> in_y;
 
		// iterate on x, move a pointer on y
		int y = 10;
		for (int x = 10; x <= MAX_BASE; x++) {
			const int cur = to_base_10(x, in_x);
 
			// we want to_base_10(y, in_y) to equal cur
			// bigger y results in a bigger to_10(y, in_y)
			// thus, we increase y as necessary
			while (to_base_10(y, in_y) < cur) { y++; }
 
			if (y <= MAX_BASE && to_base_10(y, in_y) == cur) {
				std::cout << x << ' ' << y << '\n';
				break;
			}
		}
	}
}


import java.io.*;
import java.util.*;
 
public class WhatBase {
	private static final int MAX_BASE = 15_000;
 
	/** @return the given number in base 10 */
	private static int toBase10(int base, String num) {
		return (num.charAt(0) - '0') * base * base + (num.charAt(1) - '0') * base +
		    (num.charAt(2) - '0');
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("whatbase.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("whatbase.out"));
 
		int testNum = Integer.parseInt(br.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String inX = st.nextToken();
			String inY = st.nextToken();
 
			// iterate on x, move a pointer on y
			int y = 10;
			for (int x = 10; x <= MAX_BASE; x++) {
				final int cur = toBase10(x, inX);
 
				// we want toBase10(y, inY) to equal cur
				// bigger y results in a bigger toBase10(y, inY)
				// thus, we increase y as necessary
				while (toBase10(y, inY) < cur) { y++; }
 
				if (y <= MAX_BASE && toBase10(y, inY) == cur) {
					pw.println(x + " " + y);
					break;
				}
			}
		}
 
		br.close();
		pw.close();
	}
}


import sys
 
MAX_BASE = 15_000
 
 
def to_base_10(base, num):
	return int(num[0]) * base * base + int(num[1]) * base + int(num[2])
 
 
sys.stdin = open("whatbase.in", "r")
sys.stdout = open("whatbase.out", "w")
 
test_num = int(sys.stdin.readline())
for _ in range(test_num):
	in_x, in_y = sys.stdin.readline().split()
 
	# iterate on x, move a pointer on y
	y = 10
	for x in range(10, MAX_BASE + 1):
		cur = to_base_10(x, in_x)
 
		# we want to_base_10(y, in_y) to equal cur
		# bigger y results in a bigger to_base_10(y, in_y)
		# thus, we increase y as necessary
		while to_base_10(y, in_y) < cur:
			y += 1
 
		if y <= MAX_BASE and to_base_10(y, in_y) == cur:
			print(x, y)
			break

Implementación 2

Complejidad temporal: $\mathcal{O}(KM)$ , donde $M$ es el valor máximo posible de la base.

C++JavaPython


#include <bits/stdc++.h>
 
constexpr int MAX_BASE = 15'000;
 
int to_base_10(int base, const std::string &num) {
	return (num[0] - '0') * base * base + (num[1] - '0') * base + (num[2] - '0');
}
 
int main() {
	std::freopen("whatbase.in", "r", stdin);
	std::freopen("whatbase.out", "w", stdout);
 
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		std::string in_x, in_y;
		std::cin >> in_x >> in_y;
 
		// maps to_base_10(y, in_y) to y
		std::unordered_map<int, int> y_vals;
		for (int y = 10; y <= MAX_BASE; y++) { y_vals[to_base_10(y, in_y)] = y; }
 
		for (int x = 10; x <= MAX_BASE; x++) {
			const int cur = to_base_10(x, in_x);
			if (y_vals.find(cur) != y_vals.end()) {
				std::cout << x << ' ' << y_vals[cur] << '\n';
				break;
			}
		}
	}
}


import java.io.*;
import java.util.*;
 
public class WhatBase {
	static final int MAX_BASE = 15000;
 
	static int toBase10(int base, String num) {
		return (num.charAt(0) - '0') * base * base + (num.charAt(1) - '0') * base +
		    (num.charAt(2) - '0');
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("whatbase.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("whatbase.out"));
 
		int testNum = Integer.parseInt(br.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String inX = st.nextToken();
			String inY = st.nextToken();
 
			// maps to_base_10(y, in_y) to y
			Map<Integer, Integer> yVals = new HashMap<>();
			for (int y = 10; y <= MAX_BASE; y++) { yVals.put(toBase10(y, inY), y); }
 
			for (int x = 10; x <= MAX_BASE; x++) {
				int cur = toBase10(x, inX);
				if (yVals.containsKey(cur)) {
					pw.println(x + " " + yVals.get(cur));
					break;
				}
			}
		}
 
		br.close();
		pw.close();
	}
}


import sys
 
MAX_BASE = 15_000
 
 
def to_base_10(base, num):
	return int(num[0]) * base * base + int(num[1]) * base + int(num[2])
 
 
sys.stdin = open("whatbase.in", "r")
sys.stdout = open("whatbase.out", "w")
 
test_num = int(sys.stdin.readline())
for _ in range(test_num):
	in_x, in_y = sys.stdin.readline().split()
 
	y_vals = {to_base_10(y, in_y): y for y in range(10, MAX_BASE + 1)}
 
	for x in range(10, MAX_BASE + 1):
		cur = to_base_10(x, in_x)
		if cur in y_vals:
			print(x, y_vals[cur])
			break