Программисты, ходите на собеседования

Было как-то одно занимательное интервью, дали задачку на два с половиной часа. «Осенило» решением только под конец второго часа, но собес провалил по иным причинам.
Собственно, задача:

Есть два регистра: R1 и R2
Есть две команды:
C1: R1 := K*R2 — R1
C2: R2 := K*R1 + R2
Есть целевое число N
На входе: K, N, R1, R2
Нужно: распечатать минимальную последовательность из команд, позволяющую получить N в R1 или в R2 (в любом из двух регистров)
Либо напечатать ничего
Известно, что K != 0, R1 != R2, K, R1, R2 — натуральные, N — целое.