Problem 770 asks for the smallest \(n\) for which the Delphi Flip value reaches a prescribed target \(x\). The implementations reduce that value to the closed form
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
Therefore the search problem becomes: given \(x\in(1,2)\), find the least \(n\ge 0\) such that \(D_n\ge x\). Because \(r_n\) decreases to \(0\), this is equivalent to detecting the first time a central-binomial ratio drops below a threshold.
Let
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
The implementations solve this by turning the original inequality into a monotone threshold test for \(r_n\), then combining an exact recurrence with a large-\(n\) asymptotic estimate.
Starting from
$$D_n=\frac{2}{1+r_n},$$
the condition \(D_n\ge x\) is equivalent to
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
If we define the threshold
$$\tau=\frac{2}{x}-1,$$
then the whole problem becomes
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
This reformulation is the key reason the code never needs to simulate the game directly.
The central ratio is
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
Comparing consecutive terms gives
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
Hence
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
Because \(\frac{2n-1}{2n}<1\) for every \(n\ge 1\), the sequence \((r_n)\) is strictly decreasing. That monotonicity guarantees that once \(r_n\) has gone below \(\tau\), the first crossing index is unique.
For small thresholds, the answer is large, so a direct forward sweep would take too many steps. The implementations therefore use the asymptotic expansion of the central binomial coefficient:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
The leading term is \(1/\sqrt{\pi n}\), so the first approximation to the crossing point is obtained by solving
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
which yields
$$n\approx \frac{1}{\pi\tau^2}.$$
This gives a very good starting index when \(x\) is close to \(2\), precisely the regime that matters for the final query.
The asymptotic series gives an estimate, not an exact answer, so the implementations finish with exact multiplicative updates. First an initial guess is taken as
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor.$$
The truncated asymptotic formula is evaluated at \(n_0\). If that estimated value is already at or below the threshold, the implementations walk backward using
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
until they are just above the threshold. Then they move forward again with
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
until the first valid index is reached. Because the sequence is monotone and the asymptotic start is close to the true answer, only a short correction loop is needed in the large-\(n\) regime.
When the estimate \(n_0\) is modest, the simplest method is also the most reliable: start from \(r_0=1\) and repeatedly apply
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
until \(r_n\le \tau\). The implementations switch to this direct branch whenever the asymptotic estimate is below a fixed cutoff. That avoids unnecessary asymptotic work for easy inputs.
This checkpoint appears in the implementations. First compute
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
Now compare the two consecutive central ratios around the crossing:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
Since \(r_9>\tau\) but \(r_{10}\le \tau\), the first valid index is
$$g(1.7)=10.$$
Equivalently, \(D_9<1.7\) and \(D_{10}\ge 1.7\), so the minimum is exactly \(10\).
The C++, Python, and Java implementations follow the same strategy. They first convert the requested target \(x\) into the threshold \(\tau=2/x-1\). Next they compute the coarse estimate \(\lfloor 1/(\pi\tau^2)\rfloor\). If that estimate is small, they iterate the exact recurrence from \(n=0\), updating the ratio by a single multiplication at each step.
If the estimate is large, they evaluate the truncated asymptotic series at that index and then repair any approximation error by stepping backward or forward with the exact recurrence ratio until the minimal valid \(n\) is found. No factorials, huge binomial coefficients, or large integer tables are required; the algorithm works entirely with a few floating-point quantities and exact multiplicative transitions between consecutive terms.
The direct branch takes \(O(g(x))\) time because it visits every index from \(0\) up to the answer, and it uses \(O(1)\) memory. In the large-\(n\) branch, the asymptotic estimate is computed in \(O(1)\) time and the correction loop is typically very short, so the practical running time is close to constant while the memory usage remains \(O(1)\).
Problem 770 verlangt das kleinste \(n\), für das der Delphi-Flip-Wert einen vorgegebenen Zielwert \(x\) erreicht. Die Implementierungen reduzieren diesen Wert auf die geschlossene Form
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
Damit wird aus der ursprünglichen Frage: Finde für \(x\in(1,2)\) das kleinste \(n\ge 0\) mit \(D_n\ge x\). Weil \(r_n\) monoton gegen \(0\) fällt, ist das äquivalent dazu, den ersten Index zu finden, an dem ein zentrales Binomialverhältnis unter einen Schwellwert sinkt.
Wir definieren
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
Die Implementierungen lösen dies, indem sie die Ungleichung in einen monotonen Test für \(r_n\) umschreiben und anschließend eine exakte Rekurrenz mit einer Groß-\(n\)-Asymptotik kombinieren.
Aus
$$D_n=\frac{2}{1+r_n}$$
folgt
$$D_n\ge x \iff \frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
Mit der Definition
$$\tau=\frac{2}{x}-1$$
erhält man also
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
Gerade diese Umformung erklärt, warum der Code das Spiel selbst nicht direkt modellieren muss.
Für das Verhältnis gilt
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
Vergleicht man zwei aufeinanderfolgende Glieder, so ergibt sich
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
Damit folgt
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
Da \(\frac{2n-1}{2n}<1\) für jedes \(n\ge 1\) gilt, ist \((r_n)\) streng fallend. Deshalb ist der erste Index mit \(r_n\le \tau\) eindeutig bestimmt.
Für sehr kleine Schwellwerte ist die gesuchte Antwort groß, und ein reines Vorwärtslaufen wäre zu teuer. Deshalb benutzen die Implementierungen die asymptotische Entwicklung des zentralen Binomialkoeffizienten:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
Der führende Term ist \(1/\sqrt{\pi n}\). Löst man zunächst
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
so erhält man den Startwert
$$n\approx \frac{1}{\pi\tau^2}.$$
Gerade wenn \(x\) nahe bei \(2\) liegt, ist dieser Schätzwert bereits sehr präzise.
Die Asymptotik liefert nur eine Näherung, deshalb enden die Implementierungen mit exakten Multiplikationsschritten. Zuerst wird
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor$$
gesetzt. Danach wird die abgeschnittene Asymptotik bei \(n_0\) ausgewertet. Liegt dieser Wert bereits unter oder auf dem Schwellwert, dann gehen die Implementierungen mit
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
zurück, bis sie wieder knapp oberhalb der Grenze sind. Anschließend laufen sie mit
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
vorwärts, bis der erste gültige Index erreicht ist. Wegen der Monotonie und des guten Startwerts bleibt diese Korrektur im großen Bereich sehr kurz.
Ist \(n_0\) klein, ist die einfachste Methode auch die beste: Man startet mit \(r_0=1\) und wendet wiederholt
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
an, bis \(r_n\le \tau\) gilt. Die Implementierungen schalten bei kleinen Schätzwerten genau auf diesen direkten Zweig um und vermeiden so unnötige asymptotische Zusatzarbeit.
Dieser Kontrollwert steht in den Implementierungen. Zuerst berechnet man
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
Dann betrachtet man die beiden aufeinanderfolgenden Verhältnisse um den Grenzpunkt:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
Weil \(r_9>\tau\), aber \(r_{10}\le \tau\), ist der erste gültige Index
$$g(1.7)=10.$$
Äquivalent dazu gilt \(D_9<1.7\) und \(D_{10}\ge 1.7\), also ist das Minimum genau \(10\).
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Strategie. Zuerst wird aus dem Zielwert \(x\) der Schwellwert \(\tau=2/x-1\) berechnet. Danach bestimmen sie den groben Startindex \(\lfloor 1/(\pi\tau^2)\rfloor\). Ist dieser klein, laufen sie die exakte Rekurrenz ab \(n=0\) einfach vorwärts durch und aktualisieren das Verhältnis pro Schritt mit genau einer Multiplikation.
Ist der Startindex groß, werten sie die abgeschnittene asymptotische Reihe an dieser Stelle aus und reparieren den verbleibenden Näherungsfehler durch wenige Rückwärts- oder Vorwärtsschritte mit dem exakten Rekurrenzfaktor. Fakultäten, riesige Binomialkoeffizienten oder große Tabellen werden zu keinem Zeitpunkt erzeugt; der ganze Algorithmus arbeitet nur mit wenigen Gleitkommazahlen und exakten Übergängen zwischen benachbarten Termen.
Der direkte Zweig benötigt \(O(g(x))\) Zeit, weil jeder Index von \(0\) bis zur Antwort besucht wird, und \(O(1)\) Speicher. Im Groß-\(n\)-Zweig kostet die asymptotische Schätzung \(O(1)\) Zeit, und die anschließende Korrekturschleife ist in der Praxis sehr kurz. Deshalb liegt die Laufzeit dort praktisch nahe an konstant, während der Speicherbedarf weiterhin \(O(1)\) bleibt.
Problem 770, Delphi Flip değerinin verilen bir \(x\) hedefini ilk kez hangi \(n\) için yakaladığını sorar. Uygulamalar bu değeri
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}$$
kapalı formuna indirger. Böylece soru şuna dönüşür: \(x\in(1,2)\) verildiğinde \(D_n\ge x\) koşulunu sağlayan en küçük \(n\ge 0\) nedir? \(r_n\) dizisi \(0\)'a doğru azaldığı için, bu aslında merkezi binom oranının bir eşik değerin altına ilk inişini bulma problemidir.
Şunu tanımlayalım:
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
Uygulamalar bu ifadeyi \(r_n\) için tek yönlü bir eşik testine çevirir; sonra da tam rekürans ile büyük \(n\) asimptotiğini birleştirir.
Başlangıç noktası
$$D_n=\frac{2}{1+r_n}$$
olduğuna göre, \(D_n\ge x\) şartı
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1$$
ile aynıdır. Şimdi
$$\tau=\frac{2}{x}-1$$
tanımını yaparsak
$$g(x)=\min\{n\ge 0:r_n\le \tau\}$$
elde edilir. Kodun oyunu doğrudan modellemek yerine yalnızca bu oranı izlemesinin nedeni budur.
Oran
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}$$
şeklindedir. Ardışık iki terimi oranlarsak
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}$$
bulunur. Dolayısıyla
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1)$$
olur. \(\frac{2n-1}{2n}<1\) olduğu için \((r_n)\) sıkı biçimde azalan bir dizidir. Bu da eşik geçişinin tek bir ilk indekste gerçekleştiğini garanti eder.
Eşik çok küçükse cevap çok büyür; bu durumda \(n=0\)'dan itibaren tek tek ilerlemek pahalı olur. Bu yüzden uygulamalar merkezi binom katsayısının şu açılımını kullanır:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
Baş terim \(1/\sqrt{\pi n}\) olduğundan, ilk kaba tahmin
$$\frac{1}{\sqrt{\pi n}}\approx \tau$$
denklemini çözerek elde edilir:
$$n\approx \frac{1}{\pi\tau^2}.$$
\(x\) değeri \(2\)'ye yaklaştığında tam da ihtiyaç duyulan şey budur; gerçek cevap büyük olsa bile iyi bir başlangıç noktası verir.
Asimptotik seri kesin değer vermez; yalnızca yakın bir başlangıç üretir. Bu yüzden uygulamalar önce
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor$$
değerini alır, sonra kesilmiş seriyi bu noktada hesaplar. Eğer elde edilen yaklaşık oran zaten eşikte ya da altındaysa,
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
bağıntısıyla geriye gidilir ve değer yeniden eşik üstüne çıkana kadar devam edilir. Ardından
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
ile ileri yürünür ve ilk geçerli indeks bulunur. Dizi monoton olduğu ve başlangıç tahmini iyi olduğu için büyük-\(n\) bölgesinde bu düzeltme döngüsü çok kısadır.
\(n_0\) küçükse en güvenilir yöntem aynı zamanda en basit olanıdır: \(r_0=1\) ile başla ve
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
adımını \(r_n\le \tau\) olana kadar tekrarla. Uygulamalar belirli bir kesme değerinin altında bu doğrudan dala geçer; böylece kolay girdiler için asimptotik değerlendirme yapmaya gerek kalmaz.
Bu kontrol değeri uygulamaların içinde de bulunur. Önce
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882$$
hesaplanır. Sınırın çevresindeki iki ardışık oran şunlardır:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
\(r_9>\tau\) ama \(r_{10}\le \tau\) olduğundan ilk geçerli indeks
$$g(1.7)=10$$
olur. Aynı şey \(D_9<1.7\) ve \(D_{10}\ge 1.7\) şeklinde de görülebilir.
C++, Python ve Java uygulamaları aynı düzeni izler. Önce hedef \(x\), \(\tau=2/x-1\) eşiğine çevrilir. Sonra kaba başlangıç olarak \(\lfloor 1/(\pi\tau^2)\rfloor\) hesaplanır. Bu tahmin küçükse tam rekürans \(n=0\)'dan itibaren ileri yürütülür; her adımda oran yalnızca tek bir çarpma ile güncellenir.
Tahmin büyükse, uygulama kesilmiş asimptotik seriyi o noktada değerlendirir ve kalan hatayı tam rekürans oranıyla birkaç geri ya da ileri adım atarak düzeltir. Faktöriyel hesapları, dev binom katsayıları veya büyük yardımcı tablolar yoktur; bütün çözüm birkaç kayan noktalı sayı ve ardışık terimler arasındaki tam çarpan üzerinden yürür.
Doğrudan dal \(0\)'dan cevaba kadar her indeksi ziyaret ettiği için süre maliyeti \(O(g(x))\), bellek maliyeti ise \(O(1)\)'dir. Büyük-\(n\) dalında asimptotik tahmin \(O(1)\) zamanda elde edilir ve düzeltme döngüsü pratikte çok kısa kalır; bu yüzden çalışma süresi fiilen sabite yakındır. Her iki durumda da bellek kullanımı \(O(1)\) olarak kalır.
El Problema 770 pide el menor \(n\) para el cual el valor de Delphi Flip alcanza un objetivo dado \(x\). Las implementaciones reducen ese valor a la forma cerrada
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
Por tanto, el problema se convierte en lo siguiente: dado \(x\in(1,2)\), hallar el menor \(n\ge 0\) tal que \(D_n\ge x\). Como \(r_n\) decrece hasta \(0\), esto equivale a detectar el primer índice en el que una razón binomial central cae por debajo de un umbral.
Definimos
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
Las implementaciones resuelven esta búsqueda transformando la desigualdad original en una prueba monótona sobre \(r_n\), y luego combinan una recurrencia exacta con una aproximación asintótica para \(n\) grande.
Partimos de
$$D_n=\frac{2}{1+r_n}.$$
Entonces la condición \(D_n\ge x\) es equivalente a
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
Si introducimos el umbral
$$\tau=\frac{2}{x}-1,$$
obtenemos
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
Esta equivalencia explica por qué el algoritmo no necesita reproducir el juego paso a paso: basta con seguir la sucesión \(r_n\).
La razón central es
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
Al comparar términos consecutivos se obtiene
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
Por lo tanto,
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
Como \(\frac{2n-1}{2n}<1\) para todo \(n\ge 1\), la sucesión es estrictamente decreciente. En consecuencia, el primer cruce del umbral es único.
Cuando el umbral es muy pequeño, la respuesta es grande y avanzar desde \(n=0\) sería costoso. Por eso las implementaciones usan la expansión asintótica del coeficiente binomial central:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
El término dominante es \(1/\sqrt{\pi n}\). Si resolvemos primero
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
aparece la estimación inicial
$$n\approx \frac{1}{\pi\tau^2}.$$
Ese punto de partida es especialmente eficaz cuando \(x\) está muy cerca de \(2\).
La serie asintótica da una aproximación, no la respuesta exacta. Por eso las implementaciones toman primero
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor$$
y evalúan allí la versión truncada de la expansión. Si el valor estimado ya está por debajo o justo en el umbral, retroceden con
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
hasta quedar otra vez por encima. Después avanzan mediante
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
hasta localizar el primer índice válido. La monotonicidad de \(r_n\) y la buena calidad de \(n_0\) hacen que esta corrección sea corta en la práctica.
Si \(n_0\) es pequeño, lo mejor es empezar desde el principio: se toma \(r_0=1\) y se aplica repetidamente
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
hasta que se cumpla \(r_n\le \tau\). Las implementaciones usan precisamente esta rama cuando la estimación asintótica es modesta, porque evita cualquier coste adicional de aproximación.
Este valor aparece como verificación en las implementaciones. Primero se calcula
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
Ahora miramos las dos razones consecutivas alrededor del cruce:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
Como \(r_9>\tau\) pero \(r_{10}\le \tau\), el primer índice válido es
$$g(1.7)=10.$$
En otras palabras, \(D_9<1.7\) y \(D_{10}\ge 1.7\), así que el mínimo buscado es exactamente \(10\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero convierten el objetivo \(x\) en el umbral \(\tau=2/x-1\). Después calculan la aproximación gruesa \(\lfloor 1/(\pi\tau^2)\rfloor\). Si esa estimación es pequeña, recorren la recurrencia exacta desde \(n=0\), actualizando la razón con una sola multiplicación por paso.
Si la estimación es grande, evalúan la serie asintótica truncada en ese índice y luego corrigen el error residual avanzando o retrocediendo con la razón exacta entre términos consecutivos hasta hallar el menor \(n\) válido. No es necesario construir factoriales, coeficientes binomiales enormes ni tablas de apoyo; todo el cálculo se hace con unas pocas cantidades de coma flotante y transiciones exactas entre términos vecinos.
La rama directa cuesta \(O(g(x))\) tiempo porque visita todos los índices desde \(0\) hasta la respuesta, y usa \(O(1)\) memoria. En la rama para \(n\) grande, la estimación asintótica se calcula en \(O(1)\) y la corrección final suele requerir muy pocos pasos, por lo que el tiempo práctico es casi constante. El consumo de memoria sigue siendo \(O(1)\).
第 770 题要求找出最小的 \(n\)，使得 Delphi Flip 的目标值达到给定的 \(x\)。实现并不是直接按游戏过程模拟，而是先把该值化成
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
因此问题等价于：给定 \(x\in(1,2)\)，求最小的 \(n\ge 0\)，使 \(D_n\ge x\)。由于 \(r_n\) 单调下降并趋于 \(0\)，这又等价于寻找中心二项式比值第一次不大于某个阈值的位置。
定义
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
实现的核心思路是先把原问题改写成对 \(r_n\) 的单调阈值判断，再把精确递推和大 \(n\) 渐近式结合起来。这样既能保证正确性，也能在 \(x\) 非常接近 \(2\) 时保持速度。
由
$$D_n=\frac{2}{1+r_n}$$
可知，条件 \(D_n\ge x\) 等价于
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
如果记
$$\tau=\frac{2}{x}-1,$$
那么问题就变成
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
这一步非常重要，因为它说明真正需要追踪的对象只有一个简单的数列 \(r_n\)，而不是原题的叙述形式。
中心比值写成阶乘形式就是
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
将相邻两项相除，可得
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
于是
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
由于对一切 \(n\ge 1\) 都有 \(\frac{2n-1}{2n}<1\)，所以 \((r_n)\) 是严格递减的。这样一来，阈值第一次被越过的位置一定唯一，不会出现来回震荡的问题。
当阈值非常小时，答案会很大。如果从 \(n=0\) 开始一步一步递推，虽然完全正确，但成本会偏高。因此实现使用中心二项式系数的渐近展开：
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
主导项是 \(1/\sqrt{\pi n}\)。如果先只保留主项并解方程
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
就得到初始估计
$$n\approx \frac{1}{\pi\tau^2}.$$
这个估计在 \(x\) 接近 \(2\) 时尤其有效，因为那时 \(\tau\) 很小，而真实答案正处在大 \(n\) 区域。
渐近式只负责给出一个很接近的起点，不负责直接给出精确最小值。实现首先取
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor,$$
然后在这个位置计算截断后的渐近表达式。如果估计出的 \(r_{n_0}\) 已经不大于阈值，就利用
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
向后退，直到重新回到阈值上方。接着再用
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
向前走，直到第一次满足 \(r_n\le \tau\)。由于数列单调且起点很接近真实答案，这个修正循环通常只需要很少几步。
如果 \(n_0\) 本身并不大，那么直接从 \(r_0=1\) 开始递推反而更简单、更稳妥：
$$r_n=r_{n-1}\frac{2n-1}{2n}.$$
只要不断更新，直到 \(r_n\le \tau\) 即可。实现对这种情况专门设置了直接分支，避免在小规模输入上额外使用渐近近似。
实现中包含这个校验点。先算阈值：
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
接着看跨越阈值附近的两项：
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
因为 \(r_9>\tau\)，而 \(r_{10}\le \tau\)，所以最小满足条件的下标是
$$g(1.7)=10.$$
换句话说，\(D_9<1.7\)，但 \(D_{10}\ge 1.7\)，因此答案正好是 \(10\)。
C++、Python 和 Java 实现遵循完全相同的流程。首先把目标 \(x\) 转换成阈值 \(\tau=2/x-1\)。然后计算粗略估计 \(\lfloor 1/(\pi\tau^2)\rfloor\)。如果这个估计较小，就从 \(n=0\) 开始按精确递推式逐项更新 \(r_n\)。
如果估计较大，就在该点上计算截断的渐近式，再通过精确的相邻项乘法关系做少量前后修正，最终定位到最小可行的 \(n\)。整个过程中都不需要直接构造巨大的阶乘、超大的二项式系数，或者任何大型辅助表；算法只维护少量浮点数和相邻项之间的精确比例。
直接递推分支需要从 \(0\) 走到答案，因此时间复杂度是 \(O(g(x))\)，空间复杂度是 \(O(1)\)。在大 \(n\) 分支中，渐近估计本身是 \(O(1)\) 的，而后续修正通常只需很短的循环，所以实际运行时间接近常数，空间仍然是 \(O(1)\)。
В задаче 770 нужно найти наименьшее \(n\), при котором величина Delphi Flip достигает заданного уровня \(x\). Реализации сначала сводят эту величину к закрытой формуле
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
После этого задача становится такой: для \(x\in(1,2)\) найти минимальное \(n\ge 0\), при котором \(D_n\ge x\). Так как \(r_n\) монотонно убывает к нулю, это эквивалентно поиску первого индекса, где центральное биномиальное отношение не превосходит заданный порог.
Обозначим
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
Реализации решают задачу, превращая исходное неравенство в монотонную проверку для \(r_n\), а затем комбинируют точную рекуррентную формулу и асимптотику для больших \(n\).
Из равенства
$$D_n=\frac{2}{1+r_n}$$
следует, что условие \(D_n\ge x\) равносильно
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
Если ввести порог
$$\tau=\frac{2}{x}-1,$$
то получаем
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
Именно поэтому в программе не требуется напрямую моделировать исходную постановку: достаточно отслеживать последовательность \(r_n\).
Центральное отношение имеет вид
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
Для соседних членов имеем
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
Следовательно,
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
Так как \(\frac{2n-1}{2n}<1\) при любом \(n\ge 1\), последовательность строго убывает. Значит, первый момент перехода через порог существует и определяется однозначно.
Когда порог очень мал, ответ становится большим, и прямой проход от \(n=0\) занимает слишком много шагов. Поэтому реализации используют асимптотическое разложение центрального биномиального коэффициента:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
Главный член здесь равен \(1/\sqrt{\pi n}\). Если сначала решить приближенно
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
то получится начальная оценка
$$n\approx \frac{1}{\pi\tau^2}.$$
Такой старт особенно хорош в режиме \(x\to 2\), где \(\tau\) мало, а нужный индекс велик.
Асимптотика не обязана сразу попадать в точный минимальный индекс, поэтому реализации заканчивают вычисление точными мультипликативными переходами. Сначала берётся
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor.$$
Затем в точке \(n_0\) вычисляется усечённая асимптотическая формула. Если полученное значение уже не превосходит порог, то выполняется движение назад по формуле
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
до тех пор, пока последовательность снова не окажется выше порога. После этого идёт движение вперёд по правилу
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
до первого допустимого индекса. Из-за монотонности и хорошего стартового приближения эта корректировка обычно очень короткая.
Если \(n_0\) само по себе невелико, то выгоднее просто идти от начала: взять \(r_0=1\) и повторять
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
до выполнения условия \(r_n\le \tau\). Реализации именно так и поступают на малых входах, не тратя время на асимптотическую инициализацию там, где она не нужна.
Этот контрольный пример присутствует в реализациях. Сначала считаем
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
Теперь смотрим на два соседних значения около точки перехода:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
Поскольку \(r_9>\tau\), а \(r_{10}\le \tau\), получаем
$$g(1.7)=10.$$
То же самое можно сформулировать как \(D_9<1.7\) и \(D_{10}\ge 1.7\), поэтому минимальное \(n\) равно \(10\).
Реализации на C++, Python и Java используют один и тот же алгоритм. Сначала целевое значение \(x\) переводится в порог \(\tau=2/x-1\). Затем вычисляется грубая оценка \(\lfloor 1/(\pi\tau^2)\rfloor\). Если она мала, код просто идёт вперёд по точной рекурсии, начиная с \(n=0\), и на каждом шаге обновляет отношение одной мультипликативной операцией.
Если оценка велика, берётся усечённая асимптотика в этой точке, после чего оставшаяся ошибка исправляется несколькими точными шагами назад или вперёд с помощью отношения соседних членов. Никакие большие факториалы, огромные биномиальные коэффициенты или массивные вспомогательные таблицы не строятся; всё вычисление держится на нескольких числах с плавающей точкой и точных переходах между соседними \(r_n\).
Прямая ветка требует \(O(g(x))\) времени, потому что посещает все индексы от \(0\) до ответа, и \(O(1)\) памяти. В ветке для больших \(n\) асимптотическая инициализация стоит \(O(1)\), а корректирующий цикл обычно очень короткий, так что на практике время работы почти постоянно. Память в обоих случаях остаётся \(O(1)\).
تطلب المسألة 770 إيجاد أصغر \(n\) بحيث تصل قيمة Delphi Flip إلى الهدف المعطى \(x\). تقوم التطبيقات أولًا باختزال هذه القيمة إلى الصيغة المغلقة
$$D_n=\frac{2}{1+r_n},\qquad r_n=\frac{\binom{2n}{n}}{4^n}.$$
وبذلك تصبح المهمة: عند إعطاء \(x\in(1,2)\)، أوجد أصغر \(n\ge 0\) يحقق \(D_n\ge x\). وبما أن \(r_n\) تتناقص تدريجيًا نحو الصفر، فإن هذا يكافئ البحث عن أول موضع تهبط فيه نسبة ثنائية الحد المركزية إلى ما دون حد معيّن.
لنعرّف
$$g(x)=\min\{n\ge 0:D_n\ge x\}.$$
تعتمد التطبيقات على تحويل المتباينة الأصلية إلى اختبار حدّي أحادي الاتجاه على \(r_n\)، ثم تجمع بين علاقة تراجعية دقيقة وتقدير تقاربي صالح عندما يكون \(n\) كبيرًا.
بما أن
$$D_n=\frac{2}{1+r_n},$$
فإن الشرط \(D_n\ge x\) يكافئ
$$\frac{2}{1+r_n}\ge x \iff 1+r_n\le \frac{2}{x} \iff r_n\le \frac{2}{x}-1.$$
إذا عرّفنا العتبة
$$\tau=\frac{2}{x}-1,$$
أصبحت المسألة
$$g(x)=\min\{n\ge 0:r_n\le \tau\}.$$
وهذه هي الفكرة الأساسية: لسنا بحاجة إلى محاكاة وصف المسألة حرفيًا، بل يكفي تتبّع المتتالية \(r_n\).
لدينا
$$r_n=\frac{(2n)!}{(n!)^2\,4^n}.$$
وبمقارنة حدّين متتاليين نحصل على
$$\frac{r_n}{r_{n-1}}=\frac{(2n)!}{(n!)^2\,4^n}\cdot\frac{((n-1)!)^2\,4^{n-1}}{(2n-2)!}=\frac{2n-1}{2n}.$$
إذًا
$$r_0=1,\qquad r_n=r_{n-1}\frac{2n-1}{2n}\quad(n\ge 1).$$
ولأن \(\frac{2n-1}{2n}<1\) لكل \(n\ge 1\)، فإن المتتالية \((r_n)\) تناقصية تناقصًا صارمًا. وبالتالي يوجد موضع عبور أول وحيد للعتبة.
إذا كانت العتبة صغيرة جدًا فسيكون الجواب كبيرًا، وعندها يصبح التقدّم من \(n=0\) خطوة بخطوة مكلفًا. لذلك تستخدم التطبيقات التوسع التقاربي للمعامل الثنائي المركزي:
$$r_n\approx \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8n}+\frac{1}{128n^2}+\frac{5}{1024n^3}-\frac{21}{32768n^4}\right).$$
الحد الرئيسي هنا هو \(1/\sqrt{\pi n}\). فإذا حللنا تقريبًا
$$\frac{1}{\sqrt{\pi n}}\approx \tau,$$
نحصل على نقطة البداية
$$n\approx \frac{1}{\pi\tau^2}.$$
وهذا مفيد جدًا عندما تكون \(x\) قريبة من \(2\)، لأن \(\tau\) تصبح صغيرة للغاية بينما يكبر الجواب الحقيقي.
التقريب لا يعطي الجواب الأدق مباشرة، بل يقدّم موقعًا قريبًا جدًا من الحل. لذلك تأخذ التطبيقات أولًا
$$n_0=\left\lfloor\frac{1}{\pi\tau^2}\right\rfloor,$$
ثم تحسب عنده الصيغة التقاربية المقطوعة. إذا كانت القيمة المقدّرة لا تزال عند العتبة أو دونها، يجري الرجوع باستخدام
$$r_{n-1}=r_n\frac{2n}{2n-1}$$
حتى العودة فوق العتبة. بعد ذلك يتم التقدّم من جديد بواسطة
$$r_{n+1}=r_n\frac{2n+1}{2n+2}$$
إلى أن نصل إلى أول \(n\) صالح. وبسبب رتابة المتتالية وجودة نقطة البداية، يكون هذا التصحيح قصيرًا جدًا في المجال الكبير.
إذا كان \(n_0\) صغيرًا أصلًا، فالطريقة الأبسط هي الأفضل: نبدأ من \(r_0=1\) ثم نكرر
$$r_n=r_{n-1}\frac{2n-1}{2n}$$
إلى أن يتحقق \(r_n\le \tau\). تستعمل التطبيقات هذا الفرع المباشر عندما يكون التقدير الابتدائي صغيرًا، لأن ذلك يلغي الحاجة إلى أي معالجة تقاربية إضافية.
هذا المثال مستخدم كنقطة تحقق في التطبيقات. نحسب أولًا
$$\tau=\frac{2}{1.7}-1=\frac{3}{17}\approx 0.1764705882.$$
ثم ننظر إلى الحدّين المحيطين بموضع العبور:
$$r_9=\frac{\binom{18}{9}}{4^9}=\frac{12155}{65536}\approx 0.1854705811,$$
$$r_{10}=\frac{\binom{20}{10}}{4^{10}}=\frac{46189}{262144}\approx 0.1761970520.$$
بما أن \(r_9>\tau\) ولكن \(r_{10}\le \tau\)، فإن أول فهرس صالح هو
$$g(1.7)=10.$$
وبصيغة مكافئة، لدينا \(D_9<1.7\) بينما \(D_{10}\ge 1.7\)، ولذلك فالحد الأدنى المطلوب يساوي \(10\).
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تبدأ بتحويل الهدف \(x\) إلى العتبة \(\tau=2/x-1\). ثم تحسب التقدير الخشن \(\lfloor 1/(\pi\tau^2)\rfloor\). إذا كان هذا التقدير صغيرًا، فإنها تسير مباشرة من \(n=0\) باستخدام العلاقة التراجعية الدقيقة، مع تحديث النسبة بضربة ضرب واحدة في كل خطوة.
أما إذا كان التقدير كبيرًا، فتقيّم التوسع التقاربي المقطوع عند ذلك الموضع، ثم تصلح الفرق المتبقي بعدد قليل من الخطوات الدقيقة إلى الخلف أو إلى الأمام حتى تعثر على أصغر \(n\) صالح. لا حاجة إلى حساب مضروبات ضخمة أو معاملات ثنائية هائلة أو جداول مساعدة كبيرة؛ فكل الخوارزمية تعمل بواسطة بضع قيم عائمة وانتقالات دقيقة بين حدود متجاورة.
الفرع المباشر يحتاج إلى \(O(g(x))\) زمنًا لأنه يزور كل قيمة من \(0\) حتى الجواب، ويحتاج إلى \(O(1)\) ذاكرة. أما في فرع \(n\) الكبير، فالتقدير التقاربي نفسه يكلف \(O(1)\) فقط، وحلقة التصحيح تكون قصيرة جدًا عادة، لذلك يكون الزمن العملي قريبًا من الثبات، بينما تبقى الذاكرة \(O(1)\) في جميع الأحوال.