Submission #19346819


Source Code Expand

Copy
#include <iostream>
#include <cassert>
using namespace std;
using ll = int64_t;
using long_ = __int128;

long_ myabs(long_ x) {
  return x < 0 ? -x : x;
}

// 1110 = 14 = 16-2
// 
// 
// 111 100N

// Express d as a minimal number of 1,2,...,2**k
// It's allowed to use negative steps!
ll solve(ll d, ll k) {

  if(d==0) { return 0LL; }
  ll pk = 1LL<<k;
  //ll pk1 = 1LL<<(k-1);
  //cerr << " d=" << d << " k=" << k << " pk=" << pk << " pk1=" << pk1 << endl;
  assert(0 <= d && d<pk);
  ll ans = 0;
  ll ones = 0;
  for(ll i=k; i>=0; i--) {
    ll pi = (1LL<<i);
    if(d >= pi) {
      d -= pi;
      ones++;
    } else {
      ans += min(ones, static_cast<ll>(2));
      ones = 0;
    }
  }
  ans += min(ones, static_cast<ll>(2));

  /*ll ans = (d>=pk1 ? 1+solve(d-pk1, k-1) : solve(d, k-1));
  if(pk-d < pk1) {
    ans = min(ans, 1+solve(pk-d, k-1));
  }*/
  return ans;
}
// Min number of steps to make d, stepping by 1,2,...,2**k
ll f(ll d, ll k) {
  ll pk = 1LL<<k;
  ll ans = d/pk;
  d -= ans*pk;

  assert(0<= d && d < pk);
  return ans + solve(d, k);

  // d=7 -> -8 +1 instead of 4 2 1
  /*for(ll i=k; i>=0; i--) {
    ll pi = (1LL<<i);
    while(d >= pi) {
      ans++;
      d -= pi;
    }
  }
  //cerr << "f d=" << old_d << " new_d=" << d << " k=" << k << " ans=" << ans << endl;
  assert(d==0);
  return static_cast<ll>(ans);*/
}

int main() {
  ll X,Y;
  cin >> X >> Y;
  ll ans = static_cast<ll>(2e18);
  for(ll k=0; true; k++) {
    ll pk = (1LL<<k);
    ll Xk = pk*X;
    // Either take steps of 1 -> abs(Y-X)
    // Or multiply by 2 and take steps of 1 or 2 -> 1+f(abs(Y-2X), 2)
    // Or multiply by 4 and take steps of 1,2,4 -> 2+f(abs(Y-4X), 4)
    ans = min(ans, k+f(abs(Y - Xk), k));
    if(Xk > Y) { break; }
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task F - +1-1x2
User jonathanpaulson
Language C++ (GCC 9.2.1)
Score 600
Code Size 1844 Byte
Status AC
Exec Time 9 ms
Memory 3580 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, extreme_04.txt, handmade_00.txt, handmade_01.txt, handmade_02.txt, handmade_03.txt, handmade_04.txt, random_00.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_exp_00.txt, random_exp_01.txt, random_exp_02.txt, random_exp_03.txt, random_exp_04.txt, random_exp_05.txt, random_exp_06.txt, random_exp_07.txt, random_exp_08.txt, random_exp_09.txt, random_exp_10.txt, random_exp_11.txt, random_exp_12.txt, random_exp_13.txt, random_exp_14.txt, random_exp_15.txt, random_small_00.txt, random_small_01.txt, random_small_02.txt, random_small_03.txt, random_small_04.txt, random_small_05.txt, random_small_06.txt, random_small_07.txt, random_small_08.txt, random_small_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
extreme_00.txt AC 9 ms 3576 KB
extreme_01.txt AC 2 ms 3508 KB
extreme_02.txt AC 3 ms 3376 KB
extreme_03.txt AC 3 ms 3504 KB
extreme_04.txt AC 2 ms 3376 KB
handmade_00.txt AC 2 ms 3420 KB
handmade_01.txt AC 2 ms 3376 KB
handmade_02.txt AC 2 ms 3436 KB
handmade_03.txt AC 3 ms 3432 KB
handmade_04.txt AC 2 ms 3544 KB
random_00.txt AC 2 ms 3484 KB
random_01.txt AC 2 ms 3376 KB
random_02.txt AC 2 ms 3560 KB
random_03.txt AC 3 ms 3580 KB
random_04.txt AC 2 ms 3380 KB
random_05.txt AC 2 ms 3564 KB
random_06.txt AC 8 ms 3556 KB
random_07.txt AC 2 ms 3532 KB
random_08.txt AC 2 ms 3436 KB
random_09.txt AC 3 ms 3376 KB
random_exp_00.txt AC 2 ms 3420 KB
random_exp_01.txt AC 2 ms 3568 KB
random_exp_02.txt AC 2 ms 3376 KB
random_exp_03.txt AC 2 ms 3380 KB
random_exp_04.txt AC 2 ms 3540 KB
random_exp_05.txt AC 2 ms 3580 KB
random_exp_06.txt AC 2 ms 3444 KB
random_exp_07.txt AC 2 ms 3420 KB
random_exp_08.txt AC 2 ms 3580 KB
random_exp_09.txt AC 3 ms 3380 KB
random_exp_10.txt AC 2 ms 3564 KB
random_exp_11.txt AC 3 ms 3508 KB
random_exp_12.txt AC 3 ms 3440 KB
random_exp_13.txt AC 2 ms 3436 KB
random_exp_14.txt AC 3 ms 3504 KB
random_exp_15.txt AC 2 ms 3376 KB
random_small_00.txt AC 2 ms 3500 KB
random_small_01.txt AC 3 ms 3488 KB
random_small_02.txt AC 3 ms 3568 KB
random_small_03.txt AC 2 ms 3440 KB
random_small_04.txt AC 2 ms 3500 KB
random_small_05.txt AC 2 ms 3432 KB
random_small_06.txt AC 3 ms 3500 KB
random_small_07.txt AC 6 ms 3492 KB
random_small_08.txt AC 2 ms 3496 KB
random_small_09.txt AC 3 ms 3532 KB
sample_01.txt AC 3 ms 3436 KB
sample_02.txt AC 2 ms 3492 KB
sample_03.txt AC 2 ms 3496 KB