提出 #20343302

ソースコード 拡げる

#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;
using ll = long long;

bool f(string s, ll n, ll base)
{
  ll answer = 0;
  int i = 0;
  for (auto it = s.rbegin(); it != s.rend(); ++it)
  {
    ll cur = pow(base, i++) * (*it - '0');
    if (answer > n - cur) return false;
    answer += cur;
  }
  return answer <= n;
}

ll binary_search(string x, ll n, ll imin, ll imax)
{
  if (imax < imin)
    return imin;
  ll imid = imin + (imax - imin) / 2;
  if (f(x, n, imid))
    return binary_search(x, n, imid + 1, imax);
  else
    return binary_search(x, n, imin, imid - 1);
}

ll Solve(string x, ll n)
{
  if (x.size() == 1)
  {
    int m = stoi(x);
    return m <= n;
  }
  int d = *max_element(x.begin(), x.end()) - '0';
  ll imin = 1, imax = 1e18;
  return max(0LL, binary_search(x, n, imin, imax) - d - 1);
}

int main() {
  string x; ll m;
  cin >> x >> m;
  cout << Solve(x, m) << endl;
  return 0;
}

提出情報

提出日時
問題 D - Base n
ユーザ sato11
言語 C++ (GCC 9.2.1)
得点 400
コード長 993 Byte
結果 AC
実行時間 12 ms
メモリ 4152 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 47
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, one_digit_01.txt, one_digit_02.txt, one_digit_03.txt, one_digit_04.txt, one_digit_05.txt, one_digit_06.txt, one_digit_07.txt, one_digit_08.txt, one_digit_09.txt, one_digit_10.txt, one_digit_11.txt, one_digit_12.txt, one_digit_13.txt, one_digit_14.txt, one_digit_15.txt, one_digit_16.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 9 ms 3968 KiB
hand_02.txt AC 2 ms 3512 KiB
hand_03.txt AC 5 ms 4020 KiB
hand_04.txt AC 3 ms 3560 KiB
one_digit_01.txt AC 2 ms 3436 KiB
one_digit_02.txt AC 2 ms 3560 KiB
one_digit_03.txt AC 3 ms 3492 KiB
one_digit_04.txt AC 2 ms 3544 KiB
one_digit_05.txt AC 2 ms 3560 KiB
one_digit_06.txt AC 2 ms 3556 KiB
one_digit_07.txt AC 3 ms 3540 KiB
one_digit_08.txt AC 3 ms 3556 KiB
one_digit_09.txt AC 2 ms 3564 KiB
one_digit_10.txt AC 3 ms 3676 KiB
one_digit_11.txt AC 2 ms 3488 KiB
one_digit_12.txt AC 2 ms 3540 KiB
one_digit_13.txt AC 3 ms 3372 KiB
one_digit_14.txt AC 6 ms 3560 KiB
one_digit_15.txt AC 4 ms 3564 KiB
one_digit_16.txt AC 5 ms 3544 KiB
random_01.txt AC 3 ms 3508 KiB
random_02.txt AC 2 ms 3572 KiB
random_03.txt AC 2 ms 3504 KiB
random_04.txt AC 2 ms 4068 KiB
random_05.txt AC 2 ms 3760 KiB
random_06.txt AC 3 ms 4008 KiB
random_07.txt AC 3 ms 4072 KiB
random_08.txt AC 3 ms 3932 KiB
random_09.txt AC 3 ms 3832 KiB
random_10.txt AC 4 ms 4072 KiB
random_11.txt AC 3 ms 4020 KiB
random_12.txt AC 2 ms 3832 KiB
random_13.txt AC 2 ms 3696 KiB
random_14.txt AC 2 ms 3508 KiB
random_15.txt AC 2 ms 3692 KiB
random_16.txt AC 2 ms 4056 KiB
random_17.txt AC 2 ms 4072 KiB
random_18.txt AC 2 ms 4068 KiB
random_19.txt AC 3 ms 4084 KiB
random_20.txt AC 5 ms 4064 KiB
random_21.txt AC 2 ms 4072 KiB
random_22.txt AC 2 ms 4024 KiB
random_23.txt AC 3 ms 4148 KiB
random_24.txt AC 2 ms 4152 KiB
sample_01.txt AC 2 ms 3504 KiB
sample_02.txt AC 2 ms 3556 KiB
sample_03.txt AC 12 ms 4036 KiB