Problem
Zähle alle Ganzzahlen von left bis right (beide einschließlich), bei denen keine benachbarten Ziffern gleich sind. Verwende dabei die übliche Dezimalschreibweise ohne führende Nullen. Die Null und alle anderen einstelligen Zahlen erfüllen die Bedingung.
Implementiere counting_numbers(left, right).
Eingabe
left: Der kleinste erlaubte Wert.
right: Der größte erlaubte Wert.
Ausgabe
Gib zurück, wie viele Werte die Bedingung erfüllen.
Einschränkungen
0 ≤ left ≤ right ≤ 10¹⁸. Der Bereich kann zu groß sein, um jede Zahl einzeln zu prüfen.
Beispiele
Eingabe:
left = 10
right = 15
Erwartete Ausgabe:
expected = 5Eingabe:
long long left = 10;
long long right = 15;
Erwartete Ausgabe:
long long expected = 5;Eingabe:
long left = 10;
long right = 15;
Erwartete Ausgabe:
long expected = 5;Erläuterung
Nur 11 hat gleiche benachbarte Ziffern. Die anderen fünf Zahlen erfüllen die Bedingung.
Eingabe:
left = 0
right = 9
Erwartete Ausgabe:
expected = 10Eingabe:
long long left = 0;
long long right = 9;
Erwartete Ausgabe:
long long expected = 10;Eingabe:
long left = 0;
long right = 9;
Erwartete Ausgabe:
long expected = 10;Erläuterung
Alle zehn Werte bestehen nur aus einer Ziffer und haben daher keine gleichen Nachbarn.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Zähle gültige Zahlen bis zu jedem Randwert und subtrahiere dann, um die Antwort für den Bereich zu erhalten.
Hinweis 2
Digit DP passt gut, weil die Gültigkeit von benachbarten Ziffern und davon abhängt, ob die Zahl schon begonnen hat.
Hinweis 3
Führende Nullen brauchen besondere Behandlung, damit kürzere Zahlen korrekt mitgezählt werden.
Erwartete Komplexität
Zeit O(k * 10 * states), zusätzlicher Speicher O(k * states)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.