Write a positive integer in base 10 as \(a_1a_2\cdots a_k\). It is called increasing when \(a_1 \le a_2 \le \cdots \le a_k\), decreasing when \(a_1 \ge a_2 \ge \cdots \ge a_k\), and bouncy when neither condition holds. The task is to find the least \(n\) such that exactly \(99\%\) of the integers from 1 to \(n\) are bouncy.
The implementations solve this instance directly. They scan upward through the integers, classify each one from its decimal digits, maintain a running count of bouncy values, and stop at the first exact hit. That search reaches \(n = 1{,}587{,}000\).
The key observation is that the full decimal string is more information than we need. For Problem 112, everything is determined by the signs of adjacent digit differences.
Let the digits of \(n\) be \(a_1,a_2,\dots,a_k\), and define
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
Then the classification becomes
$$\text{increasing} \iff \Delta_i \ge 0 \text{ for all } i,$$
$$\text{decreasing} \iff \Delta_i \le 0 \text{ for all } i,$$
$$\text{bouncy} \iff \text{some } \Delta_i > 0 \text{ and some } \Delta_j < 0.$$
So the only state that matters is whether we have seen a positive adjacent difference and whether we have seen a negative adjacent difference. This immediately explains why one-digit and two-digit numbers can never be bouncy: there are not enough adjacent pairs to witness both directions.
As we inspect the digits, we maintain two booleans. After examining any subset of adjacent pairs, the first records whether a rise has already appeared and the second records whether a fall has already appeared. This invariant is sufficient because later digits can add new evidence, but they can never erase a rise or fall that was already found.
That is why an early exit is correct. The moment both booleans become true, the number is irreversibly bouncy. The Python implementation checks adjacent characters from left to right; the C++ and Java implementations peel digits from right to left. Those two views are equivalent because every adjacent pair is still tested exactly once.
Let \(B(n)\) denote the number of bouncy integers in \(\{1,2,\dots,n\}\). The search is driven by the recurrence
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
where \(I(n)=1\) if \(n\) is bouncy and \(I(n)=0\) otherwise. For the required proportion \(99/100\), we seek the least \(n\) satisfying
$$\frac{B(n)}{n}=\frac{99}{100},$$
or, equivalently,
$$100\,B(n)=99\,n.$$
This integer form matters. It avoids any floating-point rounding issue, and it matches the implementations exactly. More generally, the C++ version is written for an arbitrary rational target \(p/q\) and tests \(qB(n)=pn\). Also note that \(B(n)/n\) is not guaranteed to increase at every step, because the denominator always grows while the numerator sometimes stays fixed, so checking each \(n\) directly is the safe stopping rule.
Consider \(n=155349\). Its adjacent digit differences are
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
We see both a positive difference and a negative difference, so 155349 is bouncy. By contrast, \(134468\) has only nonnegative adjacent differences and is increasing, while \(66420\) has only nonpositive adjacent differences and is decreasing.
The same recurrence then updates the running total by one on bouncy inputs and by zero on non-bouncy inputs. The implementations line up with the standard benchmark values: the least number with 50% bouncy values is 538, the least number with 90% is 21780, and the least number with 99% is \(1{,}587{,}000\).
The desired threshold occurs well below ten million, so the scan never needs to inspect more than seven digits for any one candidate. The main mathematical simplification is therefore not a closed-form counting identity, but the recognition that each integer can be classified with constant auxiliary state and a tiny amount of digit work.
The implementation walks through \(1,2,3,\dots\) in order, classifies each integer as bouncy or non-bouncy, updates a running total, and stops at the first exact 99% hit.
The C++, Python, and Java implementations all test whether both directions of change occur among adjacent digits. The Python version uses the decimal string directly. The C++ and Java versions stay in integer arithmetic and compare digits as they are peeled off. In every language, the scan terminates immediately once both a rise and a fall have been detected.
After the digit test, the implementation adds one to the running total exactly when the current value is bouncy. It then checks the cross-multiplied equality for the target proportion. The general implementation also validates itself against two known milestones, 50% at 538 and 90% at 21780, before solving the final 99% case. Those checkpoints verify both the classification logic and the cumulative counting logic.
If \(N\) is the first solution, then classifying one number costs \(O(d(n))\), where \(d(n)=\lfloor \log_{10} n \rfloor + 1\) is the number of decimal digits of \(n\). Summed over the entire search, this gives
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N)$$
in the usual asymptotic sense.
For this problem, \(N=1{,}587{,}000\), so \(d(n)\le 7\) throughout the run. In practice that makes the algorithm effectively linear in \(N\), and it uses only \(O(1)\) extra memory.
Schreibe eine positive ganze Zahl in Dezimalschreibweise als \(a_1a_2\cdots a_k\). Sie heißt steigend, wenn \(a_1 \le a_2 \le \cdots \le a_k\) gilt, fallend, wenn \(a_1 \ge a_2 \ge \cdots \ge a_k\) gilt, und bouncy, wenn keine der beiden Bedingungen erfüllt ist. Gesucht ist das kleinste \(n\), für das genau \(99\%\) der Zahlen von 1 bis \(n\) bouncy sind.
Die Implementierungen lösen genau diese Instanz direkt. Sie durchsuchen die natürlichen Zahlen aufsteigend, klassifizieren jede Zahl über ihre Dezimalziffern, führen eine laufende Zählung der bouncy Zahlen und brechen beim ersten exakten Treffer ab. Diese Suche endet bei \(n = 1{,}587{,}000\).
Der entscheidende Punkt ist, dass die gesamte Ziffernfolge mehr Information enthält als nötig. Für Problem 112 genügt das Vorzeichenmuster der Differenzen benachbarter Ziffern.
Seien \(a_1,a_2,\dots,a_k\) die Dezimalziffern von \(n\), und definiere
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
Dann gilt
$$\text{steigend} \iff \Delta_i \ge 0 \text{ für alle } i,$$
$$\text{fallend} \iff \Delta_i \le 0 \text{ für alle } i,$$
$$\text{bouncy} \iff \text{ein } \Delta_i > 0 \text{ und ein } \Delta_j < 0 \text{ vorkommen}.$$
Relevant ist also nur, ob bereits eine positive und ob bereits eine negative benachbarte Differenz aufgetreten ist. Damit ist sofort klar, warum ein- und zweistellige Zahlen niemals bouncy sein können: Es gibt nicht genug Nachbarschaftspaare, um beide Richtungen zu beobachten.
Während die Ziffern geprüft werden, hält die Implementierung zwei boolesche Zustände fest. Nach jedem bereits untersuchten Teil der Nachbarschaftspaare speichert der erste Zustand, ob schon ein Anstieg gesehen wurde, und der zweite, ob schon ein Abstieg gesehen wurde. Dieses Invariante reicht aus, weil spätere Ziffern neue Evidenz liefern können, aber einen bereits gefundenen Anstieg oder Abstieg nicht wieder löschen.
Darum ist ein früher Abbruch korrekt. Sobald beide Zustände wahr sind, ist die Zahl unwiderruflich bouncy. Die Python-Implementierung vergleicht benachbarte Zeichen von links nach rechts; die C++- und Java-Implementierungen lesen die Ziffern numerisch von rechts nach links aus. Beide Sichtweisen sind äquivalent, weil jedes benachbarte Ziffernpaar genau einmal geprüft wird.
Sei \(B(n)\) die Anzahl der bouncy Zahlen in \(\{1,2,\dots,n\}\). Die Suche folgt der Rekursion
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
wobei \(I(n)=1\) gilt, falls \(n\) bouncy ist, und \(I(n)=0\) sonst. Für den gesuchten Anteil \(99/100\) brauchen wir das kleinste \(n\) mit
$$\frac{B(n)}{n}=\frac{99}{100},$$
also äquivalent
$$100\,B(n)=99\,n.$$
Diese ganzzahlige Form ist wichtig. Sie vermeidet Rundungsprobleme mit Gleitkommazahlen und entspricht exakt der Implementierung. Allgemeiner ist die C++-Version für ein beliebiges rationales Ziel \(p/q\) geschrieben und testet \(qB(n)=pn\). Außerdem ist \(B(n)/n\) nicht notwendigerweise in jedem Schritt monoton steigend, weil der Nenner immer wächst, der Zähler aber manchmal gleich bleibt. Deshalb ist das direkte Prüfen jedes einzelnen \(n\) die sichere Abbruchregel.
Betrachte \(n=155349\). Die benachbarten Zifferndifferenzen sind
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
Es treten sowohl positive als auch negative Differenzen auf, also ist 155349 bouncy. Dagegen hat \(134468\) nur nichtnegative Differenzen und ist steigend, während \(66420\) nur nichtpositive Differenzen hat und fallend ist.
Mit derselben Rekursion erhöht sich die laufende Summe bei bouncy Eingaben um eins und bei nicht-bouncy Eingaben um null. Die Implementierungen stimmen mit den bekannten Vergleichswerten überein: Das kleinste \(n\) mit 50% bouncy Zahlen ist 538, mit 90% ist es 21780, und mit 99% ist es \(1{,}587{,}000\).
Die gesuchte Schwelle liegt deutlich unter zehn Millionen, daher müssen pro Kandidat höchstens sieben Ziffern betrachtet werden. Die mathematische Vereinfachung besteht hier also nicht in einer geschlossenen Zählformel, sondern in der Einsicht, dass jede Zahl mit konstantem Zusatzspeicher und sehr wenig Ziffernarbeit klassifiziert werden kann.
Die Implementierung läuft die Zahlen \(1,2,3,\dots\) in aufsteigender Reihenfolge durch, entscheidet für jede Zahl zwischen bouncy und nicht-bouncy, aktualisiert eine laufende Summe und stoppt beim ersten exakten 99%-Treffer.
Die C++-, Python- und Java-Implementierungen prüfen alle, ob unter den benachbarten Ziffern beide Änderungsrichtungen vorkommen. Python arbeitet direkt auf der Dezimaldarstellung als Zeichenkette. C++ und Java bleiben vollständig in ganzzahliger Arithmetik und vergleichen Ziffern beim schrittweisen Herauslösen. In allen drei Sprachen endet der Test sofort, sobald sowohl ein Anstieg als auch ein Abstieg gefunden wurden.
Nach dem Zifferntest erhöht die Implementierung die laufende Gesamtzahl genau dann um eins, wenn die aktuelle Zahl bouncy ist. Danach prüft sie die kreuzmultiplizierte Gleichung für den Zielanteil. Die allgemeine Implementierung validiert sich zusätzlich an zwei bekannten Zwischenwerten, 50% bei 538 und 90% bei 21780, bevor sie den endgültigen 99%-Fall löst. Diese Prüfwerte kontrollieren sowohl die Klassifikation als auch die kumulative Zählung.
Wenn \(N\) die erste Lösung ist, kostet die Klassifikation einer Zahl \(O(d(n))\), wobei \(d(n)=\lfloor \log_{10} n \rfloor + 1\) die Anzahl ihrer Dezimalziffern ist. Über den gesamten Suchlauf summiert sich das zu
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N).$$
Für dieses Problem ist \(N=1{,}587{,}000\), also gilt während der gesamten Suche \(d(n)\le 7\). Praktisch ist das Verfahren damit effektiv linear in \(N\) und benötigt nur \(O(1)\) zusätzlichen Speicher.
Pozitif bir tam sayıyı onluk sistemde \(a_1a_2\cdots a_k\) biçiminde yazalım. Eğer \(a_1 \le a_2 \le \cdots \le a_k\) ise sayı artan, \(a_1 \ge a_2 \ge \cdots \ge a_k\) ise azalan, bu iki koşulun hiçbiri sağlanmıyorsa zıplayıcı olur. Soru, 1'den \(n\)'e kadar olan sayıların tam olarak \(99\%\)'unun zıplayıcı olduğu en küçük \(n\)'i istiyor.
Yerel uygulamalar bu özel durumu doğrudan çözüyor. Sayılar artan sırayla taranıyor, her sayı basamaklarından sınıflandırılıyor, zıplayıcı sayısı kümülatif olarak tutuluyor ve ilk tam eşitlikte duruluyor. Bu arama \(n = 1{,}587{,}000\) değerine ulaşıyor.
Asıl fikir, tüm onluk yazımı değil, yalnızca komşu basamak farklarının işaretlerini izlemektir. Problem 112 için gereken bilgi tam olarak budur.
\(n\) sayısının onluk basamakları \(a_1,a_2,\dots,a_k\) olsun ve
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k)$$
tanımını yapalım. O zaman
$$\text{artan} \iff \Delta_i \ge 0 \text{ bütün } i \text{ için},$$
$$\text{azalan} \iff \Delta_i \le 0 \text{ bütün } i \text{ için},$$
$$\text{zıplayıcı} \iff \text{en az bir } \Delta_i > 0 \text{ ve en az bir } \Delta_j < 0.$$
Yani gerçekten gerekli olan tek durum bilgisi şudur: şimdiye kadar pozitif bir komşu fark görüldü mü, negatif bir komşu fark görüldü mü? Bu aynı zamanda tek ve çift basamaklı sayıların neden asla zıplayıcı olmadığını da açıklar; iki yönü birden gösterecek kadar komşu çift yoktur.
Basamakları incelerken iki tane boole değeri tutulur. O ana kadar bakılmış komşu çiftler içinde ilki bir yükseliş görülüp görülmediğini, ikincisi bir düşüş görülüp görülmediğini kaydeder. Bu değişmez yeterlidir; sonraki basamaklar yeni kanıt ekleyebilir ama daha önce görülmüş bir yükselişi ya da düşüşü geri alamaz.
Bu yüzden erken çıkış doğrudur. İki boole de doğru olduğu anda sayı artık kesin olarak zıplayıcıdır. Python uygulaması komşu karakterleri soldan sağa karşılaştırır; C++ ve Java uygulamaları basamakları sağdan sola sayısal olarak söker. İki yaklaşım eşdeğerdir, çünkü her komşu basamak çifti yine tam bir kez sınanır.
\(B(n)\), \(\{1,2,\dots,n\}\) içindeki zıplayıcı sayıların sayısı olsun. Arama şu özyineleme ile yürür:
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
burada \(I(n)=1\) ise \(n\) zıplayıcıdır, aksi halde \(I(n)=0\)'dır. Hedef oran \(99/100\) olduğuna göre aranan en küçük \(n\),
$$\frac{B(n)}{n}=\frac{99}{100}$$
eşitliğini sağlayan değerdir; bu da
$$100\,B(n)=99\,n$$
ile aynıdır. Bu tam sayı biçimi önemlidir. Kayan nokta yuvarlama hatalarını ortadan kaldırır ve uygulamaların yaptığı test ile birebir aynıdır. Daha genel olarak C++ sürümü herhangi bir \(p/q\) rasyonel eşiği için yazılmıştır ve \(qB(n)=pn\) denetimini kullanır. Ayrıca \(B(n)/n\) oranı her adımda artmak zorunda değildir; payda her zaman artarken pay bazen sabit kalır. Bu nedenle güvenli yaklaşım, her \(n\) için tam eşitliği doğrudan kontrol etmektir.
\(n=155349\) sayısını ele alalım. Komşu basamak farkları
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5$$
olur. Hem pozitif hem negatif fark görüldüğü için 155349 zıplayıcıdır. Buna karşılık \(134468\) yalnızca negatif olmayan farklara sahiptir ve artandır; \(66420\) ise yalnızca pozitif olmayan farklara sahiptir ve azalandır.
Aynı özyineleme zıplayıcı girdilerde toplamı bir artırır, diğerlerinde değiştirmez. Uygulamaların doğrulama değerleri de standart Project Euler kilometre taşlarıyla uyumludur: zıplayıcı oranının ilk kez 50% olduğu sayı 538, ilk kez 90% olduğu sayı 21780 ve 99% olduğu sayı \(1{,}587{,}000\)'dır.
Aranan eşik on milyonun epey altında oluşur; dolayısıyla her aday için en fazla yedi basamak incelenir. Buradaki matematiksel sadeleşme kapalı bir sayma formülü değil, her tam sayının sabit yardımcı durum ve çok az basamak işlemiyle sınıflandırılabildiğini fark etmektir.
Uygulama \(1,2,3,\dots\) sayılarını sırayla dolaşır, her birinin zıplayıcı olup olmadığını belirler, koşan toplamı günceller ve ilk tam 99% eşitliğinde durur.
C++, Python ve Java uygulamalarının hepsi komşu basamaklar arasında iki yönlü değişim olup olmadığını sorar. Python doğrudan onluk dizgeyi kullanır. C++ ve Java ise tamamen tamsayı aritmetiğinde kalır ve basamakları sırayla ayırarak karşılaştırır. Üç dilde de hem yükseliş hem düşüş görüldüğü anda tarama hemen sonlandırılır.
Basamak testi tamamlandıktan sonra uygulama, sayı zıplayıcıysa kümülatif toplama bir ekler. Ardından hedef oran için çapraz çarpılmış eşitliği sınar. Genel uygulama, son 99% aramasına geçmeden önce 538 için 50% ve 21780 için 90% kilometre taşlarını da doğrular. Bu kontroller hem sınıflandırma mantığını hem de birikimli sayımı sınar.
\(N\) ilk çözüm olsun. Tek bir sayının sınıflandırılması \(O(d(n))\) maliyetlidir; burada \(d(n)=\lfloor \log_{10} n \rfloor + 1\), \(n\)'in onluk basamak sayısıdır. Tüm tarama boyunca toplam maliyet
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N)$$
olur.
Bu problemde \(N=1{,}587{,}000\) olduğundan arama boyunca \(d(n)\le 7\) kalır. Bu da pratikte yöntemi \(N\)'de doğrusal hale getirir; ek bellek kullanımı ise yalnızca \(O(1)\)'dir.
Escribamos un entero positivo en base 10 como \(a_1a_2\cdots a_k\). El número es creciente cuando \(a_1 \le a_2 \le \cdots \le a_k\), decreciente cuando \(a_1 \ge a_2 \ge \cdots \ge a_k\), y bouncy cuando no cumple ninguna de las dos condiciones. El objetivo es hallar el menor \(n\) tal que exactamente el \(99\%\) de los enteros entre 1 y \(n\) sean bouncy.
Las implementaciones resuelven esta instancia de forma directa. Recorren los enteros en orden ascendente, clasifican cada uno a partir de sus cifras decimales, mantienen un contador acumulado de valores bouncy y se detienen en el primer acierto exacto. Esa búsqueda llega a \(n = 1{,}587{,}000\).
La idea central es que no hace falta conservar toda la cadena decimal. Para este problema basta con el patrón de signos de las diferencias entre cifras consecutivas.
Sean \(a_1,a_2,\dots,a_k\) las cifras de \(n\), y definamos
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
Entonces
$$\text{creciente} \iff \Delta_i \ge 0 \text{ para todo } i,$$
$$\text{decreciente} \iff \Delta_i \le 0 \text{ para todo } i,$$
$$\text{bouncy} \iff \text{aparece algún } \Delta_i > 0 \text{ y algún } \Delta_j < 0.$$
Por tanto, el único estado relevante es si ya vimos una diferencia positiva y si ya vimos una diferencia negativa. Esto explica de inmediato por qué ningún número de una o dos cifras puede ser bouncy: no hay suficientes pares adyacentes para mostrar ambas direcciones.
Mientras se inspeccionan las cifras, se mantienen dos valores booleanos. Tras examinar cualquier subconjunto de pares adyacentes, el primero indica si ya apareció una subida y el segundo si ya apareció una bajada. Ese invariante basta porque las cifras futuras pueden añadir evidencia nueva, pero nunca pueden borrar una subida o una bajada ya detectada.
Por eso la salida temprana es correcta. En cuanto ambos booleanos son verdaderos, el número ya es bouncy de manera irreversible. La implementación en Python compara caracteres adyacentes de izquierda a derecha; las implementaciones en C++ y Java extraen cifras de derecha a izquierda. Ambos recorridos son equivalentes porque cada par adyacente se comprueba exactamente una vez.
Sea \(B(n)\) el número de enteros bouncy en \(\{1,2,\dots,n\}\). La búsqueda sigue la recurrencia
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
donde \(I(n)=1\) si \(n\) es bouncy e \(I(n)=0\) en caso contrario. Para la proporción objetivo \(99/100\), buscamos el menor \(n\) tal que
$$\frac{B(n)}{n}=\frac{99}{100},$$
o, de forma equivalente,
$$100\,B(n)=99\,n.$$
Esta forma entera es importante. Evita cualquier error de redondeo en coma flotante y coincide exactamente con lo que hacen las implementaciones. De hecho, la versión en C++ está parametrizada para un objetivo racional arbitrario \(p/q\) y comprueba \(qB(n)=pn\). Además, la razón \(B(n)/n\) no tiene por qué crecer en cada paso, porque el denominador siempre aumenta y el numerador a veces no cambia. Por eso la regla segura es comprobar la igualdad exacta para cada \(n\).
Tomemos \(n=155349\). Sus diferencias entre cifras consecutivas son
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
Aparecen tanto diferencias positivas como negativas, así que 155349 es bouncy. En cambio, \(134468\) solo tiene diferencias no negativas y es creciente, mientras que \(66420\) solo tiene diferencias no positivas y es decreciente.
La misma recurrencia incrementa el contador en uno cuando la entrada es bouncy y en cero cuando no lo es. Los resultados intermedios coinciden con los hitos conocidos: el menor valor con 50% de números bouncy es 538, con 90% es 21780 y con 99% es \(1{,}587{,}000\).
El umbral buscado aparece muy por debajo de diez millones, así que nunca hay que examinar más de siete cifras para un candidato. La simplificación matemática decisiva no es una fórmula cerrada de conteo, sino darse cuenta de que cada entero puede clasificarse con estado auxiliar constante y con muy poco trabajo sobre sus cifras.
La implementación recorre \(1,2,3,\dots\) en orden, decide si cada entero es bouncy o no, actualiza un total acumulado y se detiene en el primer punto donde se cumple exactamente el 99%.
Las implementaciones en C++, Python y Java comprueban si entre las cifras adyacentes aparecen ambos sentidos de cambio. Python trabaja directamente con la cadena decimal. C++ y Java se mantienen en aritmética entera y comparan cifras a medida que las extraen. En los tres lenguajes, el análisis termina en cuanto ya se observó una subida y una bajada.
Después de clasificar una cifra, la implementación suma uno al total acumulado exactamente cuando el valor actual es bouncy. Luego verifica la igualdad cruzada para la proporción objetivo. La implementación general también se valida con dos hitos conocidos, 50% en 538 y 90% en 21780, antes de resolver el caso final del 99%. Esas comprobaciones verifican tanto la lógica de clasificación como la lógica del conteo acumulado.
Si \(N\) es la primera solución, clasificar un número cuesta \(O(d(n))\), donde \(d(n)=\lfloor \log_{10} n \rfloor + 1\) es el número de cifras decimales de \(n\). Sumado sobre toda la búsqueda, esto produce
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N).$$
En este problema, \(N=1{,}587{,}000\), de modo que \(d(n)\le 7\) durante toda la ejecución. En la práctica, eso hace que el algoritmo sea esencialmente lineal en \(N\) y use solo \(O(1)\) memoria adicional.
把一个正整数写成十进制形式 \(a_1a_2\cdots a_k\)。如果 \(a_1 \le a_2 \le \cdots \le a_k\)，它就是递增数；如果 \(a_1 \ge a_2 \ge \cdots \ge a_k\)，它就是递减数；如果两种条件都不满足，它就是弹跳数。题目要求找出最小的 \(n\)，使得从 1 到 \(n\) 的整数中恰好有 \(99\%\) 是弹跳数。
这几份实现都没有使用封闭计数公式，而是直接求解这个 99% 的实例：按顺序扫描整数，依据十进制数字判断当前整数是否为弹跳数，维护一个累计计数，并在第一次精确命中目标比例时停止。这样得到的最小值是 \(n = 1{,}587{,}000\)。
真正需要观察的不是整段十进制字符串，而是相邻数字差值的符号模式。抓住这一点之后，整个问题就可以压缩成一个极小的状态空间和一个累计计数。
设 \(n\) 的十进制数字为 \(a_1,a_2,\dots,a_k\)，定义
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
那么有
$$\text{递增} \iff \Delta_i \ge 0 \text{ 对所有 } i \text{ 都成立},$$
$$\text{递减} \iff \Delta_i \le 0 \text{ 对所有 } i \text{ 都成立},$$
$$\text{弹跳} \iff \text{某个 } \Delta_i > 0 \text{ 且某个 } \Delta_j < 0.$$
因此，真正重要的只有两件事：是否已经见过正的相邻差值，是否已经见过负的相邻差值。这也立刻解释了为什么一位数和两位数都不可能是弹跳数，因为相邻数字对太少，不可能同时出现两个方向的变化。
在检查数字时，程序维护两个布尔状态。对已经检查过的相邻数字对来说，第一个状态记录是否已经出现过上升，第二个状态记录是否已经出现过下降。这个不变量足够强，因为后续数字只能增加新的证据，不可能把已经出现过的上升或下降“抹掉”。
这就是为什么可以提前退出。一旦两个布尔状态都变成真，当前整数就已经不可逆地被判定为弹跳数。Python 实现从左到右比较相邻字符；C++ 和 Java 实现从右到左逐位取出数字并比较。两种写法本质等价，因为每一对相邻数字都会被恰好检查一次。
记 \(B(n)\) 为集合 \(\{1,2,\dots,n\}\) 中弹跳数的个数。搜索过程满足递推式
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
其中 \(I(n)=1\) 表示 \(n\) 是弹跳数，\(I(n)=0\) 表示不是。对于目标比例 \(99/100\)，我们要求最小的 \(n\) 满足
$$\frac{B(n)}{n}=\frac{99}{100},$$
等价地写成
$$100\,B(n)=99\,n.$$
这个整数形式非常重要。它避免了浮点误差，并且与实现中的判定完全一致。更一般地说，C++ 实现实际上支持任意有理目标 \(p/q\)，检查的是 \(qB(n)=pn\)。还要注意，\(B(n)/n\) 并不保证每一步都单调上升，因为分母每次都会加一，而分子有时保持不变，所以最稳妥的办法就是对每个 \(n\) 直接检查精确相等。
看 \(n=155349\)。它的相邻数字差值是
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
这里既出现了正差值，也出现了负差值，所以 155349 是弹跳数。相对地，\(134468\) 的相邻差值全都不小于 0，因此它是递增数；\(66420\) 的相邻差值全都不大于 0，因此它是递减数。
随后，递推式会在弹跳输入上把累计计数加一，在非弹跳输入上保持不变。实现里的验证里程碑也与这类题目的经典数值一致：弹跳比例第一次达到 50% 的最小值是 538，第一次达到 90% 的最小值是 21780，而 99% 的最小值是 \(1{,}587{,}000\)。
最终阈值远小于一千万，所以对任意候选值都只需要查看不超过七位数字。这里最重要的数学化简并不是构造复杂的闭式计数，而是识别出每个整数都可以用常数级辅助状态和很少的数字比较完成分类。
实现按顺序检查 \(1,2,3,\dots\)，判断每个整数是否为弹跳数，更新累计总数，并在第一次精确达到 99% 时停止。
C++、Python 和 Java 实现都在检查相邻数字之间是否同时出现了两个方向的变化。Python 直接使用十进制字符串。C++ 和 Java 保持在整数运算中，逐位取出数字并比较。三种实现都会在“已经看到上升且已经看到下降”这一条件成立时立刻提前结束当前数字的判断。
完成数字分类后，如果当前整数是弹跳数，累计总数就加一。然后程序检查目标比例对应的交叉相乘等式。通用实现还会先验证两个已知里程碑：50% 对应 538，90% 对应 21780，然后再求最终的 99% 情况。这些检查同时验证了数字分类逻辑和累计计数逻辑。
若最早满足条件的答案为 \(N\)，则判断单个整数的代价是 \(O(d(n))\)，其中 \(d(n)=\lfloor \log_{10} n \rfloor + 1\) 表示 \(n\) 的十进制位数。对整个搜索求和后，总复杂度为
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N).$$
对于本题，\(N=1{,}587{,}000\)，因此整个运行过程中始终有 \(d(n)\le 7\)。在实际表现上，这几乎就是关于 \(N\) 的线性算法，而且额外空间复杂度只有 \(O(1)\)。
Пусть положительное целое число в десятичной записи имеет вид \(a_1a_2\cdots a_k\). Оно называется возрастающим, если \(a_1 \le a_2 \le \cdots \le a_k\), убывающим, если \(a_1 \ge a_2 \ge \cdots \ge a_k\), и bouncy, если не выполняется ни одно из этих условий. Требуется найти наименьшее \(n\), для которого ровно \(99\%\) чисел от 1 до \(n\) являются bouncy.
Реализации решают именно эту конкретную задачу напрямую. Они последовательно перебирают натуральные числа, классифицируют каждое по его десятичным цифрам, поддерживают накопленное число bouncy-значений и останавливаются при первом точном попадании в нужную долю. В результате получается \(n = 1{,}587{,}000\).
Ключевая идея состоит в том, что нам не нужна вся десятичная строка целиком. Для Problem 112 достаточно знать знаки разностей соседних цифр.
Пусть \(a_1,a_2,\dots,a_k\) — десятичные цифры числа \(n\), и определим
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
Тогда
$$\text{возрастающее} \iff \Delta_i \ge 0 \text{ для всех } i,$$
$$\text{убывающее} \iff \Delta_i \le 0 \text{ для всех } i,$$
$$\text{bouncy} \iff \text{существует } \Delta_i > 0 \text{ и существует } \Delta_j < 0.$$
Значит, реально нужно хранить только два факта: встретилась ли уже положительная соседняя разность и встретилась ли уже отрицательная. Отсюда сразу видно, почему однозначные и двузначные числа не могут быть bouncy: у них слишком мало соседних пар, чтобы проявились оба направления изменения.
Во время просмотра цифр поддерживаются два булевых состояния. После обработки любого набора соседних пар первое состояние говорит, встречался ли уже подъём, а второе — встречалось ли уже падение. Этого инварианта достаточно, потому что последующие цифры могут добавить новые свидетельства, но не могут отменить уже найденный подъём или спад.
Именно поэтому ранний выход корректен. Как только оба булевых значения стали истинными, число уже необратимо классифицировано как bouncy. Реализация на Python сравнивает соседние символы слева направо; реализации на C++ и Java извлекают цифры справа налево. Эти два взгляда эквивалентны, потому что каждая соседняя пара цифр всё равно проверяется ровно один раз.
Обозначим через \(B(n)\) количество bouncy-чисел в множестве \(\{1,2,\dots,n\}\). Поиск опирается на рекуррентное соотношение
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
где \(I(n)=1\), если \(n\) является bouncy, и \(I(n)=0\) в противном случае. Для целевой доли \(99/100\) нужно найти наименьшее \(n\), такое что
$$\frac{B(n)}{n}=\frac{99}{100},$$
или, что то же самое,
$$100\,B(n)=99\,n.$$
Эта целочисленная форма принципиальна. Она полностью избавляет от ошибок округления при работе с числами с плавающей точкой и в точности совпадает с тем, что делают реализации. Более того, версия на C++ написана для произвольной рациональной цели \(p/q\) и проверяет равенство \(qB(n)=pn\). Важно и то, что отношение \(B(n)/n\) не обязано расти на каждом шаге: знаменатель увеличивается всегда, а числитель иногда остаётся прежним. Поэтому надёжное правило остановки — проверять точное равенство для каждого \(n\).
Рассмотрим \(n=155349\). Разности соседних цифр равны
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
Здесь есть и положительные, и отрицательные разности, значит, 155349 — bouncy-число. Для сравнения, у \(134468\) все соседние разности неотрицательны, поэтому это возрастающее число, а у \(66420\) все соседние разности неположительны, поэтому оно убывающее.
После этого рекуррентное соотношение увеличивает накопленный счётчик на единицу для bouncy-входов и не меняет его для остальных. Реализации совпадают с известными контрольными значениями: минимальное число с долей 50% равно 538, с долей 90% — 21780, а с долей 99% — \(1{,}587{,}000\).
Нужный порог достигается значительно раньше десяти миллионов, поэтому для любого кандидата приходится смотреть не более семи цифр. Главная математическая экономия здесь не в сложной формуле подсчёта, а в том, что каждое число классифицируется с постоянным дополнительным состоянием и очень малым числом операций над цифрами.
Реализация последовательно проходит числа \(1,2,3,\dots\), определяет для каждого, является ли оно bouncy, обновляет накопленное количество и останавливается при первом точном достижении доли 99%.
Реализации на C++, Python и Java проверяют, встречаются ли среди соседних цифр оба направления изменения. Python работает непосредственно со строкой десятичной записи. C++ и Java остаются в целочисленной арифметике и сравнивают цифры по мере их извлечения. Во всех трёх версиях проверка прекращается сразу, как только обнаружены и подъём, и спад.
После классификации числа программа увеличивает накопленную сумму на единицу ровно тогда, когда текущее число оказалось bouncy. Затем проверяется перекрёстно умноженное равенство для нужной доли. Общая реализация дополнительно проверяет два известных рубежа — 50% при 538 и 90% при 21780 — перед тем как решать окончательный случай 99%. Эти контрольные точки подтверждают и логику классификации, и логику накопительного счёта.
Если \(N\) — первое решение, то классификация одного числа стоит \(O(d(n))\), где \(d(n)=\lfloor \log_{10} n \rfloor + 1\) — число десятичных цифр в \(n\). Суммарно по всему перебору получаем
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N).$$
В этой задаче \(N=1{,}587{,}000\), поэтому на всём протяжении поиска выполняется \(d(n)\le 7\). На практике это делает алгоритм фактически линейным по \(N\), а дополнительная память остаётся равной \(O(1)\).
لنكتب العدد الصحيح الموجب في النظام العشري على الصورة \(a_1a_2\cdots a_k\). يكون العدد تصاعدياً إذا تحقق \(a_1 \le a_2 \le \cdots \le a_k\)، ويكون تنازلياً إذا تحقق \(a_1 \ge a_2 \ge \cdots \ge a_k\)، ويكون مرتداً إذا لم يتحقق أي من الشرطين. المطلوب هو إيجاد أصغر \(n\) بحيث تكون النسبة الدقيقة للأعداد المرتدة بين 1 و\(n\) مساوية لـ \(99\%\).
التنفيذات تحل هذه الحالة مباشرة من دون صيغة مغلقة. فهي تمر على الأعداد تصاعدياً، وتحدد نوع كل عدد من خلال أرقامه العشرية، وتحافظ على عداد تراكمي للأعداد المرتدة، وتتوقف عند أول قيمة تحقق النسبة المطلوبة بدقة. هذه العملية تصل إلى \(n = 1{,}587{,}000\).
الفكرة الأساسية هي أن كتابة العدد كاملة ليست هي المهم، بل المهم هو إشارات فروق الأرقام المتجاورة. عندما نختزل المسألة إلى هذا المستوى، تصبح عبارة عن حالة صغيرة جداً مع عداد تراكمي.
إذا كانت أرقام \(n\) العشرية هي \(a_1,a_2,\dots,a_k\)، فنعرف
$$\Delta_i = a_{i+1} - a_i \qquad (1 \le i < k).$$
وعندئذٍ نحصل على التصنيف التالي:
$$\mathrm{inc} \iff \forall i,\ \Delta_i \ge 0,$$
$$\mathrm{dec} \iff \forall i,\ \Delta_i \le 0,$$
$$\mathrm{bouncy} \iff (\exists i:\Delta_i > 0)\land(\exists j:\Delta_j < 0).$$
إذن الحالة الوحيدة التي نحتاج إلى تتبعها هي: هل ظهر فرق موجب بين رقمين متجاورين؟ وهل ظهر فرق سالب؟ وهذا يفسر فوراً لماذا لا يمكن أن تكون الأعداد ذات الرقم الواحد أو الرقمين أعداداً مرتدة؛ فعدد الأزواج المتجاورة فيها غير كافٍ لظهور الاتجاهين معاً.
أثناء فحص الأرقام تحتفظ الخوارزمية بقيمتين منطقيتين. بعد فحص أي مجموعة من الأزواج المتجاورة، تسجل القيمة الأولى ما إذا كان قد ظهر ارتفاع من قبل، وتسجل الثانية ما إذا كان قد ظهر انخفاض من قبل. هذا الثابت كافٍ، لأن الأرقام اللاحقة قد تضيف دليلاً جديداً، لكنها لا تستطيع محو ارتفاع أو انخفاض سبق اكتشافه.
ولهذا يكون الخروج المبكر صحيحاً. فبمجرد أن تصبح القيمتان المنطقيتان صحيحتين، يصبح العدد مرتداً بشكل نهائي. تنفيذ Python يقارن المحارف المتجاورة من اليسار إلى اليمين، بينما تنفيذَا C++ وJava يستخرجان الأرقام من اليمين إلى اليسار. الطريقتان متكافئتان، لأن كل زوج متجاور يُفحص مرة واحدة بالضبط.
لنرمز بـ \(B(n)\) إلى عدد الأعداد المرتدة داخل المجموعة \(\{1,2,\dots,n\}\). يعتمد البحث على العلاقة
$$B(0)=0,\qquad B(n)=B(n-1)+I(n),$$
حيث إن \(I(n)=1\) إذا كان \(n\) مرتداً، و\(I(n)=0\) خلاف ذلك. وللنسبة المستهدفة \(99/100\) نبحث عن أصغر \(n\) يحقق
$$\frac{B(n)}{n}=\frac{99}{100},$$
أي بصورة مكافئة
$$100\,B(n)=99\,n.$$
هذه الصيغة الصحيحة عددياً مهمة جداً. فهي تمنع أخطاء التقريب العشري، وتطابق ما تفعله التنفيذات حرفياً. وبصورة أعم، فإن تنفيذ C++ مهيأ لأي هدف كسري \(p/q\)، ويختبر العلاقة \(qB(n)=pn\). كذلك يجب الانتباه إلى أن النسبة \(B(n)/n\) ليست مضمونة الازدياد في كل خطوة، لأن المقام يزداد دائماً بينما قد يبقى البسط ثابتاً أحياناً، ولذلك فإن القاعدة الآمنة هي فحص المساواة الدقيقة لكل \(n\).
لنأخذ \(n=155349\). فروق الأرقام المتجاورة هي
$$5-1=4,\qquad 5-5=0,\qquad 3-5=-2,\qquad 4-3=1,\qquad 9-4=5.$$
نرى هنا فرقاً موجباً وفرقاً سالباً، ولذلك يكون 155349 عدداً مرتداً. أما \(134468\) فجميع فروقه المتجاورة غير سالبة، لذلك فهو تصاعدي، في حين أن \(66420\) جميع فروقه غير موجبة، لذلك فهو تنازلي.
بعد ذلك تزيد العلاقة التراكمية العداد بمقدار واحد عند كل إدخال مرتد، وتتركه كما هو عند الإدخال غير المرتد. كما تتطابق التنفيذات مع القيم المرجعية المعروفة: أصغر عدد تصل عنده النسبة إلى 50% هو 538، وإلى 90% هو 21780، وإلى 99% هو \(1{,}587{,}000\).
العتبة النهائية تظهر قبل عشرة ملايين بكثير، ولذلك لا تحتاج الخوارزمية إلى فحص أكثر من سبعة أرقام لأي مرشح. التبسيط الرياضي الحاسم هنا ليس صيغة عد مغلقة، بل إدراك أن تصنيف كل عدد يحتاج إلى حالة مساعدة ثابتة وعدد صغير جداً من مقارنات الأرقام.
يمر التنفيذ على \(1,2,3,\dots\) بالترتيب، ويحدد هل كل عدد مرتد أم لا، ويحدث المجموع التراكمي، ثم يتوقف عند أول موضع تتحقق فيه نسبة 99% بدقة.
تنفيذات C++ وPython وJava كلها تفحص هل يظهر الاتجاهان معاً بين الأرقام المتجاورة. يستخدم Python السلسلة العشرية مباشرة، بينما يبقى C++ وJava ضمن الحسابات الصحيحة ويقارنان الأرقام أثناء استخراجها. وفي اللغات الثلاث كلها يتوقف الفحص فور التأكد من وجود ارتفاع وانخفاض معاً.
بعد اختبار الأرقام يضيف التنفيذ واحداً إلى المجموع التراكمي إذا كان العدد الحالي مرتداً. ثم يفحص معادلة الضرب التبادلي الخاصة بالنسبة المستهدفة. كما أن التنفيذ العام يتحقق أولاً من علامتين مرجعيتين معروفتين: 50% عند 538 و90% عند 21780، قبل حل حالة 99% النهائية. هذه النقاط المرجعية تتحقق من منطق التصنيف ومنطق العد التراكمي معاً.
إذا كانت \(N\) هي أول قيمة تحقق الشرط، فإن تصنيف عدد واحد يكلف \(O(d(n))\)، حيث \(d(n)=\lfloor \log_{10} n \rfloor + 1\) هو عدد أرقام \(n\) في النظام العشري. وبجمع ذلك على كامل البحث نحصل على
$$O\!\left(\sum_{n=1}^{N} d(n)\right)=O(N\log N).$$
في هذه المسألة \(N=1{,}587{,}000\)، ولذلك يبقى \(d(n)\le 7\) طوال التنفيذ كله. عملياً يصبح الأداء شبه خطي في \(N\)، مع استخدام ذاكرة إضافية يساوي \(O(1)\).