The input consists of 1000 lines, each containing a pair \((b,e)\) representing the number \(b^e\). The task is not to compute the largest power itself, but to identify which 1-indexed line produces the largest numerical value.
The obstacle is size. Even a single value such as \(519432^{525806}\) is astronomically large, so ordinary exponentiation is the wrong mathematical object to work with. The real problem is a comparison problem: among all lines, which pair \((b_i,e_i)\) makes \(b_i^{e_i}\) as large as possible?
Let the \(i\)-th line contain \((b_i,e_i)\), and write
$$x_i=b_i^{e_i}.$$
We want the line whose \(x_i\) is maximal. The implementations do not build \(x_i\) directly. Instead they replace each gigantic power by a much smaller real-valued score that preserves exactly the same ordering.
For every positive base \(b_i\), the natural logarithm is defined and satisfies
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
This suggests attaching to each line the score
$$s_i=e_i\ln(b_i).$$
The line with the largest power is exactly the line with the largest score. No big integers are needed; the whole comparison has been reduced to ordinary floating-point arithmetic on numbers of manageable size.
The base of the logarithm is irrelevant. Using \(\log_{10}\), \(\ln\), or any other logarithm only multiplies every score by the same positive constant, so the winning line does not change. The implementations use the standard natural logarithm provided by each language runtime.
The crucial fact is that \(\ln\) is strictly increasing on positive real numbers. Therefore, for any two lines \(i\) and \(j\),
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
Likewise, equality of the original powers would give equality of the logarithmic scores. So the transformation does not approximate the ordering; it preserves it exactly. The only approximation occurs in the numerical evaluation of the logarithm, not in the mathematics of the reduction.
A small checkpoint makes the idea transparent. Compare \(2^{11}\) and \(3^7\). Their scores are
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
Since \(7\ln 3\) is larger, we conclude \(3^7 > 2^{11}\), exactly as expected.
The same method handles the larger comparison quoted in the problem discussion. Compare
$$632382^{518061}\quad\text{and}\quad 519432^{525806}.$$
The corresponding scores are
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
The first score is larger, so
$$632382^{518061} > 519432^{525806}.$$
This is exactly the kind of comparison performed for every line in the dataset.
Once each line is represented by \(s_i\), the remaining task is a simple maximum search. After processing the first \(k\) lines, maintain the invariant:
$$\text{the stored line number is the line with the largest score among } s_1,s_2,\dots,s_k.$$
When line \(k+1\) is read, compute its score \(s_{k+1}\). If \(s_{k+1}\) exceeds the current best score, replace the stored winner; otherwise keep the old one. By induction, the invariant remains true after every step, and after the final line the stored answer is the desired line number. If two scores were exactly equal, keeping the first one is consistent with the usual strict-update rule used by the implementations.
The C++, Python, and Java implementations read the comma-separated input lines, split each line into a base and an exponent, and convert both parts into numeric values. Blank lines are ignored so that the scan only processes actual data rows.
For every parsed pair \((b,e)\), the implementation computes the score \(e\ln(b)\). That number is the logarithm of \(b^e\), so it carries exactly the ordering information needed for the problem. The C++ implementation uses extended floating-point precision, while the Python and Java implementations use standard double-precision logarithms, but all three are evaluating the same mathematical quantity.
The implementation stores only the best score seen so far and the corresponding 1-indexed line number. Each new score is compared with the current best; if it is larger, both stored values are updated. After the scan reaches the end of the list, the saved line number is printed as the answer.
If the dataset has \(n\) lines, the algorithm performs one logarithm, one multiplication, and one comparison per line, so the running time is \(O(n)\). For Problem 99, \(n=1000\), so the total work is tiny.
The mathematical core needs only \(O(1)\) extra state: the current line number, the best score so far, and the best line number so far. Some implementations may read the small input into memory first because the file is tiny, but the comparison method itself is fundamentally a constant-space streaming scan.
Die Eingabe besteht aus 1000 Zeilen, von denen jede ein Paar \((b,e)\) und damit die Zahl \(b^e\) beschreibt. Gesucht ist nicht der Zahlenwert selbst, sondern die 1-indizierte Zeilennummer, deren Potenz den größten Wert besitzt.
Die Schwierigkeit liegt in der Größe der Zahlen. Schon ein einzelner Ausdruck wie \(519432^{525806}\) ist so groß, dass direkte Potenzberechnung kein sinnvoller Weg ist. Das Problem ist in Wahrheit ein Vergleichsproblem: Für welche Zeile ist \(b_i^{e_i}\) unter allen Eingaben maximal?
Sei \((b_i,e_i)\) das Paar in der \(i\)-ten Zeile und
$$x_i=b_i^{e_i}.$$
Gesucht ist die Zeile mit maximalem \(x_i\). Die Implementierungen konstruieren diese Potenzen nicht direkt, sondern ersetzen jede davon durch einen reellen Score, der dieselbe Ordnung besitzt.
Für jede positive Basis \(b_i\) gilt
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
Daher ordnen wir jeder Zeile den Score
$$s_i=e_i\ln(b_i)$$
zu. Die Zeile mit der größten Potenz ist genau die Zeile mit dem größten Score. Damit verschwindet die Notwendigkeit für Big-Integer-Arithmetik; es bleiben nur noch gewöhnliche Gleitkommawerte moderater Größe.
Welche Logarithmenbasis man verwendet, spielt keine Rolle. Ob \(\log_{10}\), \(\ln\) oder eine andere Basis benutzt wird, alle Scores werden nur mit derselben positiven Konstante skaliert. Der Sieger bleibt also unverändert. Die Implementierungen verwenden den natürlichen Logarithmus aus der Standardbibliothek.
Entscheidend ist, dass \(\ln\) auf den positiven reellen Zahlen streng monoton wächst. Für zwei Zeilen \(i\) und \(j\) gilt deshalb
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
Auch Gleichheit der ursprünglichen Potenzen würde zu gleichen Scores führen. Die Umformung approximiert also nicht die Ordnung, sondern erhält sie exakt. Näherungen treten nur bei der numerischen Auswertung des Logarithmus auf, nicht in der Herleitung selbst.
Ein kleiner Test macht die Idee sofort sichtbar. Vergleiche \(2^{11}\) mit \(3^7\). Die Scores sind
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
Da \(7\ln 3\) größer ist, folgt \(3^7 > 2^{11}\).
Dasselbe Verfahren funktioniert bei den großen Zahlen aus der Problemstellung. Vergleiche
$$632382^{518061}\quad\text{und}\quad 519432^{525806}.$$
Die zugehörigen Scores sind
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
Der erste Score ist größer, also gilt
$$632382^{518061} > 519432^{525806}.$$
Genau diese Art von Vergleich wird für jede Zeile der Datei durchgeführt.
Sobald jede Zeile durch \(s_i\) beschrieben wird, bleibt nur noch eine Maximumssuche. Nach dem Einlesen der ersten \(k\) Zeilen zeigt die gespeicherte Zeilennummer also auf das Maximum von \(s_1,s_2,\dots,s_k\).
Beim Einlesen der Zeile \(k+1\) wird zunächst \(s_{k+1}\) berechnet. Ist dieser Wert größer als der bisher beste Score, wird der gespeicherte Sieger ersetzt, sonst bleibt er erhalten. Induktiv bleibt die Invariante immer wahr, und nach der letzten Zeile ist die gespeicherte Zeilennummer die gesuchte Antwort. Bei einem exakten Gleichstand würde die frühere Zeile erhalten bleiben, weil nur bei strikt größerem Score aktualisiert wird.
Die Implementierungen in C++, Python und Java lesen die kommaseparierten Zeilen, zerlegen jede Zeile in Basis und Exponent und wandeln beide Teile in Zahlen um. Leere Zeilen werden übersprungen, sodass nur echte Datensätze in den Vergleich eingehen.
Für jedes Paar \((b,e)\) berechnet die Implementierung den Score \(e\ln(b)\). Dieser Wert ist gerade der Logarithmus von \(b^e\) und enthält daher genau die Ordnungsinformation, die für das Problem benötigt wird. C++ verwendet erweiterte Präzision, Python und Java arbeiten mit üblicher Double-Präzision, aber mathematisch vergleichen alle drei dieselbe Größe.
Gespeichert werden nur der bisher beste Score und die zugehörige 1-indizierte Zeilennummer. Jeder neue Score wird mit dem aktuellen Bestwert verglichen; ist er größer, werden beide gespeicherten Werte ersetzt. Nach dem letzten Datensatz wird die gemerkte Zeilennummer ausgegeben.
Bei \(n\) Zeilen benötigt der Algorithmus pro Zeile genau einen Logarithmus, eine Multiplikation und einen Vergleich, also insgesamt \(O(n)\) Zeit. Für Problem 99 ist \(n=1000\), daher ist der Rechenaufwand sehr klein.
Der mathematische Kern benötigt nur \(O(1)\) Zusatzspeicher: aktuelle Zeilennummer, bester Score bisher und dazugehörige Zeilennummer. Einige Implementierungen dürfen die kleine Eingabe vollständig laden, weil die Datei winzig ist; die Vergleichsmethode selbst ist jedoch grundsätzlich ein Streaming-Verfahren mit konstantem Zusatzspeicher.
Girdi 1000 satırdan oluşur ve her satırdaki \((b,e)\) çifti \(b^e\) sayısını temsil eder. İstenen şey, bu devasa sayının kendisini üretmek değil, hangi 1-indeksli satırın en büyük değeri verdiğini bulmaktır.
Zorluk sayıların büyüklüğünden gelir. \(519432^{525806}\) gibi tek bir ifade bile doğrudan üs alma ile ele alınamayacak kadar büyüktür. Bu nedenle problem aslında bir hesaplama problemi değil, bir karşılaştırma problemidir: hangi satırdaki \(b_i^{e_i}\) en büyüktür?
\(i\). satırdaki çifti \((b_i,e_i)\) ile gösterelim ve
$$x_i=b_i^{e_i}$$
yazalım. Aradığımız şey en büyük \(x_i\)'yi veren satırdır. Uygulamalar bu sayıları doğrudan oluşturmaz; bunun yerine, aynı sıralamayı koruyan daha küçük bir gerçek sayı skoru kullanır.
Her pozitif taban için
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i)$$
olur. Bu yüzden her satıra
$$s_i=e_i\ln(b_i)$$
skorunu atayabiliriz. En büyük üstel değer tam olarak en büyük skora karşılık gelir. Böylece büyük tam sayılarla uğraşmak yerine, boyutu makul kalan kayan noktalı sayılarla karşılaştırma yapmış oluruz.
Logaritmanın tabanı önemli değildir. \(\log_{10}\), \(\ln\) ya da başka bir taban kullanmak tüm skorları sadece aynı pozitif sabitle çarpar; bu yüzden kazanan satır değişmez. Uygulamalar standart kütüphanedeki doğal logaritmayı kullanır.
Temel nokta şudur: \(\ln\) fonksiyonu pozitif reel sayılar üzerinde sıkı biçimde artandır. Dolayısıyla iki satır \(i\) ve \(j\) için
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
Aynı şekilde, orijinal kuvvetler eşitse logaritmik skorlar da eşit olur. Yani bu dönüşüm sıralamayı yaklaşık olarak değil, tam olarak korur. Yaklaşım yalnızca logaritmanın sayısal hesaplanmasında vardır; matematiksel indirgeme ise kesin sonuç verir.
Küçük bir örnek yöntemi açıkça gösterir. \(2^{11}\) ile \(3^7\)'yi karşılaştıralım. Skorlar
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021$$
olur. İkinci skor daha büyük olduğu için \(3^7 > 2^{11}\) sonucuna ulaşırız.
Aynı yaklaşım problem açıklamasında geçen büyük çift için de çalışır:
$$632382^{518061}\quad\text{ve}\quad 519432^{525806}.$$
Bunların skorları
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604$$
şeklindedir. Birinci skor daha büyük olduğundan
$$632382^{518061} > 519432^{525806}$$
olur. Verideki her satır için yapılan işlem tam olarak bu tür karşılaştırmalardır.
Her satırı \(s_i\) ile temsil ettikten sonra geriye sıradan bir maksimum araması kalır. İlk \(k\) satır işlendiğinde saklanan satır numarası artık \(s_1,s_2,\dots,s_k\) arasındaki en büyük skoru gösterir.
\(k+1\). satır okunduğunda önce \(s_{k+1}\) hesaplanır. Bu değer mevcut en iyi skordan büyükse kayıtlı kazanan güncellenir; değilse eski değer korunur. İndüksiyonla bu değişmez her adımda doğru kalır ve son satır işlendiğinde elde tutulan satır numarası küresel maksimumun satırıdır. Tam eşitlik olsaydı, yalnızca sıkı büyüklükte güncelleme yapıldığı için daha erken satır korunurdu.
C++, Python ve Java uygulamaları virgülle ayrılmış giriş satırlarını okur, her satırı taban ve üs olarak iki parçaya böler ve bunları sayıya çevirir. Boş satırlar atlanır; böylece tarama yalnızca gerçek veri satırları üzerinde yapılır.
Her \((b,e)\) çifti için uygulama \(e\ln(b)\) skorunu hesaplar. Bu sayı doğrudan \(b^e\)'nin logaritmasıdır; dolayısıyla problem için gereken tüm sıralama bilgisi bu tek büyüklüğün içinde taşınır. C++ sürümü daha yüksek kayan nokta hassasiyeti kullanır; Python ve Java sürümleri standart çift duyarlıklı hesap yapar. Buna rağmen üçü de aynı matematiksel niceliği karşılaştırır.
Uygulama yalnızca şimdiye kadar görülen en iyi skoru ve buna ait 1-indeksli satır numarasını saklar. Her yeni skor mevcut en iyi değerle karşılaştırılır; daha büyükse ikisi de güncellenir. Tarama sona erdiğinde saklanan satır numarası cevap olarak yazdırılır.
Veri kümesinde \(n\) satır varsa algoritma satır başına bir logaritma, bir çarpma ve bir karşılaştırma yapar; yani çalışma süresi \(O(n)\) olur. Problem 99 için \(n=1000\) olduğundan bu maliyet çok küçüktür.
Matematiksel çekirdek yalnızca \(O(1)\) ek durum tutar: geçerli satır numarası, şimdiye kadarki en iyi skor ve ona ait satır numarası. Bazı uygulamalar giriş küçük olduğu için dosyanın tamamını okuyabilir; fakat yöntemin özü sabit ek bellekle çalışan akış tabanlı bir taramadır.
La entrada contiene 1000 líneas, y cada línea da un par \((b,e)\) que representa el número \(b^e\). La tarea no es calcular explícitamente esa potencia gigantesca, sino averiguar qué línea, contada desde 1, produce el mayor valor.
La dificultad real es el tamaño de las potencias. Una expresión como \(519432^{525806}\) es demasiado grande para tratarla mediante exponenciación directa. Por eso el problema debe reformularse como un problema de comparación: entre todas las líneas, ¿cuál hace máximo a \(b_i^{e_i}\)?
Sea \((b_i,e_i)\) el par de la línea \(i\), y definamos
$$x_i=b_i^{e_i}.$$
Queremos la línea cuyo \(x_i\) sea máximo. Las implementaciones no construyen cada \(x_i\); en su lugar, asignan a cada línea una puntuación real mucho más manejable que conserva exactamente el mismo orden.
Para toda base positiva \(b_i\), se cumple
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
Esto lleva a la puntuación
$$s_i=e_i\ln(b_i).$$
La línea con la mayor potencia es exactamente la línea con la mayor puntuación. Así desaparece la necesidad de usar enteros gigantes; basta con comparar valores de punto flotante de tamaño moderado.
La base del logaritmo no importa. Usar \(\log_{10}\), \(\ln\) o cualquier otra base solo multiplica todas las puntuaciones por la misma constante positiva, de modo que la línea ganadora no cambia. Las implementaciones usan el logaritmo natural estándar de cada lenguaje.
La observación decisiva es que \(\ln\) es estrictamente creciente en los reales positivos. Por tanto, para dos líneas \(i\) y \(j\),
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
Del mismo modo, si dos potencias originales fueran iguales, sus puntuaciones logarítmicas también lo serían. Es decir, la transformación no aproxima el orden: lo preserva exactamente. La única aproximación aparece al evaluar numéricamente el logaritmo, no en la reducción matemática.
Un ejemplo pequeño deja la idea muy clara. Comparemos \(2^{11}\) con \(3^7\). Sus puntuaciones son
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
Como \(7\ln 3\) es mayor, concluimos que \(3^7 > 2^{11}\).
La misma técnica resuelve el par grande mencionado en la discusión del problema:
$$632382^{518061}\quad\text{y}\quad 519432^{525806}.$$
Las puntuaciones correspondientes son
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
La primera es mayor, así que
$$632382^{518061} > 519432^{525806}.$$
Eso es exactamente lo que se hace, línea por línea, en todo el conjunto de datos.
Una vez que cada línea queda representada por \(s_i\), lo que resta es una búsqueda de máximo. Después de procesar las primeras \(k\) líneas, el número almacenado ya señala la mayor puntuación entre \(s_1,s_2,\dots,s_k\).
Al leer la línea \(k+1\), se calcula \(s_{k+1}\). Si supera a la mejor puntuación actual, el ganador almacenado se reemplaza; si no, se conserva. Por inducción, el invariante sigue siendo cierto en cada paso, y al terminar el archivo el número de línea guardado es la respuesta correcta. Si hubiera empate exacto, la primera línea quedaría como ganadora porque la actualización solo ocurre ante una mejora estricta.
Las implementaciones en C++, Python y Java leen las líneas separadas por comas, dividen cada una en base y exponente y convierten ambas partes a valores numéricos. Las líneas vacías se ignoran para que el recorrido solo procese datos reales.
Para cada par \((b,e)\), la implementación evalúa \(e\ln(b)\). Ese valor es el logaritmo de \(b^e\), así que contiene exactamente la información de orden que necesita el problema. La versión en C++ usa una precisión extendida; las de Python y Java usan precisión doble estándar, pero las tres comparan la misma cantidad matemática.
La implementación solo guarda la mejor puntuación vista hasta el momento y la línea 1-indexada correspondiente. Cada nueva puntuación se compara con la mejor actual; si es mayor, ambas referencias se actualizan. Al final del recorrido, se imprime el número de línea almacenado.
Si hay \(n\) líneas, el algoritmo realiza un logaritmo, una multiplicación y una comparación por línea, así que el tiempo total es \(O(n)\). En el problema concreto, \(n=1000\), por lo que el coste es mínimo.
El núcleo matemático necesita solo \(O(1)\) memoria adicional: el número de línea actual, la mejor puntuación vista y la línea asociada a esa puntuación. Algunas implementaciones pueden cargar primero la entrada completa porque el archivo es pequeño, pero el método de comparación en sí es un escaneo en flujo con espacio constante.
输入共有 1000 行，每一行给出一个 \((b,e)\) 对，表示数 \(b^e\)。题目并不是要求把这个巨大幂真正算出来，而是要求找出哪一个从 1 开始计数的行号对应的数值最大。
难点在于这些幂的规模极其夸张。像 \(519432^{525806}\) 这样的数，直接展开或做高精度幂运算都不是这道题应当采用的思路。问题的本质其实是比较问题：在所有输入对 \((b_i,e_i)\) 中，哪一个使得 \(b_i^{e_i}\) 最大？
设第 \(i\) 行是 \((b_i,e_i)\)，并记
$$x_i=b_i^{e_i}.$$
我们要找的是使 \(x_i\) 最大的那一行。实现并不会真的构造每个 \(x_i\)，而是把每个巨大的幂替换成一个更容易处理的实数“分数”，并且这个分数严格保持原来的大小顺序。
对于每个正底数 \(b_i\)，都有
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
因此可以给第 \(i\) 行定义分数
$$s_i=e_i\ln(b_i).$$
哪个幂最大，哪个分数就最大。这样一来，问题就从“比较天文级别的大整数”变成了“比较普通浮点数”。真正参与比较的对象不再是 \(b_i^{e_i}\) 本身，而是它的对数值。
这里使用哪一种对数底都无所谓。无论是 \(\log_{10}\)、\(\ln\) 还是其他底数，所有分数都只会整体乘上同一个正的常数，最大值所在的行不会改变。实现选择自然对数，只是因为标准库直接提供了这个函数。
关键事实是：\(\ln\) 在正实数范围上是严格递增函数。因此对任意两行 \(i\) 和 \(j\)，有
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
如果原来的两个幂相等，那么对应的对数分数也完全相等。也就是说，这一步并不是“用一个近似指标替代原问题”，而是把原问题精确地改写成了另一个更容易处理的比较问题。近似只出现在机器如何计算 \(\ln\) 的数值时，而不是出现在数学推导本身。
先看一个很小的例子，比较 \(2^{11}\) 和 \(3^7\)。它们的对数分数分别是
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
第二个分数更大，所以 \(3^7 > 2^{11}\)。这个结论完全不需要真的算出 \(2048\) 和 \(2187\)，而且对于更大的数同样成立。
再看题目讨论里常见的那一对大数：
$$632382^{518061}\quad\text{和}\quad 519432^{525806}.$$
它们的分数为
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
第一个分数明显更大，因此
$$632382^{518061} > 519432^{525806}.$$
整道题的核心就是对 1000 行都做这种比较，然后找出分数最大的那一行。
一旦每一行都被表示成 \(s_i\)，剩下的任务就是一次线性扫描中的最大值维护。处理完前 \(k\) 行之后，当前保存的行号就对应着 \(s_1,s_2,\dots,s_k\) 中最大的那个分数。
当读到第 \(k+1\) 行时，先计算 \(s_{k+1}\)。如果它比当前最优分数更大，就更新“最佳行号”和“最佳分数”；否则保持原值。这个过程显然保持不变式成立。于是当最后一行处理完后，保存下来的行号就是全局最大值对应的答案。若恰好出现完全相等的分数，那么由于实现只在“严格更大”时才更新，较早出现的那一行会被保留下来。
C++、Python 和 Java 实现都会读取以逗号分隔的输入行，把每一行拆成底数与指数两部分，再转换为数值类型。空白行会被跳过，这样后续扫描只处理真正的数据记录。
对每个 \((b,e)\)，实现都会计算 \(e\ln(b)\)。这个值正好是 \(b^e\) 的对数，因此它完整保留了题目所需要的大小顺序信息。C++ 版本使用更高一些的浮点精度，Python 和 Java 使用标准双精度，但三者比较的数学对象完全相同。
实现只需要保存到目前为止见过的最佳分数，以及与之对应的 1-indexed 行号。每读入一行，就把新分数与当前最佳分数比较；若更大，则更新两者。扫描结束后，输出保存的行号即可。
如果一共有 \(n\) 行，那么算法对每一行执行一次对数计算、一次乘法和一次比较，因此总时间复杂度是 \(O(n)\)。在本题中 \(n=1000\)，所以计算量非常小。
从算法本质看，只需要 \(O(1)\) 的额外状态：当前行号、目前最佳分数、以及最佳分数对应的行号。有些实现会因为输入很小而先把文件全部读入内存，但这不是方法本身的需要；核心思想本来就是一个常数额外空间的流式扫描。
Во входных данных 1000 строк, и каждая строка содержит пару \((b,e)\), представляющую число \(b^e\). Требуется не вычислить это гигантское число явно, а определить, какая строка с нумерацией от 1 даёт наибольшее значение.
Основная трудность связана с масштабом чисел. Даже выражение вроде \(519432^{525806}\) слишком велико для прямого возведения в степень как рабочего метода решения. Поэтому задача должна быть переформулирована как задача сравнения: для какой строки величина \(b_i^{e_i}\) максимальна?
Пусть в строке с номером \(i\) записана пара \((b_i,e_i)\), и пусть
$$x_i=b_i^{e_i}.$$
Нужно найти строку с максимальным \(x_i\). Реализации не строят эти степени напрямую. Вместо этого каждой строке сопоставляется гораздо более компактная вещественная оценка, которая сохраняет тот же порядок.
Для любого положительного основания \(b_i\) выполняется
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
Поэтому естественно определить оценку
$$s_i=e_i\ln(b_i).$$
Строка с наибольшей степенью совпадает со строкой с наибольшей оценкой. Тем самым задача уходит от работы с колоссальными целыми числами и сводится к сравнению обычных чисел с плавающей точкой умеренного размера.
Основание логарифма несущественно. Если использовать \(\log_{10}\), \(\ln\) или любой другой логарифм, все оценки просто умножатся на одну и ту же положительную константу, а значит строка-победитель не изменится. В реализациях используется стандартный натуральный логарифм.
Ключевой факт состоит в том, что функция \(\ln\) строго возрастает на положительных вещественных числах. Поэтому для любых двух строк \(i\) и \(j\)
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
Точно так же равенство исходных степеней привело бы к равенству логарифмических оценок. Значит, преобразование не приближает порядок, а сохраняет его в точности. Приближение возникает только на этапе численного вычисления логарифма машиной, но не в самой математической редукции.
Небольшой пример мгновенно показывает идею. Сравним \(2^{11}\) и \(3^7\). Их оценки равны
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
Поскольку вторая оценка больше, получаем \(3^7 > 2^{11}\).
Тот же приём работает и для большой пары, фигурирующей в обсуждении задачи:
$$632382^{518061}\quad\text{и}\quad 519432^{525806}.$$
Соответствующие оценки таковы:
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
Первая оценка больше, следовательно
$$632382^{518061} > 519432^{525806}.$$
Именно такой сравнительный шаг выполняется для каждой строки входного списка.
После замены каждой строки на \(s_i\) остаётся обычный поиск максимума. После обработки первых \(k\) строк сохранённый номер уже указывает на наибольшую оценку среди \(s_1,s_2,\dots,s_k\).
Когда читается строка \(k+1\), сначала вычисляется \(s_{k+1}\). Если этот результат больше текущей лучшей оценки, сохранённый победитель заменяется; иначе он остаётся прежним. По индукции инвариант верен после каждого шага, а значит после последней строки сохранённый номер и есть правильный ответ. Если бы встретилось точное равенство, сохранилась бы более ранняя строка, потому что обновление происходит только при строгом улучшении.
Реализации на C++, Python и Java читают строки, разделённые запятыми, разбивают каждую строку на основание и показатель и преобразуют обе части в числовой вид. Пустые строки игнорируются, чтобы в проходе участвовали только реальные данные.
Для каждой пары \((b,e)\) реализация вычисляет \(e\ln(b)\). Это значение является логарифмом числа \(b^e\), а значит содержит всю информацию о порядке, которая нужна задаче. В версии на C++ используется повышенная точность, а в Python и Java стандартная двойная точность, но математически сравнивается одна и та же величина.
Хранятся только лучшая оценка, увиденная на данный момент, и соответствующий ей 1-indexed номер строки. Каждая новая оценка сравнивается с текущей лучшей; если она больше, обе сохранённые величины обновляются. После окончания прохода печатается сохранённый номер строки.
Если вход содержит \(n\) строк, алгоритм выполняет один логарифм, одно умножение и одно сравнение на строку, то есть работает за \(O(n)\). Для Problem 99 имеем \(n=1000\), так что вычислительная нагрузка крайне мала.
С математической точки зрения требуется только \(O(1)\) дополнительной памяти: текущий номер строки, лучшая оценка и номер строки с этой оценкой. Некоторые реализации могут заранее прочитать весь маленький файл, но сам метод по сути является потоковым проходом с постоянным дополнительным состоянием.
تتكون المدخلات من 1000 سطر، وفي كل سطر زوج \((b,e)\) يمثل العدد \(b^e\). المطلوب ليس حساب هذه القوة الهائلة صراحة، بل تحديد رقم السطر ذي الفهرسة التي تبدأ من 1 والذي يعطي أكبر قيمة عددية.
الصعوبة الحقيقية هي ضخامة الأعداد. تعبير مثل \(519432^{525806}\) كبير إلى درجة تجعل الحساب المباشر للأس غير مناسب هنا. لذلك فالمسألة في جوهرها ليست مسألة إنشاء الأعداد نفسها، بل مسألة مقارنة: أي سطر يحقق أكبر قيمة لـ \(b_i^{e_i}\)؟
لنكتب الزوج الموجود في السطر \(i\) على الصورة \((b_i,e_i)\)، ثم نعرّف
$$x_i=b_i^{e_i}.$$
نريد السطر الذي يجعل \(x_i\) أعظم ما يمكن. لا تقوم التطبيقات ببناء هذه القوى مباشرة، بل تستبدل كل قوة هائلة بدرجة حقيقية أصغر بكثير وتحافظ تمامًا على نفس الترتيب.
لكل أساس موجب \(b_i\) لدينا
$$\ln(x_i)=\ln\!\left(b_i^{e_i}\right)=e_i\ln(b_i).$$
ولذلك نربط بكل سطر الدرجة
$$s_i=e_i\ln(b_i).$$
السطر الذي يملك أكبر قوة هو نفسه السطر الذي يملك أكبر درجة. بهذه الخطوة ننتقل من مقارنة أعداد صحيحة هائلة الحجم إلى مقارنة قيم ذات فاصلة عائمة يمكن التعامل معها بسهولة.
قاعدة اللوغاريتم لا تؤثر في الإجابة. سواء استُخدم \(\log_{10}\) أو \(\ln\) أو أي لوغاريتم آخر، فإن جميع الدرجات تتغير بالضرب في ثابت موجب واحد فقط، ولذلك لا يتغير السطر الفائز. تستخدم التطبيقات اللوغاريتم الطبيعي الموجود في المكتبات القياسية.
الحقيقة الأساسية هي أن \(\ln\) دالة متزايدة تمامًا على الأعداد الحقيقية الموجبة. لذلك لأي سطرين \(i\) و\(j\) نحصل على
$$x_i > x_j \iff \ln(x_i) > \ln(x_j) \iff e_i\ln(b_i) > e_j\ln(b_j).$$
وكذلك إذا كانت القوتان الأصليتان متساويتين فستكون الدرجتان اللوغاريتميتان متساويتين أيضًا. هذا يعني أن التحويل لا يحافظ على الترتيب تقريبًا فحسب، بل يحافظ عليه بدقة رياضية كاملة. التقريب الوحيد يظهر في التقييم العددي للوغاريتم بالحاسوب، لا في البرهان نفسه.
لنبدأ بمثال صغير يوضح الفكرة مباشرة. عند مقارنة \(2^{11}\) مع \(3^7\) تكون الدرجات
$$11\ln 2 \approx 7.624618986,\qquad 7\ln 3 \approx 7.690286021.$$
وبما أن الدرجة الثانية أكبر، نستنتج أن \(3^7 > 2^{11}\).
والطريقة نفسها تعمل مع الزوج الكبير المذكور في وصف المسألة:
\(632382^{518061}\) و \(519432^{525806}\).
درجتاهما هما
$$518061\ln 632382 \approx 6919869.733217769$$
$$525806\ln 519432 \approx 6919865.228473604.$$
الدرجة الأولى أكبر، ومن ثم
$$632382^{518061} > 519432^{525806}.$$
هذا هو بالضبط نوع المقارنة الذي يُجرى لكل سطر في مجموعة البيانات.
بعد تمثيل كل سطر بالدرجة \(s_i\)، يتبقى فقط البحث عن القيمة العظمى أثناء مسح واحد. وبعد معالجة أول \(k\) أسطر يكون رقم السطر المخزن هو صاحب أكبر درجة بين \(s_1,s_2,\dots,s_k\).
عند قراءة السطر \(k+1\) نحسب أولًا \(s_{k+1}\). إذا كانت هذه الدرجة أكبر من أفضل درجة حالية فإننا نحدّث السطر الفائز؛ وإلا نترك القيم كما هي. بالاستقراء يبقى هذا الثابت صحيحًا بعد كل خطوة، ولذلك يكون رقم السطر المخزن بعد نهاية الملف هو الجواب الصحيح. ولو حدث تعادل تام فسيبقى السطر الأسبق محفوظًا لأن التحديث يتم فقط عند وجود تحسن صارم.
تقوم تطبيقات C++ وPython وJava بقراءة الأسطر المفصولة بفواصل، ثم تقسيم كل سطر إلى أساس وأس، ثم تحويل الجزأين إلى قيم عددية. وتُهمل الأسطر الفارغة حتى يقتصر المسح على السجلات الفعلية فقط.
لكل زوج \((b,e)\) تحسب التطبيقات القيمة \(e\ln(b)\). هذه القيمة هي لوغاريتم \(b^e\)، ولذلك فهي تحمل كل معلومات الترتيب المطلوبة للمسألة. يستخدم تنفيذ C++ دقة موسعة، بينما يستخدم Python وJava الدقة الثنائية القياسية، لكن الكمية الرياضية المقارنة هي نفسها في الحالات الثلاث.
لا تحتاج التطبيقات إلا إلى أفضل درجة شوهدت حتى الآن ورقم السطر الموافق لها مع فهرسة تبدأ من 1. تُقارن كل درجة جديدة مع أفضل درجة حالية؛ فإذا كانت أكبر، تُحدَّث القيم المخزنة. وبعد نهاية المسح يُطبع رقم السطر المحفوظ بوصفه الجواب.
إذا كان عدد الأسطر \(n\)، فإن الخوارزمية تنفذ لوغاريتمًا واحدًا وضربًا واحدًا ومقارنة واحدة لكل سطر، ولذلك فإن الزمن الكلي هو \(O(n)\). وفي هذه المسألة تحديدًا لدينا \(n=1000\)، لذا فالكلفة صغيرة جدًا.
اللب الرياضي يحتاج فقط إلى حالة إضافية مقدارها \(O(1)\): رقم السطر الحالي، وأفضل درجة حتى الآن، ورقم السطر المرتبط بها. قد تقرأ بعض التطبيقات الملف الصغير كاملًا إلى الذاكرة أولًا، لكن منهج المقارنة نفسه هو في الأساس مسح تدفقي ذو مساحة إضافية ثابتة.