For a fixed \(n\), the input is generated deterministically rather than read externally. Each troll contributes a triple \((a_i,b_i,w_i)\): a height contribution, a geometric offset, and a reward. We must choose a subset and an order so that every chosen troll satisfies the standing condition implied by the geometry, while the total reward is maximized.
The key observation is that the geometry can be rewritten as an ordinary completion-deadline constraint. After that reduction, the problem becomes a weighted single-machine scheduling problem, which the implementation solves with one-dimensional dynamic programming.
Let the generated data for troll \(i\) be \((a_i,b_i,w_i)\), and let
$$A=\sum_{i=0}^{n-1} a_i$$
be the total generated height. The central threshold is
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
The implementations use the modular sequence
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
For \(i=0,1,\dots,n-1\), the \(i\)-th troll receives
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
So every generated number lies in the interval \([50,150]\), and once \(n\) is fixed the whole instance is fixed as well. There is no randomness left in the mathematical problem.
Instead of evaluating \(\sqrt{2}\) numerically, the implementation computes \(\Theta\) as the smallest integer \(x\) satisfying
$$2x^2\ge A^2.$$
This is exactly the same as \(x\ge A/\sqrt{2}\), hence the smallest such integer is \(\lceil A/\sqrt{2}\rceil\). Using only integer comparisons avoids floating-point edge cases and gives identical behavior in all three languages.
Suppose a chosen troll begins after cumulative occupied height \(s\) has already been placed. The geometry encoded by the implementation yields the feasibility inequality
$$A+b_i-s\ge \Theta.$$
Equivalently, the troll must start no later than
$$s\le A+b_i-\Theta.$$
If selecting that troll consumes \(a_i\) further units of height, then its completion time is \(C_i=s+a_i\). Therefore the same condition can be rewritten as
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
So each troll turns into a job with duration \(a_i\), reward \(w_i\), and completion deadline \(d_i\).
For a single machine with processing times and deadlines, a chosen subset is feasible if and only if it is feasible when executed in nondecreasing deadline order. This means we do not need to search over all permutations.
After sorting the jobs so that
$$d_1\le d_2\le \cdots \le d_m,$$
a subset is feasible exactly when every chosen prefix finishes on time. If the completion times in that order are \(C_1,C_2,\dots\), the required condition is simply
$$C_j\le d_j.$$
After sorting, let \(\mathrm{dp}[t]\) denote the maximum total reward among feasible chosen subsets whose total occupied time is exactly \(t\). Initially only time \(0\) is reachable.
When we process one job with duration \(a\), reward \(w\), and deadline \(d\), the 0/1 transition is
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
The update runs in descending \(t\), which prevents the same job from being reused inside one iteration. The final answer is
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
The first five generated triples are \((51,55,75)\), \((74,69,145)\), \((121,102,108)\), \((138,86,129)\), and \((142,89,127)\).
Hence
$$A=51+74+121+138+142=526.$$
The threshold is
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
because \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
The completion deadlines are therefore
$$260,\ 297,\ 377,\ 378,\ 385.$$
The optimal feasible subset is the 2nd, 4th, and 5th trolls. Their total occupied time is
$$74+138+142=354,$$
their total reward is
$$145+129+127=401,$$
and their completion times in deadline order are \(74\), \(212\), and \(354\), which satisfy \(74\le 297\), \(212\le 378\), and \(354\le 385\). This matches the built-in checkpoint.
The C++, Python, and Java implementations follow the same sequence of steps. First they stream the powers of \(5\) modulo \(10^9+7\), reduce each term into the interval \([50,150]\), and group every three values into one troll.
Next they sum all generated heights and recover \(\Theta\) by integer binary search, so no floating-point square root is needed. Every troll is then converted into a scheduling job with a duration, a reward, and a completion deadline.
The jobs are sorted by increasing deadline, with shorter duration used only as a deterministic tie-breaker. A one-dimensional DP array stores the best reward for each reachable total occupied time, using a large negative sentinel for impossible states. Each job updates that array from right to left, preserving the 0/1 nature of the choice.
After all jobs have been processed, the implementation scans the DP table and returns the largest reachable reward. The algorithmic structure is identical across the three languages; only the surrounding syntax changes.
Let \(D=\max_i d_i\). Generating the data and building the job list cost \(O(n)\) time. Sorting costs \(O(n\log n)\). The dominant part is the dynamic program, which performs a descending time scan up to the relevant deadline for each job, so the total running time is \(O(nD)\).
The memory usage is \(O(D)\), because only one DP array is kept. Since every generated number lies between \(50\) and \(150\), the total height \(A\) is \(O(n)\), and \(D\) is also \(O(n)\). For this particular generator the practical growth is therefore roughly quadratic in \(n\), with linear memory.
Für ein festes \(n\) werden die Eingabedaten nicht extern eingelesen, sondern deterministisch erzeugt. Jeder Troll liefert ein Tripel \((a_i,b_i,w_i)\): einen Höhenbeitrag, einen geometrischen Offset und einen Gewinnwert. Gesucht ist eine Teilmenge mit Reihenfolge, sodass jeder ausgewählte Troll die durch die Geometrie vorgegebene Bedingung erfüllt und die Summe der Gewinne maximal wird.
Die entscheidende Beobachtung ist, dass sich diese Geometrie in eine gewöhnliche Deadline-Bedingung für Fertigstellungszeiten umformulieren lässt. Danach bleibt ein gewichtetes Einmaschinen-Scheduling-Problem, das per eindimensionaler dynamischer Programmierung gelöst wird.
Sei \((a_i,b_i,w_i)\) das erzeugte Tripel des \(i\)-ten Trolls, und setze
$$A=\sum_{i=0}^{n-1} a_i.$$
Die zentrale Schwelle ist
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
Die Implementierungen verwenden die modulare Folge
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
Für \(i=0,1,\dots,n-1\) erhält der \(i\)-te Troll das Tripel
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
Damit liegt jede erzeugte Zahl im Intervall \([50,150]\), und für festes \(n\) ist die gesamte Instanz vollständig festgelegt. Ein zufälliger Anteil bleibt mathematisch nicht übrig.
Statt \(\sqrt{2}\) numerisch auszuwerten, berechnet die Implementierung \(\Theta\) als kleinste ganze Zahl \(x\) mit
$$2x^2\ge A^2.$$
Das ist exakt äquivalent zu \(x\ge A/\sqrt{2}\), also ist die kleinste solche Zahl genau \(\lceil A/\sqrt{2}\rceil\). Reine Ganzzahlarithmetik vermeidet Rundungsprobleme und sorgt in allen drei Sprachen für identisches Verhalten.
Beginnt ein ausgewählter Troll erst dann, wenn bereits eine kumulierte Höhe \(s\) aufgebaut wurde, dann liefert die in der Implementierung kodierte Geometrie die Bedingung
$$A+b_i-s\ge \Theta.$$
Äquivalent dazu darf der Troll spätestens bei
$$s\le A+b_i-\Theta$$
beginnen. Wenn die Auswahl dieses Trolls weitere \(a_i\) Höheneinheiten verbraucht, ist seine Fertigstellungszeit \(C_i=s+a_i\). Damit wird dieselbe Bedingung zu
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
Jeder Troll wird also zu einem Job mit Bearbeitungszeit \(a_i\), Gewinn \(w_i\) und Deadline \(d_i\).
Für eine einzelne Maschine mit Bearbeitungszeiten und Deadlines ist eine gewählte Teilmenge genau dann zulässig, wenn sie in nichtfallender Deadline-Reihenfolge zulässig ist. Man muss also keine Permutationen bruteforcen.
Nach dem Sortieren mit
$$d_1\le d_2\le \cdots \le d_m$$
ist eine Teilmenge genau dann zulässig, wenn jedes gewählte Präfix rechtzeitig fertig wird. Haben die gewählten Jobs in dieser Reihenfolge die Fertigstellungszeiten \(C_1,C_2,\dots\), so lautet die Bedingung
$$C_j\le d_j.$$
Nach dem Sortieren bezeichne \(\mathrm{dp}[t]\) den maximalen Gesamtgewinn unter allen zulässigen Teilmengen mit gesamter belegter Zeit \(t\). Anfangs ist nur Zeit \(0\) erreichbar.
Für einen Job mit Bearbeitungszeit \(a\), Gewinn \(w\) und Deadline \(d\) lautet der 0/1-Übergang
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
Die Aktualisierung läuft in absteigendem \(t\), damit derselbe Job innerhalb einer Iteration nicht mehrfach benutzt werden kann. Das Endergebnis ist
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
Die ersten fünf erzeugten Tripel sind \((51,55,75)\), \((74,69,145)\), \((121,102,108)\), \((138,86,129)\) und \((142,89,127)\).
Daraus folgt
$$A=51+74+121+138+142=526.$$
Die Schwelle ist
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
denn \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
Die Fertigstellungs-Deadlines lauten damit
$$260,\ 297,\ 377,\ 378,\ 385.$$
Die optimale zulässige Teilmenge besteht aus dem 2., 4. und 5. Troll. Ihre gesamte belegte Zeit ist
$$74+138+142=354,$$
ihr Gesamtgewinn ist
$$145+129+127=401,$$
und ihre Fertigstellungszeiten in Deadline-Reihenfolge sind \(74\), \(212\) und \(354\). Diese erfüllen \(74\le 297\), \(212\le 378\) und \(354\le 385\). Genau das ist der eingebaute Kontrollwert.
Die Implementierungen in C++, Python und Java folgen derselben Abfolge. Zuerst werden die Potenzen von \(5\) modulo \(10^9+7\) fortlaufend erzeugt, in den Bereich \([50,150]\) projiziert und jeweils zu Dreiergruppen für einen Troll zusammengefasst.
Anschließend werden alle erzeugten Höhen aufsummiert und \(\Theta\) per ganzzahliger binärer Suche bestimmt, also ohne Fließkomma-Wurzel. Danach wird jeder Troll in einen Scheduling-Job mit Bearbeitungszeit, Gewinn und Deadline umgewandelt.
Die Jobs werden nach wachsender Deadline sortiert; kürzere Bearbeitungszeit dient nur als deterministischer Tie-Break. Ein eindimensionales DP-Array speichert den besten Gewinn für jede erreichbare Gesamtzeit, wobei ein großer negativer Wächterwert unmögliche Zustände markiert. Jeder Job aktualisiert dieses Array von rechts nach links, damit die Auswahl strikt 0/1 bleibt.
Nach Verarbeitung aller Jobs wird das DP-Array nach dem größten erreichbaren Gewinn durchsucht. Die Algorithmik ist in allen drei Sprachen gleich; nur die Syntax unterscheidet sich.
Sei \(D=\max_i d_i\). Das Erzeugen der Daten und das Aufbauen der Jobliste benötigen \(O(n)\) Zeit. Das Sortieren kostet \(O(n\log n)\). Der dominante Teil ist die dynamische Programmierung, die für jeden Job einen absteigenden Scan bis zur relevanten Deadline ausführt, also insgesamt \(O(nD)\) Zeit.
Der Speicherverbrauch ist \(O(D)\), weil nur ein einziges DP-Array gehalten wird. Da jede erzeugte Zahl zwischen \(50\) und \(150\) liegt, ist die Gesamthöhe \(A=O(n)\), und damit ist auch \(D=O(n)\). Für diesen speziellen Generator wächst die Laufzeit daher praktisch ungefähr quadratisch in \(n\), bei linearem Speicher.
Sabit bir \(n\) için girdi dışarıdan okunmaz; tamamen deterministik olarak üretilir. Her troll için \((a_i,b_i,w_i)\) biçiminde üç sayı vardır: bir yükseklik katkısı, geometrik bir ofset ve ödül değeri. Amaç, bu trolllerden bir alt küme ve sıralama seçerek her seçilen trollün geometrik durma koşulunu sağlamasını ve toplam ödülün en büyük olmasını sağlamaktır.
Kritik fikir, geometrik koşulun sıradan bir bitiş son zamanı kısıtına dönüştürülebilmesidir. Bu dönüşüm yapıldıktan sonra problem, tek makineli ağırlıklı zamanlama problemine indirgenir ve çözüm tek boyutlu dinamik programlama ile gelir.
\(i\). troll için üretilen üçlü \((a_i,b_i,w_i)\) olsun. Toplam yükseklik
$$A=\sum_{i=0}^{n-1} a_i$$
ve temel eşik
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil$$
olarak tanımlanır.
Uygulamalar şu modüler diziyi kullanır:
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
\(i=0,1,\dots,n-1\) için \(i\). trollün üçlüsü
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right)$$
şeklindedir. Böylece her üretilen sayı \([50,150]\) aralığındadır ve \(n\) sabitlenince örnek tamamen sabit olur. Yani çözümde olasılıksal bir argüman yoktur.
\(\sqrt{2}\) için kayan nokta hesabı yapmak yerine, uygulama \(\Theta\)'yı
$$2x^2\ge A^2$$
eşitsizliğini sağlayan en küçük tam sayı \(x\) olarak bulur. Bu tam olarak \(x\ge A/\sqrt{2}\) ile eşdeğerdir; dolayısıyla elde edilen sayı \(\lceil A/\sqrt{2}\rceil\)'dir. Sadece tam sayı karşılaştırmaları kullanmak, üç dilde de aynı davranışı garanti eder.
Seçilen bir troll, öncesinde toplam \(s\) kadar yükseklik yerleştirildikten sonra başlıyorsa, uygulamanın kullandığı geometri şu koşulu verir:
$$A+b_i-s\ge \Theta.$$
Bu da trollün en geç
$$s\le A+b_i-\Theta$$
anında başlaması gerektiği anlamına gelir. Bu trollü seçmek \(a_i\) kadar ek yükseklik tükettiği için bitiş zamanı \(C_i=s+a_i\) olur. O halde aynı koşul
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i$$
biçiminde yazılır. Böylece her troll, süresi \(a_i\), ödülü \(w_i\) ve bitiş deadline'ı \(d_i\) olan bir işe dönüşür.
Tek makineli, süreli ve deadline'lı işlerde bir alt küme uygunsa, artmayan değil artan deadline sırasıyla da uygundur. Bu yüzden tüm permütasyonları denemek gerekmez.
İşler
$$d_1\le d_2\le \cdots \le d_m$$
şeklinde sıralandığında, bir alt kümenin uygun olması her seçili önekin zamanında bitmesine eşdeğerdir. Bu sıradaki bitiş zamanları \(C_1,C_2,\dots\) ise koşul
$$C_j\le d_j.$$
şeklindedir.
Sıralamadan sonra \(\mathrm{dp}[t]\), toplam kullanılan süresi tam \(t\) olan uygun alt kümeler arasındaki en yüksek toplam ödülü göstersin. Başlangıçta yalnızca \(t=0\) durumu erişilebilirdir.
Süresi \(a\), ödülü \(w\), deadline'ı \(d\) olan bir iş işlendiğinde 0/1 geçişi
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d)$$
olur. Döngünün \(t\) üzerinde azalan yönde gitmesi gerekir; aksi halde aynı iş bir tur içinde birden fazla kez kullanılabilir. Sonuç
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i$$
değeridir.
İlk beş üretilen üçlü \((51,55,75)\), \((74,69,145)\), \((121,102,108)\), \((138,86,129)\) ve \((142,89,127)\) olur.
Buradan
$$A=51+74+121+138+142=526$$
elde edilir. Eşik
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372$$
çünkü \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
Buna karşılık bitiş deadline'ları
$$260,\ 297,\ 377,\ 378,\ 385$$
olur. En iyi uygun alt küme 2., 4. ve 5. trolllerden oluşur. Toplam kullanılan süre
$$74+138+142=354,$$
toplam ödül ise
$$145+129+127=401$$
eder. Deadline sırasındaki bitiş zamanları \(74\), \(212\) ve \(354\) olup sırasıyla \(297\), \(378\) ve \(385\) sınırlarını aşmaz. Bu değer, yerleşik kontrol sonucuyla aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(5\)'in \(10^9+7\) modundaki kuvvetleri ardışık olarak üretilir, her terim \([50,150]\) aralığına indirgenir ve her üç sayı bir troll olarak gruplanır.
Daha sonra tüm yükseklikler toplanır ve \(\Theta\) tam sayılı ikili arama ile bulunur; böylece kayan noktalı karekök hesabına ihtiyaç kalmaz. Sonra her troll bir süre, ödül ve bitiş deadline'ı içeren zamanlama işine dönüştürülür.
İşler artan deadline'a göre sıralanır; eşitlik durumunda daha kısa süre yalnızca deterministik bir bağ bozucu olarak kullanılır. Tek boyutlu DP dizisi, erişilebilir her toplam süre için en iyi ödülü saklar ve imkansız durumlar için büyük negatif bir işaret değeri taşır. Her iş bu diziyi sağdan sola günceller; böylece seçim 0/1 olarak kalır.
Tüm işler işlendiğinde DP tablosundaki en büyük erişilebilir ödül okunur. Algoritmanın özü üç dilde de aynıdır; değişen sadece sözdizimidir.
\(D=\max_i d_i\) olsun. Veriyi üretmek ve iş listesini oluşturmak \(O(n)\) zaman alır. Sıralama \(O(n\log n)\) maliyetlidir. Baskın kısım dinamik programlamadır; her iş için ilgili deadline'a kadar azalan bir zaman taraması yapıldığı için toplam süre \(O(nD)\) olur.
Bellek kullanımı \(O(D)\)'dir, çünkü yalnızca tek bir DP dizisi tutulur. Üretilen her sayı \(50\) ile \(150\) arasında olduğundan toplam yükseklik \(A=O(n)\) ve dolayısıyla \(D=O(n)\) olur. Bu özel üretici için pratik büyüme yaklaşık kareseldir, fakat bellek lineerdir.
Para un \(n\) fijo, la entrada no se lee desde fuera: se genera de forma determinista. Cada troll aporta una terna \((a_i,b_i,w_i)\): una contribución de altura, un desplazamiento geométrico y una recompensa. Hay que elegir un subconjunto y un orden de modo que cada troll elegido satisfaga la condición geométrica de apoyo y que la suma total de recompensas sea máxima.
La observación decisiva es que la geometría puede reescribirse como una restricción ordinaria de plazo de finalización. Tras esa reducción, el problema pasa a ser uno de planificación ponderada en una sola máquina, resuelto mediante programación dinámica unidimensional.
Sea \((a_i,b_i,w_i)\) la terna generada para el troll \(i\), y definamos
$$A=\sum_{i=0}^{n-1} a_i.$$
El umbral central es
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
Las implementaciones usan la sucesión modular
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
Para \(i=0,1,\dots,n-1\), el troll \(i\) recibe
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
Así, cada valor generado pertenece a \([50,150]\), y una vez fijado \(n\) la instancia completa queda totalmente determinada. No hay ningún componente probabilístico en el análisis.
En vez de evaluar \(\sqrt{2}\) con coma flotante, la implementación obtiene \(\Theta\) como el menor entero \(x\) que satisface
$$2x^2\ge A^2.$$
Eso es exactamente equivalente a \(x\ge A/\sqrt{2}\), así que el menor tal entero es \(\lceil A/\sqrt{2}\rceil\). Trabajar solo con comparaciones enteras evita problemas de redondeo y mantiene el mismo comportamiento en los tres lenguajes.
Supongamos que un troll elegido empieza después de que ya se haya colocado una altura acumulada \(s\). La geometría usada por la implementación conduce a la desigualdad
$$A+b_i-s\ge \Theta.$$
Equivalentemente, el troll debe empezar no más tarde de
$$s\le A+b_i-\Theta.$$
Como seleccionar ese troll consume \(a_i\) unidades adicionales de altura, su tiempo de finalización es \(C_i=s+a_i\). Por tanto, la misma condición se reescribe como
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
Cada troll se convierte así en un trabajo con duración \(a_i\), recompensa \(w_i\) y deadline de finalización \(d_i\).
En planificación sobre una sola máquina con duraciones y deadlines, un subconjunto elegido es factible si y solo si lo es en orden no decreciente de deadline. Por eso no hace falta explorar todas las permutaciones.
Después de ordenar de manera que
$$d_1\le d_2\le \cdots \le d_m,$$
un subconjunto es factible exactamente cuando cada prefijo elegido termina a tiempo. Si los tiempos de finalización en ese orden son \(C_1,C_2,\dots\), la condición es
$$C_j\le d_j.$$
Tras ordenar, sea \(\mathrm{dp}[t]\) la recompensa total máxima entre los subconjuntos factibles cuyo tiempo total ocupado es exactamente \(t\). Al principio solo el tiempo \(0\) es alcanzable.
Cuando se procesa un trabajo con duración \(a\), recompensa \(w\) y deadline \(d\), la transición 0/1 es
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
La actualización debe recorrer \(t\) en orden descendente; de lo contrario, un mismo trabajo podría reutilizarse dentro de la misma iteración. La respuesta final es
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
Las primeras cinco ternas generadas son \((51,55,75)\), \((74,69,145)\), \((121,102,108)\), \((138,86,129)\) y \((142,89,127)\).
Entonces
$$A=51+74+121+138+142=526.$$
El umbral es
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
porque \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
Los deadlines de finalización resultan ser
$$260,\ 297,\ 377,\ 378,\ 385.$$
El subconjunto factible óptimo usa los trolls 2, 4 y 5. Su tiempo total ocupado es
$$74+138+142=354,$$
su recompensa total es
$$145+129+127=401,$$
y sus tiempos de finalización en orden de deadline son \(74\), \(212\) y \(354\), que satisfacen \(74\le 297\), \(212\le 378\) y \(354\le 385\). Ese valor coincide con la comprobación incorporada.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero generan en flujo las potencias de \(5\) módulo \(10^9+7\), reducen cada término al intervalo \([50,150]\) y agrupan cada tres valores en un troll.
Después suman todas las alturas generadas y recuperan \(\Theta\) mediante una búsqueda binaria entera, sin recurrir a raíces cuadradas en coma flotante. Luego cada troll se transforma en un trabajo de planificación con duración, recompensa y deadline de finalización.
Los trabajos se ordenan por deadline creciente; una duración menor solo se usa como desempate determinista. Un arreglo DP unidimensional guarda la mejor recompensa para cada tiempo total alcanzable, usando un gran centinela negativo para los estados imposibles. Cada trabajo actualiza ese arreglo de derecha a izquierda, preservando la semántica 0/1.
Al final, la implementación recorre la tabla DP y devuelve la mayor recompensa alcanzable. La estructura algorítmica es la misma en los tres lenguajes; solo cambia la sintaxis.
Sea \(D=\max_i d_i\). Generar los datos y construir la lista de trabajos cuesta \(O(n)\) tiempo. Ordenar cuesta \(O(n\log n)\). La parte dominante es la programación dinámica, que realiza para cada trabajo un barrido descendente del tiempo hasta el deadline relevante, dando \(O(nD)\) tiempo total.
La memoria es \(O(D)\), porque solo se mantiene un arreglo DP. Como todos los valores generados están entre \(50\) y \(150\), la altura total \(A\) es \(O(n)\), y también \(D\) es \(O(n)\). Para este generador concreto, el crecimiento práctico es aproximadamente cuadrático en \(n\), con memoria lineal.
对于固定的 \(n\)，输入并不是从外部读入，而是按确定性的规则直接生成。每个 troll 对应一个三元组 \((a_i,b_i,w_i)\)：一个高度贡献、一个几何偏移量，以及选中它时得到的奖励。目标是在这些 troll 中选出一个子集并安排顺序，使得每个被选中的 troll 都满足题目中的站立几何条件，同时总奖励最大。
真正的关键不在于暴力枚举顺序，而在于把几何约束改写成普通的“完成时间不得超过截止时间”约束。一旦完成这个化简，问题就变成了带权单机调度，再用一维动态规划求最优值即可。
设第 \(i\) 个 troll 生成出的三元组为 \((a_i,b_i,w_i)\)，并记总高度为
$$A=\sum_{i=0}^{n-1} a_i.$$
整个化简围绕下面这个阈值展开：
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
三种实现都使用同一个模序列：
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
对 \(i=0,1,\dots,n-1\)，第 \(i\) 个 troll 的三元组定义为
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
因此所有生成值都落在 \([50,150]\) 中，而且 \(n\) 一旦固定，整组数据也就完全固定了。虽然题面背景是故事化的，但算法本身处理的是一个确定的离散优化实例。
程序并不直接计算浮点数 \(\sqrt{2}\)，而是把
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil$$
改写成“最小的满足
$$2x^2\ge A^2$$
的整数 \(x\)”来求。这个改写是完全等价的，因为 \(x\ge A/\sqrt{2}\) 与 \(2x^2\ge A^2\) 表达的是同一件事。这样实现的好处是只用整数比较，不会出现跨语言的浮点舍入差异。
设某个被选中的 troll 开始时，前面已经累计放置了高度 \(s\)。实现所对应的几何条件可以整理成
$$A+b_i-s\ge \Theta.$$
这意味着它的开始时刻必须满足
$$s\le A+b_i-\Theta.$$
而一旦选择该 troll，还要再占用 \(a_i\) 个单位的高度，所以它的完成时间为 \(C_i=s+a_i\)。于是同一个条件可以写成更标准的形式
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
到这里，每个 troll 都已经变成了一个调度作业：处理时间是 \(a_i\)，收益是 \(w_i\)，完成截止时间是 \(d_i\)。题目的几何外壳被完整地转成了调度约束。
对于单机调度问题，一个给定子集如果存在某种可行排列，那么按截止时间从小到大执行它也一定可行。因此没有必要枚举所有排列。
把作业按
$$d_1\le d_2\le \cdots \le d_m$$
排序之后，可行性的判断就变得很直接：每一个被选中的前缀都必须按时完成。若在这个顺序下完成时间分别为 \(C_1,C_2,\dots\)，那么要求就是
$$C_j\le d_j.$$
这一步把“选择哪些 troll、顺序怎样安排”的组合爆炸，压缩成了“在排好序的作业中，哪些总时长状态是可达且可行”的问题。
排序后，令 \(\mathrm{dp}[t]\) 表示：总占用时间恰好为 \(t\) 时，所有可行选择方案中的最大奖励。初始时只有 \(t=0\) 可达，其余状态都视为不可能。
处理一个持续时间为 \(a\)、奖励为 \(w\)、截止时间为 \(d\) 的作业时，转移为
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
这里必须让 \(t\) 从大到小更新，否则同一个作业可能在同一轮中被重复使用，从而破坏 0/1 选择的语义。全部作业处理完后，答案就是
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
前五个生成出的三元组分别是 \((51,55,75)\)、\((74,69,145)\)、\((121,102,108)\)、\((138,86,129)\)、\((142,89,127)\)。
因此
$$A=51+74+121+138+142=526.$$
阈值为
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
因为 \(2\cdot 371^2<526^2\le 2\cdot 372^2\)。
代入
$$d_i=A+b_i-\Theta+a_i$$
可得五个完成截止时间：
$$260,\ 297,\ 377,\ 378,\ 385.$$
动态规划求出的最优可行子集是第 2、4、5 个 troll。它们的总占用时间为
$$74+138+142=354,$$
总奖励为
$$145+129+127=401.$$
按截止时间顺序看，完成时刻分别是 \(74\)、\(212\)、\(354\)，确实满足 \(74\le 297\)、\(212\le 378\)、\(354\le 385\)。这正好对应实现里的内置校验值。
C++、Python 和 Java 实现遵循完全相同的流程。首先顺序生成 \(5\) 在模 \(10^9+7\) 下的幂，把每一项压缩到 \([50,150]\) 范围内，然后每三个数打包成一个 troll。
接着把所有高度求和，通过整数二分求出 \(\Theta\)，从而避免任何浮点平方根计算。然后把每个 troll 改写为一个调度作业，包含处理时间、奖励和完成截止时间。
作业按截止时间递增排序；若截止时间相同，则用更短的持续时间作为确定性的次级排序键。一维 DP 数组保存每个可达总时间对应的最大奖励，不可达状态用一个很小的负值哨兵表示。每处理一个作业，就从右向左更新一次 DP 数组，以保持 0/1 选择模型。
全部作业处理完后，扫描整张 DP 表，取其中最大的可达奖励作为答案。三种语言实现的算法结构完全一致，差别只在语法细节上。
记 \(D=\max_i d_i\)。生成数据和构造作业列表都只需 \(O(n)\) 时间。排序需要 \(O(n\log n)\)。主导部分是一维动态规划：每个作业都会在相关时间区间上做一次逆序扫描，因此总时间复杂度为 \(O(nD)\)。
空间复杂度为 \(O(D)\)，因为始终只保留一张 DP 表。又由于每个生成值都在 \(50\) 到 \(150\) 之间，所以总高度 \(A=O(n)\)，而 \(D\) 也同阶。对这个特定生成器而言，整体运行时间大致呈二次增长，而内存仍保持线性。
Для фиксированного \(n\) входные данные не читаются извне, а порождаются детерминированно. Каждый troll задается тройкой \((a_i,b_i,w_i)\): вклад в высоту, геометрический сдвиг и награда. Нужно выбрать подмножество и порядок так, чтобы каждый выбранный troll удовлетворял геометрическому условию стояния, а суммарная награда была максимальной.
Главная идея состоит в том, что геометрическое ограничение можно переписать как обычное ограничение на время завершения. После этого задача становится взвешенной задачей расписания на одной машине и решается одномерным динамическим программированием.
Пусть для troll \(i\) сгенерирована тройка \((a_i,b_i,w_i)\), и пусть
$$A=\sum_{i=0}^{n-1} a_i.$$
Ключевой порог равен
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
Все реализации используют модульную последовательность
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
Для \(i=0,1,\dots,n-1\) тройка \(i\)-го troll имеет вид
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
Следовательно, каждое число лежит в интервале \([50,150]\), а при фиксированном \(n\) весь экземпляр задачи определяется однозначно. В анализе нет никакой вероятностной составляющей.
Вместо прямого вычисления \(\sqrt{2}\) реализация ищет \(\Theta\) как минимальное целое \(x\), для которого верно
$$2x^2\ge A^2.$$
Это в точности эквивалентно условию \(x\ge A/\sqrt{2}\), поэтому найденное значение равно \(\lceil A/\sqrt{2}\rceil\). Использование только целочисленных сравнений устраняет проблемы округления и делает поведение одинаковым во всех трех языках.
Пусть выбранный troll начинает после того, как уже накоплена высота \(s\). Геометрия, заложенная в реализации, приводит к неравенству
$$A+b_i-s\ge \Theta.$$
То есть начать он должен не позже, чем при
$$s\le A+b_i-\Theta.$$
Поскольку выбор этого troll добавляет еще \(a_i\) единиц высоты, время завершения равно \(C_i=s+a_i\). Тогда то же условие переписывается в стандартном виде
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
Таким образом, каждый troll становится задачей с длительностью \(a_i\), наградой \(w_i\) и дедлайном \(d_i\).
Для одно-машинного расписания с длительностями и дедлайнами выбранное подмножество допустимо тогда и только тогда, когда оно допустимо в порядке неубывания дедлайнов. Поэтому полный перебор перестановок не нужен.
После сортировки
$$d_1\le d_2\le \cdots \le d_m$$
допустимость подмножества эквивалентна тому, что каждый выбранный префикс успевает завершиться вовремя. Если времена завершения в этом порядке равны \(C_1,C_2,\dots\), то условие таково:
$$C_j\le d_j.$$
После сортировки пусть \(\mathrm{dp}[t]\) означает максимальную суммарную награду среди всех допустимых выборов с общим занятым временем ровно \(t\). Изначально достижимо только состояние \(t=0\).
При обработке задачи с длительностью \(a\), наградой \(w\) и дедлайном \(d\) используется переход 0/1
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
Обновление по \(t\) идет в убывающем порядке, чтобы одну и ту же задачу нельзя было использовать несколько раз за одну итерацию. Ответом является
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
Первые пять сгенерированных троек: \((51,55,75)\), \((74,69,145)\), \((121,102,108)\), \((138,86,129)\), \((142,89,127)\).
Отсюда
$$A=51+74+121+138+142=526.$$
Порог равен
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
поскольку \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
Соответствующие дедлайны завершения равны
$$260,\ 297,\ 377,\ 378,\ 385.$$
Оптимальное допустимое подмножество состоит из 2-го, 4-го и 5-го troll. Их суммарное занятое время равно
$$74+138+142=354,$$
суммарная награда равна
$$145+129+127=401,$$
а времена завершения в порядке дедлайнов равны \(74\), \(212\) и \(354\), что удовлетворяет ограничениям \(297\), \(378\) и \(385\). Это совпадает со встроенной контрольной проверкой.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала последовательно порождаются степени числа \(5\) по модулю \(10^9+7\), затем каждое значение сжимается в диапазон \([50,150]\), и каждые три числа объединяются в одного troll.
После этого суммируются все высоты, а значение \(\Theta\) находится целочисленным бинарным поиском, без вещественного квадратного корня. Затем каждый troll превращается в задачу расписания с длительностью, наградой и дедлайном завершения.
Задачи сортируются по возрастанию дедлайна; меньшая длительность используется только как детерминированный критерий при равенстве. Одномерный массив DP хранит лучший выигрыш для каждого достижимого суммарного времени, а недостижимые состояния помечаются большим отрицательным значением. Для каждой задачи массив обновляется справа налево, сохраняя семантику 0/1.
Когда все задачи обработаны, код просматривает таблицу DP и берет максимальную достижимую награду. Алгоритмическая логика одинакова во всех трех языках; различается только синтаксис.
Пусть \(D=\max_i d_i\). Генерация данных и построение списка задач занимают \(O(n)\) времени. Сортировка требует \(O(n\log n)\). Доминирует динамическое программирование: для каждой задачи выполняется нисходящий проход по времени до нужного дедлайна, поэтому суммарное время равно \(O(nD)\).
Память равна \(O(D)\), так как хранится только один массив DP. Поскольку все сгенерированные значения лежат между \(50\) и \(150\), общая высота \(A\) имеет порядок \(O(n)\), и то же верно для \(D\). Для данного генератора практический рост получается примерно квадратичным по \(n\), при линейной памяти.
عندما يكون \(n\) ثابتا، فإن المعطيات لا تُقرأ من مصدر خارجي بل تُولد بصورة حتمية. كل troll يعطي ثلاثية \((a_i,b_i,w_i)\): مساهمة في الارتفاع، وإزاحة هندسية، ومكافأة. المطلوب اختيار مجموعة فرعية وترتيب مناسب بحيث يحقق كل troll مختار شرط الوقوف الهندسي، مع تعظيم مجموع المكافآت.
الفكرة الحاسمة هي أن القيد الهندسي يمكن تحويله إلى قيد اعتيادي من نوع "زمن الإنهاء يجب ألا يتجاوز الموعد النهائي". بعد هذا التحويل تصبح المسألة مسألة جدولة موزونة على آلة واحدة، ويجري حلها ببرمجة ديناميكية أحادية البعد.
لتكن الثلاثية المولدة للـ troll رقم \(i\) هي \((a_i,b_i,w_i)\)، ولنعرّف
$$A=\sum_{i=0}^{n-1} a_i.$$
العتبة الأساسية هي
$$\Theta=\left\lceil\frac{A}{\sqrt{2}}\right\rceil.$$
تستخدم التطبيقات المتتالية المعيارية
$$u_t\equiv 5^t \pmod{10^9+7},\qquad r_t=(u_t\bmod 101)+50.$$
ولكل \(i=0,1,\dots,n-1\) تكون ثلاثية الـ troll رقم \(i\) هي
$$\left(a_i,b_i,w_i\right)=\left(r_{3i},r_{3i+1},r_{3i+2}\right).$$
إذن كل قيمة مولدة تقع داخل المجال \([50,150]\)، وبمجرد تثبيت \(n\) تصبح المسألة كاملة محددة سلفا. لا يوجد أي عنصر احتمالي في التحليل.
بدلا من حساب \(\sqrt{2}\) عدديا، تحسب التطبيقات \(\Theta\) بوصفها أصغر عدد صحيح \(x\) يحقق
$$2x^2\ge A^2.$$
وهذا مكافئ تماما للشرط \(x\ge A/\sqrt{2}\)، ولذلك فإن أصغر قيمة ممكنة هي \(\lceil A/\sqrt{2}\rceil\). استخدام المقارنات الصحيحة فقط يزيل مشاكل التقريب ويجعل السلوك متطابقا في اللغات الثلاث.
إذا بدأ troll مختار بعد أن أصبح الارتفاع المتراكم قبله مساويا لـ \(s\)، فإن الهندسة التي تعتمدها التطبيقات تعطي المتباينة
$$A+b_i-s\ge \Theta.$$
أي أنه يجب أن يبدأ في موعد لا يتجاوز
$$s\le A+b_i-\Theta.$$
وبما أن اختياره يستهلك \(a_i\) وحدة إضافية من الارتفاع، فإن زمن إنهائه هو \(C_i=s+a_i\). لذلك يمكن إعادة كتابة الشرط نفسه على الصورة القياسية
$$C_i\le d_i,\qquad d_i=A+b_i-\Theta+a_i.$$
وهكذا يتحول كل troll إلى عمل جدولة له مدة \(a_i\)، ومكافأة \(w_i\)، وموعد نهائي للإنهاء \(d_i\).
في الجدولة على آلة واحدة مع مدد تنفيذ ومواعيد نهائية، تكون المجموعة المختارة ممكنة إذا وفقط إذا كانت ممكنة أيضا عند تنفيذها بترتيب تصاعدي للمواعيد النهائية. لذلك لا حاجة لتجريب جميع التباديل.
بعد ترتيب الأعمال بحيث
$$d_1\le d_2\le \cdots \le d_m,$$
فإن إمكانية مجموعة ما تعني ببساطة أن كل بادئة مختارة تنتهي في الوقت المناسب. وإذا كانت أزمنة الإنهاء بهذا الترتيب هي \(C_1,C_2,\dots\)، فالقيد هو
$$C_j\le d_j.$$
بعد الترتيب، لتكن \(\mathrm{dp}[t]\) هي أكبر مكافأة كلية بين جميع الاختيارات الممكنة التي يكون زمنها المشغول الكلي مساويا تماما لـ \(t\). في البداية تكون الحالة الوحيدة الممكنة هي \(t=0\).
عند معالجة عمل مدته \(a\) ومكافأته \(w\) وموعده النهائي \(d\)، يكون انتقال 0/1 هو
$$\mathrm{dp}[t]=\max\bigl(\mathrm{dp}[t],\mathrm{dp}[t-a]+w\bigr)\qquad(a\le t\le d).$$
ويجب تحديث \(t\) تنازليا حتى لا يُستخدم العمل نفسه أكثر من مرة داخل الدورة الواحدة. والجواب النهائي هو
$$\max_{0\le t\le D}\mathrm{dp}[t],\qquad D=\max_i d_i.$$
أول خمس ثلاثيات مولدة هي \((51,55,75)\)، \((74,69,145)\)، \((121,102,108)\)، \((138,86,129)\)، و\((142,89,127)\).
ومن ثم
$$A=51+74+121+138+142=526.$$
وتكون العتبة
$$\Theta=\left\lceil\frac{526}{\sqrt{2}}\right\rceil=372,$$
لأن \(2\cdot 371^2<526^2\le 2\cdot 372^2\).
فتصبح المواعيد النهائية للإنهاء
$$260,\ 297,\ 377,\ 378,\ 385.$$
أفضل مجموعة ممكنة هي troll رقم 2 و4 و5. زمنها المشغول الكلي هو
$$74+138+142=354,$$
ومجموع مكافآتها هو
$$145+129+127=401.$$
وأزمنة الإنهاء بترتيب المواعيد النهائية هي \(74\)، \(212\)، و\(354\)، وهي تحقق الحدود \(297\)، \(378\)، و\(385\). وهذا يطابق قيمة التحقق المضمنة في التنفيذ.
التنفيذات في C++ وPython وJava تتبع المسار نفسه. أولا تُولد قوى العدد \(5\) بترديد \(10^9+7\) بصورة متتابعة، ثم يُختزل كل حد إلى المجال \([50,150]\)، وتُجمع كل ثلاثة أعداد في troll واحد.
بعد ذلك تُجمع جميع الارتفاعات ويُستخرج \(\Theta\) ببحث ثنائي صحيح، من دون الحاجة إلى جذر تربيعي عشري. ثم يتحول كل troll إلى عمل جدولة له مدة ومكافأة وموعد نهائي للإنهاء.
تُرتب الأعمال حسب الموعد النهائي تصاعديا، وتُستخدم المدة الأقصر فقط ككاسر تعادل حتمي. مصفوفة DP أحادية البعد تحفظ أفضل مكافأة لكل زمن كلي قابل للوصول، مع قيمة سالبة كبيرة للحالات المستحيلة. ويجري تحديث هذه المصفوفة من اليمين إلى اليسار لكل عمل، حفاظا على طبيعة الاختيار 0/1.
بعد معالجة جميع الأعمال، يمسح التنفيذ جدول DP ويأخذ أكبر مكافأة قابلة للوصول. البنية الخوارزمية متطابقة في اللغات الثلاث، والاختلاف فقط في الصياغة البرمجية.
ليكن \(D=\max_i d_i\). توليد البيانات وبناء قائمة الأعمال يكلفان \(O(n)\) زمنا. أما الفرز فيكلف \(O(n\log n)\). الجزء المسيطر هو البرمجة الديناميكية، إذ يُجرى لكل عمل مسح زمني تنازلي حتى الموعد النهائي المناسب، وبالتالي يكون الزمن الكلي \(O(nD)\).
استهلاك الذاكرة هو \(O(D)\)، لأن التنفيذ يحتفظ بمصفوفة DP واحدة فقط. وبما أن كل قيمة مولدة تقع بين \(50\) و\(150\)، فإن \(A=O(n)\) وكذلك \(D=O(n)\). لذلك يكون النمو العملي لهذا المولد قريبا من التربيعي في \(n\)، مع ذاكرة خطية.