USACO 2015 January Contest, Bronze Problem 3. It's All About the Base

原题下载

USACO2015JAN-B3

答案

(Analysis by Mark Gordon)

This problem gives us two three digit strings and asks us to determine the bases X and Y such that those strings evaluate to the same integer. We are also guaranteed that there is a unique result where X, Y <= 15,000.

There are a number of ways to approach this. However, the naive approach of simply testing each pair of bases X, Y <= 15,000 is too slow and will time out.

A better approach is to compute all integers each input number could evaluate to and find the overlap. An even better approach, shown below, is to observe that a positive number interpreted in base X is larger when interpreted instead in base X+1. This means that what we're really trying to do is find an equal element in two sorted arrays. We can do this simply by incrementing the base that produces the smaller corresponding evaluation until they are equal.

#include <iostream>
#include <cstdio>

using namespace std;

#define MAXB 15000

int evaluate(const string& num, int base) {
  return (num[0] - '0') * base * base +
         (num[1] - '0') * base +
         (num[2] - '0');
}

int main() {
  freopen("whatbase.in", "r", stdin);
  freopen("whatbase.out", "w", stdout);

  int T; cin >> T;
  for (int t = 1; t <= T; t++) {
    string num_in_x, num_in_y;
    cin >> num_in_x >> num_in_y;

    /* Initialize both bases at 10.  Increment the base that produces the
     * smaller evaluated result until they yield an equal result. */
    int X = 10;
    int Y = 10;
    while (X <= MAXB && Y <= MAXB) {
      int num_x = evaluate(num_in_x, X);
      int num_y = evaluate(num_in_y, Y);
      if (num_x < num_y) {
        X++;
      } else if (num_y < num_x) {
        Y++;
      } else {
        cout << X << ' ' << Y << '\n';
        break;
      }
    }
  }
  return 0;
}

以上就是关于【USACO 2015 January Contest, Bronze Problem 3. It's All About the Base】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！