2015 Jan Bronze Problem 3 It's All About the Base

Official Problem Statement

It's All About the Base

Problem

In "It's All About the Base", the problem is described as follows:

The cows are playing with a strange numeral system, where each digit is represented by a different letter. The cow Bessie has given her friend Elsie two positive integers in this numeral system, but she hasn't told Elsie what base this numeral system is using. Bessie then adds these two numbers to get a third positive integer, and gives this to Elsie as well. Now Elsie is wondering: what is the minimum possible base Bessie could be using?

Write a program that determines the minimum possible base that Bessie could be using.

You are given the three positive integers as three separate strings. Each string is at most 15 characters in length and the characters in each string are unique. Bessie can use any base that is greater than or equal to the number of unique digits used in the problem, and the base is at most 36. When the base is larger than 10, the digits 0-9 represent the values 0-9 and the letters A-Z represent the values 10-35.

Solution

One possible solution for this problem is a brute-force search. The base Bessie could be using must be greater than the maximum value of the digit in the three strings. For each base starting from this minimum possible base, we convert the three strings into decimal numbers according to this base, then check if the first two numbers add up to the third number.

Code

C++

#include <iostream>
#include <string>

using namespace std;

// Define a limit for bases to avoid infinite loops
const int BASE_LIMIT = 15000;

// Function to evaluate a 3-digit number in a given base
int evaluate(const string& num, int base) {
  return (num[0] - '0') * base * base +
         (num[1] - '0') * base +
         (num[2] - '0');
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int T; 
  cin >> T;
  
  while (T--) {
    string num_in_x, num_in_y;
    cin >> num_in_x >> num_in_y;

    // Initialize both bases at 10. Increment the base which produces the smaller evaluated result until they yield an equal result.
    int base_x = 10;
    int base_y = 10;
    while (base_x <= BASE_LIMIT && base_y <= BASE_LIMIT) {
      int value_x = evaluate(num_in_x, base_x);
      int value_y = evaluate(num_in_y, base_y);
      
      if (value_x < value_y) {
        base_x++;
      } else if (value_y < value_x) {
        base_y++;
      } else {
        cout << base_x << ' ' << base_y << '\n';
        break;
      }
    }
  }
  return 0;
}

Java

import java.util.Scanner;

public class Main {
    private static final int BASE_LIMIT = 15000;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        while (T-- > 0) {
            String numInX = scanner.next();
            String numInY = scanner.next();

            // Initialize both bases at 10. Increment the base which produces the smaller evaluated result until they yield an equal result.
            int baseX = 10;
            int baseY = 10;
            while (baseX <= BASE_LIMIT && baseY <= BASE_LIMIT) {
                int valueX = evaluate(numInX, baseX);
                int valueY = evaluate(numInY, baseY);

                if (valueX < valueY) {
                    baseX++;
                } else if (valueY < valueX) {
                    baseY++;
                } else {
                    System.out.println(baseX + " " + baseY);
                    break;
                }
            }
        }
    }

    // Function to evaluate a 3-digit number in a given base
    private static int evaluate(String num, int base) {
        return (num.charAt(0) - '0') * base * base +
                (num.charAt(1) - '0') * base +
                (num.charAt(2) - '0');
    }
}

Python

def evaluate(num, base):
    return (ord(num[0]) - ord('0')) * base * base + (ord(num[1]) - ord('0')) * base + (ord(num[2]) - ord('0'))

def find_base():
    T = int(input())
    for t in range(T):
        num_in_x, num_in_y = input().split()

        # Initialize both bases at 10. Increment the base which produces the smaller evaluated result until they yield an equal result.
        base_x = 10
        base_y = 10
        while base_x <= 15000 and base_y <= 15000:
            value_x = evaluate(num_in_x, base_x)
            value_y = evaluate(num_in_y, base_y)

            if value_x < value_y:
                base_x += 1
            elif value_y < value_x:
                base_y += 1
            else:
                print(base_x, base_y)
                break

find_base()