Contest Duration: - (local time) (100 minutes) Back to Home

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 2021-01-10 22:11:52+0900 F - +1-1x2 jonathanpaulson C++ (GCC 9.2.1) 600 1844 Byte AC 9 ms 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