Submission #20343302


Source Code Expand

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

Submission Info

Submission Time
Task D - Base n
User sato11
Language C++ (GCC 9.2.1)
Score 400
Code Size 993 Byte
Status AC
Exec Time 12 ms
Memory 4152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 47
Set Name Test Cases
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
Case Name Status Exec Time Memory
hand_01.txt AC 9 ms 3968 KB
hand_02.txt AC 2 ms 3512 KB
hand_03.txt AC 5 ms 4020 KB
hand_04.txt AC 3 ms 3560 KB
one_digit_01.txt AC 2 ms 3436 KB
one_digit_02.txt AC 2 ms 3560 KB
one_digit_03.txt AC 3 ms 3492 KB
one_digit_04.txt AC 2 ms 3544 KB
one_digit_05.txt AC 2 ms 3560 KB
one_digit_06.txt AC 2 ms 3556 KB
one_digit_07.txt AC 3 ms 3540 KB
one_digit_08.txt AC 3 ms 3556 KB
one_digit_09.txt AC 2 ms 3564 KB
one_digit_10.txt AC 3 ms 3676 KB
one_digit_11.txt AC 2 ms 3488 KB
one_digit_12.txt AC 2 ms 3540 KB
one_digit_13.txt AC 3 ms 3372 KB
one_digit_14.txt AC 6 ms 3560 KB
one_digit_15.txt AC 4 ms 3564 KB
one_digit_16.txt AC 5 ms 3544 KB
random_01.txt AC 3 ms 3508 KB
random_02.txt AC 2 ms 3572 KB
random_03.txt AC 2 ms 3504 KB
random_04.txt AC 2 ms 4068 KB
random_05.txt AC 2 ms 3760 KB
random_06.txt AC 3 ms 4008 KB
random_07.txt AC 3 ms 4072 KB
random_08.txt AC 3 ms 3932 KB
random_09.txt AC 3 ms 3832 KB
random_10.txt AC 4 ms 4072 KB
random_11.txt AC 3 ms 4020 KB
random_12.txt AC 2 ms 3832 KB
random_13.txt AC 2 ms 3696 KB
random_14.txt AC 2 ms 3508 KB
random_15.txt AC 2 ms 3692 KB
random_16.txt AC 2 ms 4056 KB
random_17.txt AC 2 ms 4072 KB
random_18.txt AC 2 ms 4068 KB
random_19.txt AC 3 ms 4084 KB
random_20.txt AC 5 ms 4064 KB
random_21.txt AC 2 ms 4072 KB
random_22.txt AC 2 ms 4024 KB
random_23.txt AC 3 ms 4148 KB
random_24.txt AC 2 ms 4152 KB
sample_01.txt AC 2 ms 3504 KB
sample_02.txt AC 2 ms 3556 KB
sample_03.txt AC 12 ms 4036 KB