У Василия есть число a, которое он хочет превратить в число b. Для этого он может производить два типа операций:

умножить имеющееся у него число на 2 (то есть заменить число x числом 2·x);
приписать к имеющемуся у него числу цифру 1 справа (то есть заменить число x числом 10·x + 1).
Вам надо помочь Василию получить из числа a число b с помощью описанных операций, либо сообщить, что это невозможно.

Обратите внимание, что в этой задаче не требуется минимизировать количество операций. Достаточно найти любой из способов получить из числа a число b.

Входные данные
В первой строке записаны два целых положительных числа a и b (1 ≤ a < b ≤ 10⁹) — число, которое есть у Василия, и число, которое он хочет получить.

Выходные данные
Если получить число b из числа a невозможно, выведите «NO» (без кавычек).

В противном случае в первую строку выведите «YES» (без кавычек). Во вторую строку выведите число k — количество чисел в последовательности превращений. В третьей строке выведите последовательность превращений x1, x2, ..., xk, причём:

x1 должно быть равно a,
xk должно быть равно b,
число xi должно быть получено с помощью одной из двух операций из числа xi - 1 (1 < i ≤ k).
Если ответов несколько, разрешается вывести любой из них.

Идея решения: идти не от \( a \) к \( b \), а наоборот — от \( b \) к \( a \). Так проще понять, какая операция могла быть последней.

Если последнее действие было умножением на \( 2 \), то текущее число делится на \( 2 \). Значит, назад нужно разделить на \( 2 \).

Если последнее действие было приписыванием цифры \( 1 \), то число оканчивается на \( 1 \). Значит, назад нужно убрать последнюю цифру: \( x \to \frac{x - 1}{10} \).

Алгоритм:

• создать список и положить в него \( b \);
• пока \( b > a \):
• если \( b \) оканчивается на \( 1 \), заменить \( b \) на \( \frac{b - 1}{10} \);
• иначе если \( b \) делится на \( 2 \), заменить \( b \) на \( \frac{b}{2} \);
• иначе ответ NO;
• после каждого шага добавлять новое число в список;
• если в конце получилось \( a \), ответ YES, список нужно развернуть.

Пример кода на C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
long long a, b;
cin >> a >> b;

vector<long long> ans;
ans.push_back(b);

while (b > a) {
if (b % 10 == 1) {
b = (b - 1) / 10;
} else if (b % 2 == 0) {
b /= 2;
} else {
cout << "NO";
return 0;
}
ans.push_back(b);
}

if (b != a) {
cout << "NO";
return 0;
}

reverse(ans.begin(), ans.end());

cout << "YES\n";
cout << ans.size() << "\n";
for (long long x : ans) {
cout << x << " ";
}

return 0;
}

0 0 Пожаловаться