Algorithmen und Datenstrukturen

Zahlentransformation

Emil hat eine Zahl x und möchte sie in eine andere Zahl y umwandeln. Dafür stehen ihm folgende Aktionen zur Verfügung:
  1. Emil kann die aktuelle Zahl x um 1 erhöhen (x = x + 1) und dafür 1 Geldeinheit bezahlen.
  1. Emil kann die aktuelle Zahl x um 1 verringern (wenn x größer als 0 ist) (x = x - 1) und dafür 1 Geldeinheit bezahlen.
  1. Emil kann x mit einer beliebigen positiven ganzen Zahl k multiplizieren (x = k ⋅ x) und dafür 2k Geldeinheiten bezahlen.
  1. Emil kann x durch eine beliebige positive ganze Zahl k teilen, sofern x durch k teilbar ist (x = x / k), und dafür 2k Geldeinheiten bezahlen.
Schreibe ein Programm, das ermittelt, wie viel Geld Emil mindestens bezahlen muss, um x in y zu verwandeln. Außerdem soll es die erforderlichen Aktionen in der Reihenfolge ausgeben, in der sie ausgeführt werden müssen. Beachte, dass es mehrere Möglichkeiten geben kann, diese minimale Summe zu erreichen – du kannst jede davon ausgeben. Zusätzlich muss die Anzahl der Aktionen nicht minimiert werden.

Eingabe

Die Eingabe besteht aus zwei ganzen Zahlen x und y (1 ≤ x, y ≤ 10 000). Sie stehen für Emils Anfangswert und den gewünschten Endwert.

Ausgabe

Die erste Zeile der Ausgabe soll zwei durch Leerzeichen getrennte Zahlen m und n enthalten, wobei m die Anzahl der Aktionen darstellt und n die minimale Geldsumme, die Emil benötigt, um x in y umzuwandeln.
In den nächsten m Zeilen gibst du für jede Aktion der Reihe nach den Index der Operation, , aus. Handelt es sich um Multiplikation oder Division ( oder ), so soll nach der Angabe der Operationsnummer auch die entsprechende Zahl ausgegeben werden (mit einem Leerzeichen dazwischen).

Beispiele

Eingabe
Ausgabe
3 7
4 4 1 1 1 1
10 21
2 5 3 2 1
21 10
2 5 2 4 2
10 32
3 8 3 3 1 1

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue