Нужна помощь с задачей

x убывает как минимум в 3 раза с каждой итерацией.
Для a=5 нужны чётные x, дающие в сумме остатков от деления на 3 - 5, т.е., как минимум, три слагаемых (1+2+2).
Для b=9 нужны нечётные x, дающие в сумме остатков от деления на 5 - 9, т.е. не менее трёх слагаемых (1+4+4, 2+3+4 или 3+3+3). Порядок слагаемых, естественно, неважен, главное - набрать сумму за 3 слагаемых.
Итого, не менее 6 итераций цикла, на последней из которых x = 1 или 2, а на первой, соответственно, более 3⁵ = 243.

Например, обратным счётом (таблица (1)):

 x   Инкремент

2     a   +2

7     b      +2

23    b      +3

69    b      +4

208   a   +1

626   a   +2 

Так мы получаем нужные значения a и b за минимальное количество шагов (6).
Можно ли ещё уменьшить x путём взятия меньших остатков от деления на 3?

Допустим, на последней итерации x = 1. Перебираем возможные значения x на предпоследней итерации (их 3). Перебор останавливаем, как только не удалось набрать слагаемые для a из (1, 2, 2) или для b из (1, 4, 4), (2, 3, 4) или (3, 3, 3), в любом порядке, поскольку "неправильное" слагаемое потребует лишней итерации, а лишнее умножение x на 3 сразу выведет его за границу найденного минимума (т.к. на семи итерациях начальное x будет не менее 3⁶ = 729).

Но все варианты x теперь будут включать 2 нечётных значения (x * 3 и x * 3 + 2) и 1 чётное (x * 3 + 1), которое даёт для a остаток 1. А нам для a приемлем только остаток 2. Поэтому это - тупиковый путь. Значит, последний x = 2.

Смотрим предпоследнюю итерацию:

 x  Инкремент

6   a  +0

7   b     +2

8   a  +2 

Подходят второе и третье значения. Из нечётного x=7 мы можем выйти только один раз, поэтому пока не вышли, можно либо набирать инкременты для b, а только потом переходить к a, получив один раз +1 и один раз +2. Именно это делает схема, приведённая выше. Либо можно один раз выйти из нечётных x, а потом туда вернуться.

Рассмотрим путь с набором сначала инкрементов для b. Попробуем на третьей с конца итерации взять другое нечётное x: x = 7 * 3 = 21. Инкремент b+1, недопустим (т.к. мы уже пошли путём (2, 3, 4)). На четвёртой с конца - можно ли взять 23 * 3 + 2 = 71? Это опять приведёт к +1 для b. А на двух первых итерациях задача ещё проще: надо взять чётные значения, дающее подходящие остатки для a (1 и 2 по одному разу). Несложно видеть, что такая комбинация только одна.

А если пойти путём x=22, a+1? Тут нужно сразу взять инкремент a+2, т.к. потом вернуться к чётным x уже не сможем. И дальше набирать +3, +4 для b. Выходит не более одного пути:

 x  Инкремент

22  a  +1

66  a  +2

199 b    +4

597 b    +2   (или 599 b   +4) 

К первой итерации мы поставлены перед выбором из двух недопустимых инкрементов для b: один даёт b=8, другой - b=10, а нам нужно b=9. Тупик.

Рассмотрим на предпоследней итерации случай x=8 и 3-ю с конца итерацию с ним:

 x  Инкремент

24  a  +0

25  b    +0

26  a  +2 

Первые два инкремента недопустимы, а третий делает a=6, поэтому тоже недопустим. Тупик.

Итак, наименьшее x=626 достигается таблицей (1) за 6 итераций, а другие пути ведут к увеличению количества итераций, и соответственно, к большим x.

Для наглядности можно нарисовать дерево с корнем в (x=0), глубиной 7 и ветвлениями на x * 3, x * 3 + 1, x * 3 + 2 на каждом уровне. Вычёркиваем все тупиковые пути и выбираем наименьший x по коротким путям.