Das Rest-Spiel
Lass uns ein Spiel spielen. Gegeben ist eine Anfangszahl sowie zwei Sequenzen und . Das Ziel ist, so schnell wie möglich von auf 0 zu gelangen. In jedem Schritt darfst du einen Index
i wählen und die folgende Operation auf die aktuelle Zahl anwenden:Auf diese Weise erhältst du die nächste Zahl. Du sollst die minimale Anzahl von Operationen bestimmen, um von auf 0 zu kommen.
Eingabe
Die erste Zeile der Eingabe enthält 3 ganze Zahlen
n, m und (0 ≤ n ≤ 10, 0 ≤ m ≤ 100 000 und 0 < < m).Die nächsten
n Zeilen enthalten jeweils ein Paar von ganzen Zahlen und (0 ≤ , ≤ ).Ausgabe
Das Programm soll die minimale Anzahl an Operationen ausgeben, um von auf 0 zu gelangen. Ist es unmöglich, 0 zu erreichen, soll das Programm
Impossible ausgeben.Beispiele
Eingabe | Ausgabe |
2 5 1
3 1
2 1 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB