読者です 読者をやめる 読者になる 読者になる

ACM-ICPC World Finals 2016 E解法

E: Forever Young

問題

私はY歳です。
適切なBを求めて、「YをB進数で表した時全ての桁は0~9であり、その表示を十進数とみなすとL以上である」ようにしなさい。
その最大のBを出力しなさい。

制約

10 <= Y <= 10^18
10 <= L <= Y

解法

Bを1つ選んでYのB進数表示を求めるのは簡単。しかし現実的な時間では精々B <= 10^6 ~ 10^7 程度までである。
Bが10^6より大きい時にそのB進数表示は3桁以下である。なぜなら4桁目が1以上ならば元の数がB^3以上でありYの上限を超えるから。
よって平方分割(立法分割?)が適している。
3桁の表示が全て0~9の場合を決めて、逆にBを方程式を解くなり、二分探索を行うなり求める。

コード

汚い。チーム戦なら解を洗練してからコーディングするべき。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

LL Y, L;

int main() {
    scanf("%lld%lld", &Y, &L);

    LL ans = 10;

    for (LL b = 11; b <= 1000000; b++) {
	LL yy = Y;
	LL d = 0, t = 1;

	bool ok = true;

	while (yy) {
	    if (yy % b >= 10) {
		ok = false;
		break;
	    }

	    d += (yy % b) * t;
	    t *= 10;
	    yy /= b;
	}

	if (ok && d >= L) {
	    amax(ans, b);
	}
    }

    REP (a0, 10) REP (a1, 10) REP (a2, 10) REP (a3, 10) {
	if (a3 * 1000 + a2 * 100 + a1 * 10 + a0 < L) continue;

	LL lo = 10, hi = 2e18 + 10;
	while (hi - lo > 1) {
	    LL m = (hi + lo) >> 1;
	    double d = m;

	    if (a3 * d * d * d + a2 * d * d + a1 * d + a0 > 2e18) hi = m;
	    else if (a3 * m * m * m + a2 * m * m + a1 * m + a0 > Y) hi = m;
	    else lo = m;
	}

	LL m = lo;
	if (a3 * m * m * m + a2 * m * m + a1 * m + a0 == Y) {
	    amax(ans, m);
	}
    }
    printf("%lld\n", ans);

    return 0;
}