Alsalis
5 год назад
У Василия есть число a, которое он хочет превратить в число b. Для этого он может производить два типа операций:
умножить имеющееся у него число на 2 (то есть заменить число x числом 2·x);
приписать к имеющемуся у него числу цифру 1 справа (то есть заменить число x числом 10·x + 1).
Вам надо помочь Василию получить из числа a число b с помощью описанных операций, либо сообщить, что это невозможно.
Обратите внимание, что в этой задаче не требуется минимизировать количество операций. Достаточно найти любой из способов получить из числа a число b.
Входные данные
В первой строке записаны два целых положительных числа a и b (1 ≤ a < b ≤ 109) — число, которое есть у Василия, и число, которое он хочет получить.
Выходные данные
Если получить число b из числа a невозможно, выведите «NO» (без кавычек).
В противном случае в первую строку выведите «YES» (без кавычек). Во вторую строку выведите число k — количество чисел в последовательности превращений. В третьей строке выведите последовательность превращений x1, x2, ..., xk, причём:
x1 должно быть равно a,
xk должно быть равно b,
число xi должно быть получено с помощью одной из двух операций из числа xi - 1 (1 < i ≤ k).
Если ответов несколько, разрешается вывести любой из них.
ОТВЕТЫ
Erazm
Aug 8, 2019
Данный код делает даже больше - подсчитывает сколькими способами можно перевести начальное число в конечное, и как именно. Формат вывода подогнать не сложно
# Код на ruby 2.2.3p173
def f0(number, log) #
n = 10 * number + 1
log += " + 1 "
log += "[" + n.to_s + "] "
return [n, log]
end
def f1(number, log) #
n = 2 * number
log += " * 2 "
log += "[" + n.to_s + "] "
return [n, log]
end
def f2(number, log) #
n = number + 4
log += " + 4 "
log += "[" + n.to_s + "] "
return [n, log]
end
start_num = 14 # начальное число
end_num = 28 # конечное число
max_steps = end_num
op_numbers = 2
count = 0
for steps in 1..max_steps
for i in 0..op_numbers**steps-1
s = ("000000000000000000000000000000" + i.to_s(op_numbers))[-steps..-1]
num = start_num
log = start_num.to_s
for k in 0..s.size - 1
num, log = f0(num, log) if s[k] == "0"
num, log = f1(num, log) if s[k] == "1"
# num, log = f2(num, log) if s[k] == "2"
break if num gt; end_num
end
# p [num, log, s, steps, i]
if num == end_num
log += " = " + end_num.to_s
count += 1
p log
end
end
end
p count
# Код на ruby 2.2.3p173
def f0(number, log) #
n = 10 * number + 1
log += " + 1 "
log += "[" + n.to_s + "] "
return [n, log]
end
def f1(number, log) #
n = 2 * number
log += " * 2 "
log += "[" + n.to_s + "] "
return [n, log]
end
def f2(number, log) #
n = number + 4
log += " + 4 "
log += "[" + n.to_s + "] "
return [n, log]
end
start_num = 14 # начальное число
end_num = 28 # конечное число
max_steps = end_num
op_numbers = 2
count = 0
for steps in 1..max_steps
for i in 0..op_numbers**steps-1
s = ("000000000000000000000000000000" + i.to_s(op_numbers))[-steps..-1]
num = start_num
log = start_num.to_s
for k in 0..s.size - 1
num, log = f0(num, log) if s[k] == "0"
num, log = f1(num, log) if s[k] == "1"
# num, log = f2(num, log) if s[k] == "2"
break if num gt; end_num
end
# p [num, log, s, steps, i]
if num == end_num
log += " = " + end_num.to_s
count += 1
p log
end
end
end
p count
24
Смежные вопросы:
