Блог пользователя rr459595

Автор rr459595, история, 5 лет назад, По-английски

You are given a number x. you have to find the minimum number of steps required to reach n from 1. At a particular point, you have two choices

1) increment the number by 1

2) reverse the integer (remove leading zeros after reversing)

eg: n=42

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>41>42 (15 steps)

The minimum steps to reach 42 from 1 is 15. This can be achieved if we increment numbers by 1 from 1 to 14 (13 steps). After reaching 14 we can reverse the number which will give us 41 (1 step). From 41 we can increment number by 1 to reach 42(1 step). hence total 15 steps which is then minimum

Note that if we reverse the number after reaching 12 or 13, we will not get the minimum steps

1>2>3>4>5>6>7>8>9>10>11>12>21>22>23>32>33>34>35>36>37>38>39>40>41>42 (25 steps)

eg: n=16

sol: 1>2>3>4>5>6>7>8>9>10>11>12>13>14>15>16 (15 steps)

In this case we have to increment the numbers till 16 which will give us the minimum of 15 steps.

Constraints:- 1<=n<=10^14.

I can only think of BFS/DP here which doesn't look like optimal solution.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you provide the link to this problem ?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Let's say the goal is $$$n = 5280$$$. There must be some first moment when we get a 4-digit number and the only possibility is that we increase by one from $$$999$$$ to $$$1000$$$. With the same logic, we must take a step from $$$99$$$ to $$$100$$$ before. So the problem breaks into: how to get from $$$100$$$ to $$$999$$$ optimally (and similar for smaller number of digits), and how to get from $$$1000$$$ to $$$5270$$$. I guess that both parts are about the sum of two halves of a number (first one is reversed). So, I would get $$$5270$$$ from $$$1000$$$ by $$$25$$$ increments first, then reverse, then another $$$70-1 = 69$$$ increments. That's my idea, maybe there are some issues with this.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Thanks for the answer. However, I am not able to prove that your method will indeed give the optimal answer.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

Based on Errichto's hint, I came up with this solution. I don't know if it is right or not, but I think it is.

Let's call all numbers which are of the form 10 ^ r as base numbers. To reach a number X from 1, we first reach a base number having the same number of digits as X. E.g. to reach 32463, we first reach 10000 using some operations. Only then do we think about reaching 32463.

How do we reach a base number? To reach 1000, you must reach 999 and then increment 1. It is the only way to increase the number of digits. Reversing a number won't help. This brings us back to the question of reaching some number X (999) from a base number (100) and so on.

To reach 32463 from 10000, we observe that it is optimal to use the reverse operation at most once. This operation is preceded and followed by some number of increment operations. Thinking backward, we need to solve for 32461 (with last digit 1) and then increment twice to reach X = 32463. The last digit 1 is preserved when we reverse our number. Now for the remaining 4 digits to the left of 1. If we add 6 (tens' place) before reversing, then we shall be adding 6 * 10 ^ 3 to our base number. It is better to add this digit after the reversal, i.e., we will need only to add 6 * 10 ^ 1. By this logic, the first two digits should be added before the reverse operation and the later half afterward. The whole series of operations looks like this:

$$$ 1 -> 99 $$$
$$$ 99 -> 100 $$$
$$$ 100 -> 999 $$$
$$$ 999 -> 1000 $$$
$$$ 1000 -> 9999 $$$
$$$ 9999 -> 10000 $$$
$$$ 10000 -> 10023 (increment __ 23 __ times) $$$
$$$ 10023 -> 32001 (reversal) $$$
$$$ 32001 -> 32461 (increment __ 460 __ times) $$$

To reach from 10000 -> 99999, we use the same logic. First, we reach 10000 -> 10099, reverse to 99001, and then go 99001 -> 99999.

It's a simple pattern with the number of 9s being divided equally into both sides of the reverse operation.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long X;
    cin >> X;
    long long cur = 1, ans = 0;

    auto pow10 = [](int r) -> long long {
        long long base = 1;
        while (r > 0) {
            base *= 10;
            --r;
        }
        return base;
    };
    
    // Increase zeroes until `cur` and `X` have same no. of digits
    while (cur * 10 <= X) {
        long long d = int(log10(cur)) + 1;
        ans += 1 * (cur != 1) + pow10(d / 2) - 1 + pow10((d + 1) / 2) - 1;
        cur *= 10;
    }

    // X is of the form (10 ^ p)
    if (cur == X) {
        cout << ans << endl;
        return 0;
    }

    // If X has last digit 0, solve for (X - 1) and increment one later
    if (X % 10 == 0) {
        --X;
        ++ans;
    }

    // Convert X so that its last digit is 1
    ans += (X % 10) - 1;
    X = X - (X % 10) + 1; 

    long long d = int(log10(X)) + 1;
    assert(d == int(log10(cur)) + 1);

    // Add first half to `cur`
    long long firstHalf = 0;
    for (int i = d / 2; i < d; i++) {
        int digit = (X / pow10(i)) % 10;
        firstHalf = firstHalf * 10 + digit;
    }

    ans += firstHalf;
    cur += firstHalf;

    // reverse `cur` (only if it's not a palindrome)
    long long tmp = cur, old = cur;
    cur = 0;
    while (tmp) {
        cur = cur * 10 + tmp % 10;
        tmp /= 10;
    }
    if (cur != old) ++ans;

    // Add second half to `cur`
    long long secondHalf = 0;
    for (int i = d / 2 - 1; i > 0; i--) {
        int digit = (X / pow10(i)) % 10;
        secondHalf = secondHalf * 10 + digit;
    }
    secondHalf *= 10;

    ans += secondHalf;
    cur += secondHalf;

    assert(cur == X);
    cout << ans << endl;

    return 0;
}