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;
}

以上就是關(guān)于【USACO 2015 January Contest, Bronze Problem 3. It's All About the Base】的解答，如需了解學(xué)校/賽事/課程動態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學(xué)申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結(jié)、報名門檻收緊、晉級規(guī)則重塑...你準備好了嗎？