Дідусик Морозик та Мерзенна вісімка Дідусик Морозик загадав певне ціле додатне число n.
Визначте, чи можливо зробити це число кратним 8, за умови що дозволяється змінити порядок цифр у числі. Зауважте, що отримане число не повинно містити провідних нулів (які знаходяться лівіше першої ненульової цифри) у своєму записі.
Вхідні дані
Перший рядок містить одне ціле число n (1≤n≤10
10
4
).
Вихідні дані
Якщо неможливо зробити задане число кратним 8, виведіть одне ціле число −1.
Інакше, виведіть число, яке кратне 8 та може бути утворене з n за можливості зміни порядку цифр.
Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.
2. Переливаем все из первого во второй. В первом кувшине 0 л, во втором 3л
3. Повторяем п1. В первом кувшине 3 л, во втором 3л
4. Повторяем п2. В первом кувшине 0 л, во втором 6л
5. Повторяем п1. В первом кувшине 3 л, во втором 6л
6. Переливаем из первого во второй до наполнения второго. В первом кувшине 1 л, во втором 8л
7. Выливаем все из большего кувшина. В первом кувшине 1 л, во втором 0л
8. Повторяем п2. В первом кувшине 0 л, во втором 1л
9. Повторяем поледовательнось п1-п4 два раза, В первом кувшине 0 л, во втором 7л
def shortest_chains(n):
def next_chains(chain):
new_elems = set()
for i in range(len(chain)):
for j in range(i, len(chain)):
new_elem = chain[i] + chain[j]
if new_elem > chain[-1] and new_elem not in new_elems:
new_elems.add(new_elem)
yield chain + [new_elem]
current_stage = None
next_stage = [[1]]
answer = []
while len(answer) == 0:
current_stage = next_stage
next_stage = []
for chain in current_stage:
next_stage.extend(next_chains(chain))
answer = [chain[1:] for chain in next_stage if chain[-1] == n]
return answer
def print_solution(n):
answer = shortest_chains(n)
print("Для {} есть {} решений(-я, -е):".format(n, len(answer)))
for i in range(len(answer)):
print("{}. {}".format(i + 1, " ".join(map(str, answer[i]
print()
Запустив, можно получить все 5 возможных решений для числа 7, по 4 решения для 15 и 23 и 87 решений для 63.