We have \(N\) identical balls moving in a one-dimensional frictionless tube of length \(L\). Their empty gaps and initial directions are generated deterministically from the recurrence
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
From each state we obtain a gap
$$d_n=(r_n\bmod 1000)+1,$$
and the direction is to the right when \(r_n\le 10^7\), otherwise to the left. The goal is not the whole collision history, but only the exit time of the ball that starts in position \(j\) from the left. The implementations avoid explicit collision simulation by turning the problem into a selection problem on a derived list of times.
The key observation is that equal-mass elastic collisions in one dimension only exchange velocities. That lets us replace the real system by non-colliding ghost trajectories, then recover the required labeled ball through an order statistic.
The recurrence gives one positive gap for each ball. Define the cumulative reduced position
$$s_n=\sum_{m=1}^{n} d_m.$$
This quantity is exactly what the implementations maintain while scanning the pseudo-random sequence. It is the natural coordinate after collapsing away the fixed diameter contribution of the balls already placed to the left, so
$$s_1<s_2<\cdots<s_N.$$
All geometry-dependent formulas in the algorithm depend only on these cumulative values, not on a step-by-step physical reconstruction of every collision.
In one dimension, two identical balls undergoing an elastic collision simply exchange velocities. If we ignore labels, this is indistinguishable from the balls passing through each other. Therefore the multiset of unlabeled trajectories is the same as if no collisions happened at all.
So each ball can be treated as a ghost particle that moves in a straight line until it leaves the tube. The real system is recovered afterward by restoring labels according to left-to-right order. This is the standard label-exchange trick and is the reason the problem can be reduced to pure arithmetic.
For the queried ball index \(j\), the implementations use the fixed geometry term
$$B_j=L-10-20(j-1).$$
The subtraction of \(20(j-1)\) accounts for the diameters of the \(j-1\) balls initially to its left, and the remaining \(10\) is the edge-radius correction appearing in the tube geometry. Once the reduced coordinate \(s_n\) is known, the \(n\)-th ghost contributes the candidate time
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
The sign is determined entirely by the initial direction. A right-moving ghost has less distance left when its reduced coordinate is larger, while a left-moving ghost contributes the symmetric expression with a plus sign. The C++, Python, and Java implementations compute exactly these values.
Let the candidate times be sorted in nondecreasing order:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
A larger candidate means that the corresponding ghost trajectory remains inside the tube longer. Because real collisions only swap labels, the ball that starts in position \(j\) from the left follows the \(j\)-th longest surviving ghost schedule. Equivalently, its exit time is the \((N-j+1)\)-st smallest candidate:
$$T_j=\tau_{(N-j+1)}.$$
In zero-based array indexing this is exactly the element at position
$$N-j.$$
The whole problem is therefore reduced to a deterministic recurrence plus one order statistic:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
Here \(\operatorname{OS}_{k}\) denotes the \(k\)-th smallest element. No collision tree, event queue, or pairwise interaction simulation is needed.
For this sample we have
$$B_2=5000-10-20(2-1)=4970.$$
The first three recurrence values generate the following data:
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
After sorting,
$$4853<5519<5692.$$
Because \(N-j=1\), we read the element at zero-based index \(1\), namely
$$T_2=5519,$$
which matches the sample check used by the implementation.
The implementations iterate once through the recurrence, maintaining the running cumulative gap \(s_n\). For each ball they immediately convert the current state into one candidate value \(\tau_n\) using the sign rule above and store that value in an array or list.
After all \(N\) candidates are produced, the C++ implementation performs direct order-statistic selection, while the Python and Java implementations sort the full collection and read the element at index \(N-j\). In every language the mathematical object being computed is the same: the \((N-j+1)\)-st smallest candidate exit time.
Generating the recurrence, cumulative gaps, and candidate times costs \(O(N)\) time. The C++ implementation then performs expected \(O(N)\) selection, so its overall expected running time is \(O(N)\). The Python and Java implementations sort all candidates, giving \(O(N\log N)\) total time. All three implementations use \(O(N)\) memory to store the candidate times.
Gegeben sind \(N\) identische Kugeln in einer eindimensionalen reibungsfreien Röhre der Länge \(L\). Leerräume und Anfangsrichtungen werden deterministisch durch die Rekursion
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}$$
erzeugt. Daraus folgt für jede Kugel ein Abstand
$$d_n=(r_n\bmod 1000)+1,$$
wobei die Bewegung nach rechts erfolgt, falls \(r_n\le 10^7\), sonst nach links. Gesucht ist nicht die komplette Stoßgeschichte, sondern nur die Austrittszeit der Kugel, die anfangs an Position \(j\) von links steht. Die Lösung ersetzt die Kollisionen durch eine Ordnungsstatistik über abgeleitete Zeiten.
Der entscheidende Punkt ist: Bei elastischen Stößen gleicher Massen in einer Dimension werden nur Geschwindigkeiten vertauscht. Dadurch kann man das reale System durch kollisionsfreie Geistertrajektorien ersetzen und die gesuchte markierte Kugel anschließend über ihre Rangposition wiederherstellen.
Aus den Abständen entsteht die kumulierte reduzierte Position
$$s_n=\sum_{m=1}^{n} d_m.$$
Genau diese Größe halten die Implementierungen während des Durchlaufs fest. Sie ist die natürliche Koordinate, wenn man die festen Durchmesserbeiträge der bereits links liegenden Kugeln herausrechnet. Deshalb gilt
$$s_1<s_2<\cdots<s_N.$$
Alle späteren Formeln hängen nur von diesen kumulierten Werten ab; eine explizite Rekonstruktion jeder einzelnen Kollision ist unnötig.
In einer Dimension verhalten sich zwei identische Kugeln bei einem elastischen Stoß so, als würden sie ihre Geschwindigkeiten austauschen. Ignoriert man die Labels, ist das dasselbe, als würden die Kugeln einfach durch einander hindurchlaufen.
Also darf jede Kugel als Geisterteilchen auf gerader Bahn bis zum Austritt betrachtet werden. Das reale System erhält man danach zurück, indem man die Labels gemäß der Links-Rechts-Reihenfolge wieder zuordnet. Genau dieser Labeltausch-Trick macht aus dem physikalischen Problem ein arithmetisches Problem.
Für den abgefragten Index \(j\) verwenden die Implementierungen den festen Geometrieterm
$$B_j=L-10-20(j-1).$$
Der Anteil \(20(j-1)\) steht für die Durchmesser der \(j-1\) anfangs links liegenden Kugeln; der verbleibende Term \(10\) ist die Randkorrektur durch den Kugelradius. Ist die reduzierte Position \(s_n\) bekannt, dann liefert die \(n\)-te Geisterbahn die Kandidatenzeit
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
Das Vorzeichen hängt nur von der Anfangsrichtung ab. Bei Bewegung nach rechts bedeutet größere reduzierte Startposition weniger Restweg; bei Bewegung nach links erscheint die symmetrische Plus-Form. Genau diese linearen Ausdrücke werden in C++, Python und Java berechnet.
Sortiere die Kandidatenzeiten aufsteigend:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
Eine größere Kandidatenzeit bedeutet, dass die betreffende Geisterbahn länger in der Röhre bleibt. Da reale Stöße nur Labels vertauschen, folgt die Kugel, die anfangs an Position \(j\) von links stand, der \(j\)-längsten überlebenden Geisterbahn. Damit ist ihre Austrittszeit die \((N-j+1)\)-kleinste Kandidatenzeit:
$$T_j=\tau_{(N-j+1)}.$$
Bei nullbasierter Indexierung ist das genau das Element an Position
$$N-j.$$
Damit reduziert sich das gesamte Problem auf eine deterministische Rekursion plus eine einzelne Ordnungsstatistik:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
Hier bezeichnet \(\operatorname{OS}_{k}\) das \(k\)-kleinste Element. Weder Ereigniswarteschlangen noch paarweise Stoßsimulationen sind erforderlich.
In diesem Beispiel gilt
$$B_2=5000-10-20(2-1)=4970.$$
Die ersten drei Rekursionswerte liefern
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
Nach dem Sortieren erhält man
$$4853<5519<5692.$$
Da \(N-j=1\), lesen wir das Element mit nullbasiertem Index \(1\), also
$$T_2=5519,$$
genau den Kontrollwert der Implementierung.
Die Implementierungen durchlaufen die Rekursion genau einmal und halten dabei die laufende Summe \(s_n\). Für jede Kugel wird sofort mit der obigen Vorzeichenregel ein Kandidatenwert \(\tau_n\) berechnet und in einem Array oder einer Liste gespeichert.
Nachdem alle \(N\) Kandidaten erzeugt wurden, führt die C++-Implementierung eine direkte Ordnungsstatistik-Selektion aus. Die Python- und Java-Implementierungen sortieren die gesamte Sammlung und lesen anschließend das Element an Index \(N-j\) aus. In allen drei Sprachen ist das mathematische Ziel identisch: die \((N-j+1)\)-kleinste Kandidatenzeit.
Das Erzeugen der Rekursion, der kumulierten Abstände und der Kandidatenzeiten kostet \(O(N)\) Zeit. Anschließend arbeitet die C++-Implementierung mit erwarteter \(O(N)\)-Selektion und bleibt somit insgesamt erwartungsgemäß bei \(O(N)\). Die Python- und Java-Implementierungen sortieren vollständig und benötigen daher \(O(N\log N)\) Zeit. Alle drei Fassungen brauchen \(O(N)\) Speicher für die Kandidatenzeiten.
Elimizde uzunluğu \(L\) olan tek boyutlu sürtünmesiz bir tüp içinde hareket eden \(N\) özdeş bilye vardır. Boşluklar ve ilk yönler şu deterministik yineleme ile üretilir:
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
Her durumdan
$$d_n=(r_n\bmod 1000)+1$$
boşluğu elde edilir; \(r_n\le 10^7\) ise hareket sağa, aksi halde sola doğrudur. İstenen şey tüm çarpışma geçmişi değildir; soldan \(j\). sırada başlayan bilyenin tüpten çıkış zamanıdır. Çözüm, çarpışmaları tek tek canlandırmak yerine problemi türetilmiş zamanlar üzerinde bir sıralı istatistik hesabına indirger.
Ana gözlem şudur: Bir boyutta eşit kütleli elastik çarpışmalar yalnızca hızları değiş tokuş eder. Bu yüzden gerçek sistemi, çarpışmayan hayalet yörüngelerle değiştirip sonra istenen etiketi sıra bilgisiyle geri getirebiliriz.
Boşluklardan kümülatif indirgenmiş konumu tanımlayalım:
$$s_n=\sum_{m=1}^{n} d_m.$$
Uygulamalar yinelemeyi gezerken tam olarak bu büyüklüğü günceller. Bu değer, solda kalan bilyelerin sabit çap katkıları çıkarıldıktan sonra elde edilen doğal koordinattır. Dolayısıyla
$$s_1<s_2<\cdots<s_N$$
olur. Sonraki bütün formüller yalnızca bu kümülatif değerlere bağlıdır; her çarpışmayı ayrı ayrı üretmeye gerek kalmaz.
Bir boyutta iki özdeş bilye elastik çarpıştığında, etiketleri yok sayarsak sonuç sanki birbirlerinin içinden geçmişler gibi görünür. Fiziksel fark yalnızca hangi etiketin hangi doğrusal yörüngeye geçtiğidir.
Bu nedenle her bilyeyi, tüpten çıkana kadar düz bir doğru üzerinde ilerleyen hayalet bir parçacık gibi ele alabiliriz. Gerçek sistemi geri kurmak için gereken tek şey, soldan sağa sıralamanın korunmasıdır. Böylece fiziksel problem doğrudan aritmetik bir seçme problemine dönüşür.
Sorgulanan \(j\) indeksi için uygulamaların kullandığı sabit geometrik terim
$$B_j=L-10-20(j-1)$$
şeklindedir. Buradaki \(20(j-1)\), başlangıçta solda duran \(j-1\) bilyenin çaplarından gelir; kalan \(10\) ise tüp kenarındaki yarıçap düzeltmesidir. İndirgenmiş konum \(s_n\) bilindiğinde, \(n\). hayalet yörünge şu aday zamanı üretir:
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
İşaret tamamen ilk yöne bağlıdır. Sağa giden bir hayalet için daha büyük indirgenmiş konum daha az kalan mesafe demektir; sola giden için simetrik olarak artı işaretli ifade ortaya çıkar. C++, Python ve Java uygulamaları tam olarak bu değerleri hesaplar.
Aday zamanları küçükten büyüğe sıralayalım:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
Daha büyük bir aday, ilgili hayalet yörüngenin tüp içinde daha uzun süre kaldığını gösterir. Gerçek çarpışmalar sadece etiket değişimi yaptığı için, soldan \(j\). sırada başlayan bilye \(j\). en uzun yaşayan hayalet programa bağlanır. Bu yüzden aranan çıkış zamanı, \((N-j+1)\). en küçük adaydır:
$$T_j=\tau_{(N-j+1)}.$$
Sıfır tabanlı dizi indislemesinde bu tam olarak
$$N-j$$
konumundaki elemandır.
Böylece tüm problem deterministik bir yineleme ve tek bir sıralı istatistiğe indirgenir:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
Burada \(\operatorname{OS}_{k}\), \(k\). en küçük elemanı gösterir. Olay kuyruğu, temas listesi ya da ikili çarpışma simülasyonu gerekmez.
Bu örnekte
$$B_2=5000-10-20(2-1)=4970$$
olur. İlk üç yineleme değeri şu tabloyu verir:
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
Sıralanmış adaylar
$$4853<5519<5692$$
şeklindedir. \(N-j=1\) olduğu için sıfır tabanlı dizide 1. indisli elemanı alırız:
$$T_2=5519.$$
Bu değer, uygulamanın kullandığı örnek kontrolle aynıdır.
Uygulamalar yinelemeyi tek geçişte üretir ve aynı anda kümülatif toplam \(s_n\)'yi tutar. Her bilye için mevcut durumdan doğrudan bir aday değer \(\tau_n\) hesaplanır ve bir diziye ya da listeye eklenir.
Tüm \(N\) aday üretildikten sonra C++ uygulaması doğrudan sıralı istatistik seçimi yapar. Python ve Java uygulamaları ise tüm koleksiyonu sıralayıp \(N-j\) indisli elemanı okur. Üç dilde de hesaplanan matematiksel nesne aynıdır: \((N-j+1)\). en küçük aday çıkış zamanı.
Yineleme, kümülatif boşluklar ve aday zamanların üretilmesi \(O(N)\) zaman alır. Ardından C++ uygulaması beklenen \(O(N)\) seçme işlemi yaptığı için toplam beklenen süre \(O(N)\) olur. Python ve Java uygulamaları tüm adayları sıraladığı için toplam zaman \(O(N\log N)\)'dir. Üç uygulamanın da aday zamanları saklamak için kullandığı bellek \(O(N)\)'dir.
Tenemos \(N\) bolas idénticas dentro de un tubo unidimensional sin fricción de longitud \(L\). Los huecos iniciales y las direcciones se generan de forma determinista mediante
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
De cada estado se obtiene un hueco
$$d_n=(r_n\bmod 1000)+1,$$
y la dirección es hacia la derecha si \(r_n\le 10^7\), o hacia la izquierda en caso contrario. No hace falta reconstruir toda la historia de choques; solo se pide el instante de salida de la bola que empieza en la posición \(j\) contando desde la izquierda. La solución transforma el problema en una selección sobre una lista de tiempos candidatos.
La observación central es que, en una dimensión, los choques elásticos entre masas iguales solo intercambian velocidades. Eso permite reemplazar el sistema real por trayectorias fantasma sin colisiones y recuperar después la bola etiquetada mediante una estadística de orden.
Definimos la posición reducida acumulada por
$$s_n=\sum_{m=1}^{n} d_m.$$
Esta es exactamente la cantidad que mantienen las implementaciones al recorrer la recurrencia. Puede verse como la coordenada natural que queda al descontar la contribución fija del diámetro de las bolas ya colocadas a la izquierda. Por eso
$$s_1<s_2<\cdots<s_N.$$
Todas las fórmulas posteriores dependen solo de estos valores acumulados, no de una simulación detallada de cada impacto.
En una dimensión, dos bolas idénticas que chocan elásticamente se comportan, si ignoramos las etiquetas, como si simplemente se atravesaran. La diferencia física real es solo qué etiqueta queda asociada a cada trayectoria rectilínea.
Por lo tanto, cada bola puede estudiarse como una partícula fantasma que se mueve en línea recta hasta abandonar el tubo. Después se recupera el sistema real reinsertando las etiquetas según el orden izquierda-derecha. Este truco de intercambio de etiquetas es la simplificación decisiva.
Para el índice consultado \(j\), las implementaciones usan el término geométrico fijo
$$B_j=L-10-20(j-1).$$
La parte \(20(j-1)\) representa los diámetros de las \(j-1\) bolas que al inicio están a su izquierda; el \(10\) restante es la corrección de borde asociada al radio. Una vez conocida la coordenada reducida \(s_n\), la trayectoria fantasma \(n\) aporta el tiempo candidato
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
El signo depende solo de la dirección inicial. Si la bola fantasma va a la derecha, una coordenada reducida mayor significa menos distancia restante; si va a la izquierda aparece la expresión simétrica con signo positivo. Las implementaciones en C++, Python y Java calculan exactamente estas cantidades.
Ordenemos los tiempos candidatos de menor a mayor:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
Un candidato mayor significa que la trayectoria fantasma correspondiente permanece dentro del tubo durante más tiempo. Como los choques reales solo intercambian etiquetas, la bola que empezó en la posición \(j\) desde la izquierda acaba siguiendo la \(j\)-ésima trayectoria fantasma más duradera. Por tanto, su instante de salida es el \((N-j+1)\)-ésimo candidato más pequeño:
$$T_j=\tau_{(N-j+1)}.$$
Con índices basados en cero, eso coincide exactamente con la posición
$$N-j.$$
Todo el problema se reduce así a una recurrencia determinista y una sola estadística de orden:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
Aquí \(\operatorname{OS}_{k}\) denota el \(k\)-ésimo elemento más pequeño. No se necesita ninguna cola de eventos ni una simulación explícita de choques por parejas.
En este caso
$$B_2=5000-10-20(2-1)=4970.$$
Los tres primeros valores de la recurrencia producen
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
Tras ordenar, obtenemos
$$4853<5519<5692.$$
Como \(N-j=1\), leemos el elemento de índice cero-basado \(1\), es decir,
$$T_2=5519,$$
que coincide con la comprobación de ejemplo usada por la implementación.
Las implementaciones recorren una vez la recurrencia y mantienen la suma acumulada \(s_n\). Para cada bola convierten inmediatamente el estado actual en un valor candidato \(\tau_n\) mediante la regla de signo anterior y lo guardan en un arreglo o lista.
Cuando ya existen los \(N\) candidatos, la implementación en C++ hace una selección directa de estadística de orden. Las implementaciones en Python y Java ordenan toda la colección y leen el elemento situado en el índice \(N-j\). En los tres casos se calcula el mismo objeto matemático: el \((N-j+1)\)-ésimo candidato más pequeño.
Generar la recurrencia, las sumas acumuladas y los tiempos candidatos cuesta \(O(N)\). Después, la implementación en C++ aplica una selección de tiempo esperado \(O(N)\), por lo que su tiempo total esperado es \(O(N)\). Las implementaciones en Python y Java ordenan todos los candidatos y requieren \(O(N\log N)\). Las tres usan \(O(N)\) memoria para almacenar los tiempos candidatos.
题目考虑一根长度为 \(L\) 的一维无摩擦管道，里面有 \(N\) 个完全相同的小球。初始空隙和运动方向不是手工给定，而是由确定性的递推序列生成：
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
对第 \(n\) 个状态定义空隙
$$d_n=(r_n\bmod 1000)+1,$$
若 \(r_n\le 10^7\) 则该球初始向右，否则向左。真正要求的并不是完整的碰撞过程，而是“初始时从左到右排在第 \(j\) 个”的那个球离开管道的时间。实现并不显式维护每一次碰撞，而是把问题转写成一组候选时间上的顺序统计问题。
核心思想是：在一维中，等质量弹性碰撞只会交换速度。于是我们可以先忽略标签，把系统看成互相穿过的“幽灵粒子”；最后再用左右顺序把真正的小球标签还原回来。
先定义累计的压缩坐标
$$s_n=\sum_{m=1}^{n} d_m.$$
这正是实现过程中持续维护的量。它的含义是：把已经放在左边那些球的固定直径贡献压缩掉之后，第 \(n\) 个球剩下的自然坐标。由于每个空隙都是正数，所以
$$s_1<s_2<\cdots<s_N.$$
这样一来，后续公式只依赖这些累计值，而不需要把真实几何位置和所有接触事件逐一展开。
在一维中，两个完全相同的小球发生弹性碰撞时，如果不关心球的身份，只看轨迹集合，那么结果和“两个粒子直接穿过彼此”没有区别。真正发生变化的只是标签附着到了哪一条直线运动轨迹上。
因此可以先假想每个球都是不会碰撞的幽灵粒子，各自沿直线运动直到离开管道。然后再根据任意时刻从左到右的次序，把真实的标签重新贴回去。这个“碰撞等价于标签交换”的技巧，正是整个算法能成立的关键。
对于询问中的第 \(j\) 个球，实现先构造一个固定的几何基准量
$$B_j=L-10-20(j-1).$$
其中 \(20(j-1)\) 对应于它左边那 \(j-1\) 个球的直径总贡献，而额外的 \(10\) 是由边界与半径带来的修正项。知道了压缩坐标 \(s_n\) 以后，第 \(n\) 条幽灵轨迹就对应一个候选时间
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
符号完全由初始方向决定。向右运动时，压缩坐标越大，剩余距离越短，所以出现减号；向左运动时得到与之对称的加号形式。C++、Python 和 Java 实现计算的正是这两种线性表达式。
把所有候选时间按从小到大排序：
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
候选时间越大，说明对应的幽灵轨迹在管道中存活得越久。由于真实碰撞只会交换标签，初始时排在左边第 \(j\) 个的球，最终对应的是“存活时间第 \(j\) 长”的那条幽灵轨迹。换成从小到大的顺序，这个时间就是第 \((N-j+1)\) 小的候选值：
$$T_j=\tau_{(N-j+1)}.$$
如果采用从 \(0\) 开始的数组下标，那么读取的位置正好是
$$N-j.$$
因此整个问题可以压缩成“生成递推序列 + 计算一次顺序统计”：
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
这里 \(\operatorname{OS}_{k}\) 表示第 \(k\) 小元素。算法不需要事件优先队列，也不需要按时间顺序枚举任意一对球的碰撞。
这时
$$B_2=5000-10-20(2-1)=4970.$$
递推的前三项给出如下数据：
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
排序后得到
$$4853<5519<5692.$$
因为 \(N-j=1\)，所以读取零基下标 \(1\) 处的值：
$$T_2=5519.$$
这与实现中的示例检验完全一致。
实现先顺序生成递推值，同时维护累计量 \(s_n\)。每处理一个球，就立刻根据当前方向把它转换成一个候选时间 \(\tau_n\)，并保存到数组或列表中。
当全部 \(N\) 个候选值生成后，C++ 实现直接做一次顺序统计选择；Python 和 Java 实现则对整个集合排序，然后读取下标 \(N-j\) 的元素。三种语言计算的数学对象完全相同：第 \((N-j+1)\) 小的候选离开时间。
生成递推、累计空隙以及构造全部候选时间需要 \(O(N)\) 时间。随后，C++ 实现采用期望 \(O(N)\) 的选择过程，因此总期望时间仍为 \(O(N)\)。Python 和 Java 实现对全部候选值排序，所以总时间为 \(O(N\log N)\)。三种实现都需要 \(O(N)\) 额外空间保存候选时间。
Рассматриваются \(N\) одинаковых шаров в одномерной трубе без трения длины \(L\). Начальные промежутки и направления задаются детерминированной рекурсией
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
Из каждого состояния получается зазор
$$d_n=(r_n\bmod 1000)+1,$$
а направление выбирается так: вправо при \(r_n\le 10^7\), влево иначе. Требуется не вся история столкновений, а только время выхода шара, который в начальный момент стоял \(j\)-м слева. Реализация не моделирует столкновения по событиям, а сводит задачу к выбору порядковой статистики из списка вычисленных времен.
Главное наблюдение состоит в том, что при упругих столкновениях одинаковых масс в одном измерении меняются местами только скорости. Поэтому реальную систему можно заменить системой призрачных траекторий без столкновений, а нужную метку восстановить по порядку слева направо.
Введем накопленную редуцированную координату
$$s_n=\sum_{m=1}^{n} d_m.$$
Именно эту величину поддерживают реализации при проходе по рекурсии. Она естественна после того, как из конфигурации вынесен фиксированный вклад диаметров шаров, уже стоящих левее. Поэтому
$$s_1<s_2<\cdots<s_N.$$
Все дальнейшие формулы зависят только от этих накопленных значений; явно восстанавливать каждое столкновение не нужно.
В одном измерении два одинаковых шара после упругого удара ведут себя, если забыть про метки, так, как будто они просто прошли друг сквозь друга. Физически меняется лишь то, какая метка прикрепляется к какой прямолинейной траектории.
Значит, можно считать, что каждый шар является призрачной частицей, движущейся по прямой до выхода из трубы. Затем реальная картина восстанавливается с помощью порядка слева направо. Этот прием обмена меток и убирает необходимость в явной симуляции столкновений.
Для запрошенного индекса \(j\) реализации используют фиксированный геометрический член
$$B_j=L-10-20(j-1).$$
Слагаемое \(20(j-1)\) учитывает диаметры \(j-1\) шаров, которые изначально стоят левее, а оставшееся \(10\) представляет краевую поправку, связанную с радиусом. Когда известно значение \(s_n\), \(n\)-я призрачная траектория дает кандидат
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
Знак полностью определяется начальным направлением. Для движения вправо большая редуцированная координата означает меньший оставшийся путь; для движения влево возникает симметричная формула со знаком плюс. Именно эти выражения вычисляют реализации на C++, Python и Java.
Отсортируем кандидатные времена по неубыванию:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
Чем больше кандидат, тем дольше соответствующая призрачная траектория остается внутри трубы. Поскольку реальные столкновения только меняют метки местами, шар, который изначально был \(j\)-м слева, в итоге следует по \(j\)-й по длительности призрачной траектории. Следовательно, его время выхода равно \((N-j+1)\)-му наименьшему кандидату:
$$T_j=\tau_{(N-j+1)}.$$
При нулевой индексации массива это ровно позиция
$$N-j.$$
Значит, вся задача сводится к детерминированной рекурсии и одной порядковой статистике:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
Здесь \(\operatorname{OS}_{k}\) означает \(k\)-й наименьший элемент. Никакой очереди событий и никакой попарной симуляции ударов не требуется.
В этом примере
$$B_2=5000-10-20(2-1)=4970.$$
Первые три значения рекурсии дают
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
После сортировки получаем
$$4853<5519<5692.$$
Так как \(N-j=1\), нужно взять элемент с нулевым индексом \(1\):
$$T_2=5519.$$
Это в точности совпадает с контрольным примером из реализации.
Реализации один раз проходят по рекуррентной последовательности и одновременно поддерживают накопленную сумму \(s_n\). Для каждого шара текущее состояние сразу преобразуется в одно кандидатное время \(\tau_n\), которое сохраняется в массиве или списке.
Когда все \(N\) кандидатных значений получены, реализация на C++ выполняет прямой выбор порядковой статистики. Реализации на Python и Java полностью сортируют коллекцию и читают элемент с индексом \(N-j\). Во всех трех языках вычисляется один и тот же математический объект: \((N-j+1)\)-й наименьший кандидат времени выхода.
Построение рекурсии, накопленных зазоров и всех кандидатных времен требует \(O(N)\) времени. Затем реализация на C++ использует выбор с ожидаемой сложностью \(O(N)\), так что ее общее ожидаемое время равно \(O(N)\). Реализации на Python и Java сортируют все кандидаты, поэтому работают за \(O(N\log N)\). Во всех случаях требуется \(O(N)\) памяти для хранения кандидатных времен.
لدينا \(N\) كرات متطابقة داخل أنبوب أحادي البعد عديم الاحتكاك طوله \(L\). الفجوات الابتدائية والاتجاهات لا تُعطى مباشرة، بل تُولد حتميًا من العلاقة
$$r_1=6563116,\qquad r_{n+1}\equiv r_n^2 \pmod{32745673}.$$
ومن كل حالة نحصل على فجوة
$$d_n=(r_n\bmod 1000)+1,$$
وتكون الحركة إلى اليمين إذا كان \(r_n\le 10^7\)، وإلى اليسار خلاف ذلك. المطلوب ليس إعادة بناء جميع التصادمات، بل فقط زمن خروج الكرة التي كانت في البداية في الموضع رقم \(j\) عند العد من اليسار. لذلك تحوّل الخوارزمية المسألة إلى اختيار إحصاء رتبي من قائمة أزمنة مشتقة.
الفكرة الأساسية هي أن التصادمات المرنة بين كرات متساوية الكتلة في بعد واحد لا تفعل أكثر من تبديل السرعات. ولهذا يمكن استبدال النظام الحقيقي بمسارات شبحية غير متصادمة، ثم استرجاع الكرة المطلوبة من ترتيبها بين اليسار واليمين.
نعرّف الإحداثي المختزل التراكمي بالصيغة
$$s_n=\sum_{m=1}^{n} d_m.$$
وهذا هو المقدار الذي تحفظه التطبيقات أثناء المرور على العلاقة التكرارية. ويمكن النظر إليه على أنه الإحداثي الطبيعي بعد حذف المساهمة الثابتة لأقطار الكرات الواقعة إلى اليسار. لذلك نحصل على
$$s_1<s_2<\cdots<s_N.$$
جميع الصيغ اللاحقة تعتمد فقط على هذه القيم التراكمية، من غير حاجة إلى تتبع كل تصادم على حدة.
في بعد واحد، إذا اصطدمت كرتان متماثلتان تصادمًا مرنًا، فإن تجاهل الهويات يجعل النتيجة مساوية تمامًا لحالة مرور كل كرة عبر الأخرى. الفرق الحقيقي الوحيد هو أي بطاقة تعريف تُلصق بأي مسار مستقيم.
بالتالي يمكن اعتبار كل كرة جسيمًا شبحيًا يتحرك في خط مستقيم حتى يخرج من الأنبوب. وبعد ذلك نستعيد النظام الفيزيائي الحقيقي بإرجاع البطاقات وفق ترتيب اليسار إلى اليمين. هذه الحيلة، أي مساواة التصادم بتبديل الملصقات، هي سبب اختفاء الحاجة إلى المحاكاة الصريحة.
للفهرس المطلوب \(j\)، تستخدم التطبيقات الحد الهندسي الثابت
$$B_j=L-10-20(j-1).$$
الحد \(20(j-1)\) يمثل أقطار الكرات \(j-1\) التي كانت أصلًا إلى اليسار، أما \(10\) الباقية فهي تصحيح حدودي مرتبط بنصف القطر. وبعد معرفة الإحداثي المختزل \(s_n\)، يعطي المسار الشبحي رقم \(n\) الزمن المرشح
$$\tau_n=\begin{cases} B_j-s_n, & r_n\le 10^7,\\ B_j+s_n, & r_n>10^7. \end{cases}$$
الإشارة تحددها الجهة الابتدائية فقط. فالحركة إلى اليمين تعني أن زيادة الإحداثي المختزل تقلل المسافة المتبقية، بينما تعطي الحركة إلى اليسار الصيغة المتناظرة ذات الإشارة الموجبة. تطبيقات C++ وPython وJava تحسب هذه القيم نفسها.
لنرتب الأزمنة المرشحة تصاعديًا:
$$\tau_{(1)}\le \tau_{(2)}\le \cdots \le \tau_{(N)}.$$
كلما كان الزمن المرشح أكبر، بقي المسار الشبحي داخل الأنبوب مدة أطول. وبما أن التصادمات الحقيقية لا تفعل سوى تبديل الملصقات، فإن الكرة التي بدأت في الموضع \(j\) من اليسار تتبع في النهاية المسار الشبحي ذي البقاء رقم \(j\) من حيث الطول. لذلك يكون زمن خروجها هو العنصر رقم \((N-j+1)\) عند الترتيب التصاعدي:
$$T_j=\tau_{(N-j+1)}.$$
وباستعمال فهارس تبدأ من الصفر، فهذا يساوي تمامًا الموضع
$$N-j.$$
إذن تُختزل المسألة كلها إلى علاقة حتمية وإحصاء رتبي واحد:
$$\boxed{T_j=\operatorname{OS}_{N-j+1}\!\left(\left\{\tau_1,\tau_2,\dots,\tau_N\right\}\right),\qquad \tau_n=\begin{cases} L-10-20(j-1)-s_n, & r_n\le 10^7,\\ L-10-20(j-1)+s_n, & r_n>10^7. \end{cases}}$$
حيث \(\operatorname{OS}_{k}\) تعني العنصر \(k\)-الأصغر. لا حاجة إلى طابور أحداث، ولا إلى محاكاة تصادمات زوجية بمرور الزمن.
في هذا المثال
$$B_2=5000-10-20(2-1)=4970.$$
وتعطي أول ثلاث قيم من العلاقة التكرارية البيانات التالية:
$$\begin{aligned} r_1&=6563116,& d_1&=117,& s_1&=117,& r_1\le 10^7,& \tau_1&=4970-117=4853,\\ r_2&=14723431,& d_2&=432,& s_2&=549,& r_2>10^7,& \tau_2&=4970+549=5519,\\ r_3&=19804172,& d_3&=173,& s_3&=722,& r_3>10^7,& \tau_3&=4970+722=5692. \end{aligned}$$
بعد الترتيب نحصل على
$$4853<5519<5692.$$
ولأن \(N-j=1\)، فإننا نقرأ العنصر ذي الفهرس الصفري \(1\):
$$T_2=5519.$$
وهذا يطابق تمامًا قيمة التحقق المستخدمة في التطبيق.
تجتاز التطبيقات العلاقة التكرارية مرة واحدة، وتحافظ في الوقت نفسه على المجموع التراكمي \(s_n\). ولكل كرة تُحوِّل الحالة الحالية مباشرة إلى قيمة مرشحة \(\tau_n\) بحسب قاعدة الإشارة السابقة، ثم تخزنها في مصفوفة أو قائمة.
بعد توليد جميع القيم وعددها \(N\)، تنفذ نسخة C++ اختيارًا مباشرًا للإحصاء الرتبي. أما نسختا Python وJava فتقومان بترتيب المجموعة كاملة ثم قراءة العنصر عند الفهرس \(N-j\). في كل اللغات يبقى الهدف الرياضي نفسه: إيجاد الزمن المرشح رقم \((N-j+1)\) عند الترتيب تصاعديًا.
توليد العلاقة التكرارية والفجوات التراكمية والأزمنة المرشحة يحتاج إلى \(O(N)\) زمنًا. بعد ذلك تستخدم نسخة C++ اختيارًا بزمن متوقع \(O(N)\)، فيكون زمنها الكلي المتوقع \(O(N)\). أما نسختا Python وJava فتفرزان جميع القيم، ولذلك يكون الزمن الكلي \(O(N\log N)\). وتحتاج جميع النسخ إلى \(O(N)\) ذاكرة لتخزين الأزمنة المرشحة.