We seek the minimum possible value of \(x_1+\cdots+x_{17}\) for points added one at a time inside the unit interval. After the \(m\)-th insertion, the current set of \(m\) points must occupy the \(m\) half-open subintervals
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$$
exactly once. So the first stage uses one bin, the second stage must place two points into the two halves, the third stage must place three points into the thirds, and so on up to \(m=17\). The implementations compute the optimal sum exactly, prove that \(17\) stages are feasible, and also verify that the same condition fails at \(18\).
The key simplification is to represent uncertainty by rational intervals instead of individual real numbers. Every future decision only cuts intervals by equal-partition boundaries, so the whole search can be done with integer arithmetic.
Let
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Because every \(m\le 17\) divides \(d\), every boundary \(k/m\) can be written exactly as an integer multiple of \(1/d\). Instead of storing a point \(x\), we store an interval
$$I=[l,u)\subseteq[0,d),$$
which means that the real point may lie anywhere in
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
Initially nothing is known, so the first state is just one interval:
$$[0,d).$$
Assume a state with \(n\) current intervals already encodes all constraints from stages \(1\) through \(n\). For the next stage set
$$m=n+1.$$
The unit interval is now partitioned into \(m\) equal bins, which on the common denominator grid become
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
Each existing interval \(I_i\) must be assigned to one distinct bin with nonempty intersection. If bin \(B_{\pi(i)}\) is chosen, the interval is refined to
$$I_i'=I_i\cap B_{\pi(i)}.$$
Exactly one bin is left unused, and that unused bin becomes the interval of the newly inserted point. If no injective assignment exists, that branch of the search is impossible.
For a fixed stage \(m\), form a bipartite graph whose left side is the current intervals and whose right side is the \(m\) bins. Connect \(I_i\) to \(B_k\) whenever
$$I_i\cap B_k\ne\varnothing.$$
A valid transition is exactly an injective matching of the \(n\) current intervals into the \(m\) bins, leaving one unmatched bin for the new point. This is the Hall-type combinatorial core of the problem. The implementations do not invoke a separate matching library; instead they search directly through these assignments and prune as soon as a state becomes impossible.
Once only the set of surviving intervals matters, the names of the points no longer matter. After every transition, the intervals are sorted by their endpoints. Two different histories that produce the same sorted interval list therefore represent exactly the same future problem.
This turns the search into dynamic programming on canonical states. A state is fully described by its sorted half-open intervals, and every repeated state can reuse the previously computed result instead of exploring the whole subtree again.
When the search reaches \(17\) intervals, each interval \(I_i=[l_i,u_i)\) contains all admissible final positions of one point. Since the target quantity is the sum of coordinates and every interval includes its left endpoint, the minimum achievable sum inside that terminal state is
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
Choosing any point farther to the right can only increase the total. So the global optimization problem reduces to minimizing the integer numerator
$$F=\sum_{i=1}^{17} l_i,$$
and converting to the real answer only once, at the end, by dividing by \(d\).
The implementations include a small exact checkpoint at target \(4\). Then
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
One optimal chain of states is
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
At the fourth stage the quarter bins are \([0,3)\), \([3,6)\), \([6,9)\), and \([9,12)\). An optimal refinement is
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
The unused bin is \([3,6)\). Therefore the four final left endpoints are \(0,3,6,9\), so
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
This is exactly the verification embedded in the implementations.
The C++, Python, and Java implementations all follow the same plan. They first build the common denominator \(d\), then represent every state as a sorted list of half-open intervals with integer endpoints. From a state with \(n\) intervals, the implementation creates the \(n+1\) equal bins for the next stage and computes every nonempty interval-bin intersection.
If some interval has no compatible bin, the state is rejected immediately. Otherwise the search tries injective assignments, always considering first the interval with the fewest available bins, because that ordering cuts the branching factor sharply. One memoized search answers the yes-or-no question “can this state still be completed?”, and another memoized search returns the minimum possible numerator \(F\) reachable from that state.
The final decimal output is produced by exact integer rounding of \(F/d\) to twelve digits after the decimal point. The implementations also perform three internal consistency checks: the \(4\)-point value is \(3/2\), the \(6\)-point dynamic program agrees with a brute-force search, and feasibility is true for \(17\) but false for \(18\).
For a state containing \(n\) intervals, constructing the next-stage bins and all interval-bin intersections costs \(O(n^2)\), because there are \(n\) intervals and \(n+1\) bins. The difficult part is the search over injective assignments, whose worst-case size is combinatorial, so the theoretical upper bound is exponential in the target size.
In practice, three features make the problem tractable for \(17\): interval intersections shrink the options quickly, branching starts with the most constrained interval, and canonical-state memoization merges many different histories into the same subproblem. Therefore the real running time is governed by the number of distinct canonical interval states that are visited, while memory is proportional to the number of cached states times the interval data stored for each one.
Gesucht ist der kleinstmögliche Wert von \(x_1+\cdots+x_{17}\), wobei die Punkte nacheinander im Einheitsintervall eingefügt werden. Nach dem \(m\)-ten Einfügen müssen die aktuell vorhandenen \(m\) Punkte die \(m\) halboffenen Teilintervalle
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$$
genau einmal besetzen. Stufe \(2\) verlangt also je einen Punkt in jeder Hälfte, Stufe \(3\) je einen Punkt in jedem Drittel und so weiter bis \(m=17\). Die Implementierungen berechnen die optimale Summe exakt, zeigen die Erfüllbarkeit für \(17\) und bestätigen zugleich, dass die gleiche Bedingung bei \(18\) scheitert.
Die zentrale Vereinfachung besteht darin, keine einzelnen reellen Zahlen zu verfolgen, sondern nur Intervalle möglicher Positionen. Da alle späteren Schnitte an gleichmäßigen Teilungsgrenzen stattfinden, reicht reine Ganzzahlarithmetik aus.
Setze
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Dann teilt jedes \(m\le 17\) die Zahl \(d\), also ist jede Grenze \(k/m\) exakt ein ganzzahliges Vielfaches von \(1/d\). Statt einen Punkt \(x\) direkt zu speichern, speichern wir ein Intervall
$$I=[l,u)\subseteq[0,d),$$
das den reellen Bereich
$$\left[\frac{l}{d},\frac{u}{d}\right)$$
repräsentiert. Am Anfang ist noch nichts festgelegt, daher besteht der Startzustand nur aus
$$[0,d).$$
Angenommen, ein Zustand mit \(n\) Intervallen kodiert bereits alle Bedingungen der Stufen \(1\) bis \(n\). Für die nächste Stufe setzen wir
$$m=n+1.$$
Das Einheitsintervall wird nun in \(m\) gleich große Boxen zerlegt; auf dem gemeinsamen Nennergitter sind das
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
Jedes bestehende Intervall \(I_i\) muss einer eigenen Box mit nichtleerem Schnitt zugeordnet werden. Wird die Box \(B_{\pi(i)}\) gewählt, so verengt sich das Intervall zu
$$I_i'=I_i\cap B_{\pi(i)}.$$
Genau eine Box bleibt unbenutzt; sie wird zum Intervall des neu eingefügten Punkts. Existiert keine injektive Zuordnung, ist dieser Suchzweig unmöglich.
Für eine feste Stufe \(m\) kann man einen bipartiten Graphen bilden: links die aktuellen Intervalle, rechts die \(m\) Boxen. Eine Kante zwischen \(I_i\) und \(B_k\) existiert genau dann, wenn
$$I_i\cap B_k\ne\varnothing.$$
Ein gültiger Übergang ist also ein injektives Matching der \(n\) Intervalle in die \(m\) Boxen, wobei eine Box frei bleibt und den neuen Punkt aufnimmt. Das ist der Hall-artige kombinatorische Kern der Aufgabe. Die Implementierungen verwenden dafür keine separate Matching-Bibliothek, sondern durchsuchen diese Zuordnungen direkt und verwerfen Zustände sofort, sobald sie unmöglich werden.
Sobald nur noch die Menge der verbleibenden Intervalle zählt, spielen die Namen der Punkte keine Rolle mehr. Deshalb werden nach jedem Übergang alle Intervalle nach ihren Endpunkten sortiert. Zwei verschiedene Entstehungsgeschichten, die dieselbe sortierte Intervallliste erzeugen, führen exakt auf dasselbe Restproblem.
Damit wird die Suche zu dynamischer Programmierung auf kanonischen Zuständen. Ein Zustand ist vollständig durch seine sortierten halboffenen Intervalle beschrieben, und ein bereits berechneter Zustand muss nicht noch einmal vollständig durchsucht werden.
Sobald \(17\) Intervalle erreicht sind, enthält jedes Intervall \(I_i=[l_i,u_i)\) alle noch zulässigen Endpositionen eines Punkts. Da minimiert werden soll und jedes Intervall seinen linken Endpunkt enthält, ist die kleinste in diesem Endzustand erreichbare Summe
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
Jede Wahl weiter rechts kann die Summe nur vergrößern. Global genügt es also, den ganzzahligen Zähler
$$F=\sum_{i=1}^{17} l_i$$
zu minimieren und erst am Ende durch \(d\) zu teilen.
Die Implementierungen enthalten einen exakten Kontrollwert für Zielgröße \(4\). Dann ist
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
Eine optimale Zustandsfolge ist
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
In Stufe \(4\) sind die Viertelboxen \([0,3)\), \([3,6)\), \([6,9)\) und \([9,12)\). Eine optimale Verfeinerung lautet
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
Die unbenutzte Box ist \([3,6)\). Damit lauten die vier linken Endpunkte \(0,3,6,9\), also
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
Genau dieser Wert wird auch im Programm überprüft.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst wird der gemeinsame Nenner \(d\) berechnet, danach wird jeder Zustand als sortierte Liste halboffener Intervalle mit ganzzahligen Endpunkten dargestellt. Aus einem Zustand mit \(n\) Intervallen erzeugt die Implementierung die \(n+1\) gleich großen Boxen der nächsten Stufe und berechnet alle nichtleeren Intervall-Box-Schnitte.
Hat ein Intervall keine kompatible Box, wird der Zustand sofort verworfen. Andernfalls probiert die Suche injektive Zuordnungen aus, wobei stets zuerst das Intervall mit den wenigsten Optionen bearbeitet wird; genau das reduziert die Verzweigung deutlich. Eine memoisiere Suche beantwortet die reine Erfüllbarkeitsfrage, eine zweite memoisiere Suche liefert den kleinsten von dort aus noch erreichbaren Zähler \(F\).
Die endgültige Dezimaldarstellung entsteht durch exaktes ganzzahliges Runden von \(F/d\) auf zwölf Nachkommastellen. Zusätzlich führen die Implementierungen drei interne Konsistenztests aus: der \(4\)-Punkt-Wert ist \(3/2\), das dynamische Programm für \(6\) Punkte stimmt mit einer Brute-Force-Suche überein, und Erfüllbarkeit ist bei \(17\) wahr, bei \(18\) aber falsch.
Für einen Zustand mit \(n\) Intervallen kostet das Erzeugen der nächsten Boxen und aller Intervall-Box-Schnitte \(O(n^2)\), denn es gibt \(n\) Intervalle und \(n+1\) Boxen. Der schwierige Teil ist die Suche über injektive Zuordnungen; deren Worst-Case-Größe ist kombinatorisch, daher ist die theoretische Obergrenze exponentiell in der Zielgröße.
Praktisch wird das Problem für \(17\) durch drei Effekte handhabbar: die Intervallschnitte verengen die Optionen schnell, die Verzweigung beginnt beim jeweils am stärksten eingeschränkten Intervall, und die Memoisierung kanonischer Zustände verschmilzt viele verschiedene Suchpfade zu demselben Teilproblem. Die reale Laufzeit wird daher hauptsächlich durch die Anzahl verschiedener besuchter kanonischer Zustände bestimmt; der Speicherverbrauch ist proportional zur Zahl der gecachten Zustände mal den pro Zustand gespeicherten Intervallinformationen.
Amaç, birim aralık içine sırayla yerleştirilen \(17\) nokta için \(x_1+\cdots+x_{17}\) toplamını mümkün olan en küçük değere indirmektir. \(m\)-inci eklemeden sonra eldeki \(m\) nokta,
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1,$$
şeklindeki \(m\) yarı açık alt aralığı tam olarak birer kez doldurmak zorundadır. Yani \(2\). aşamada iki yarımın her birinde bir nokta, \(3\). aşamada üçte birlik aralıkların her birinde bir nokta ve bu şekilde \(17\). aşamaya kadar devam eder. Uygulamalar optimal toplamı tam olarak hesaplar, \(17\) için uygunluk olduğunu gösterir ve aynı koşulun \(18\) için bozulduğunu da doğrular.
Temel fikir, tek tek reel sayıları takip etmek yerine olası konum aralıklarını takip etmektir. Gelecekteki bütün kararlar eşit bölme sınırlarında kesişim almakla oluştuğu için tüm arama tam sayı aritmetiği ile yapılabilir.
Şunu tanımlayalım:
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Her \(m\le 17\) sayısı \(d\)'yi böldüğü için, her \(k/m\) sınırı tam olarak \(1/d\)'nin bir tam sayı katıdır. Bu yüzden bir nokta \(x\) yerine
$$I=[l,u)\subseteq[0,d)$$
aralığını tutarız; bunun reel karşılığı
$$\left[\frac{l}{d},\frac{u}{d}\right)$$
olur. Başlangıçta hiçbir kısıt olmadığı için ilk durum yalnızca
$$[0,d)$$
aralığından oluşur.
Elimizdeki \(n\) aralıklı durumun, \(1\) ile \(n\) arasındaki tüm aşama koşullarını zaten temsil ettiğini varsayalım. Sonraki aşama için
$$m=n+1$$
alınır. Birim aralık \(m\) eşit kutuya ayrılır; ortak payda ızgarasında bunlar
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1$$
şeklindedir. Her mevcut aralık \(I_i\), boş olmayan kesişime sahip farklı bir kutuya atanmalıdır. \(B_{\pi(i)}\) kutusu seçilirse yeni aralık
$$I_i'=I_i\cap B_{\pi(i)}$$
olur. Tam bir kutu kullanılmadan kalır; o kutu da yeni eklenen noktanın aralığı olur. Böyle bir enjektif atama yoksa o arama dalı imkansızdır.
Sabit bir \(m\) aşamasında sol tarafa mevcut aralıkları, sağ tarafa da \(m\) kutuyu koyan iki parçalı bir grafik kurabiliriz. Ancak ve ancak
$$I_i\cap B_k\ne\varnothing$$
ise \(I_i\) ile \(B_k\) arasında kenar vardır. Geçerli bir geçiş, \(n\) aralığın \(m\) kutuya enjektif biçimde eşlenmesi ve bir kutunun yeni nokta için boş bırakılması demektir. Problemin Hall tipi kombinatoryal çekirdeği tam olarak budur. Uygulamalar ayrı bir eşleştirme kütüphanesi kullanmaz; bunun yerine bu atamaları doğrudan dener ve bir durum imkansız hale gelir gelmez dalı keser.
Geriye sadece yaşayan aralık kümesi kaldığında, noktaların isimleri artık önemli değildir. Bu yüzden her geçişten sonra aralıklar uç noktalarına göre sıralanır. Aynı sıralı aralık listesini üreten iki farklı geçmiş, gelecekte tamamen aynı alt probleme karşılık gelir.
Böylece arama, kanonik durumlar üzerinde dinamik programlamaya dönüşür. Bir durum, sıralı yarı açık aralık listesiyle tamamen belirlenir; daha önce çözülmüş bir durumun tüm alt ağacını yeniden aramaya gerek kalmaz.
Arama \(17\) aralığa ulaştığında her \(I_i=[l_i,u_i)\) aralığı, bir noktanın tüm geçerli son konumlarını içerir. Minimizasyon yapıldığından ve her aralık sol ucunu içerdiğinden, o terminal durumda elde edilebilecek en küçük toplam
$$\frac{1}{d}\sum_{i=1}^{17} l_i$$
olur. Daha sağdan seçilen her nokta toplamı ancak büyütür. Bu nedenle küresel problem, tam sayı payı
$$F=\sum_{i=1}^{17} l_i$$
değerini en küçük yapmak ve bölme işlemini sadece en sonda uygulamaktır.
Uygulamalarda hedef \(4\) için küçük bir tam kontrol bulunur. Bu durumda
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
Optimal bir durum zinciri
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12)$$
şeklindedir. \(4\). aşamada çeyrek kutular \([0,3)\), \([3,6)\), \([6,9)\) ve \([9,12)\) olur. Optimal bir daraltma
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12)$$
şeklindedir. Kullanılmayan kutu \([3,6)\) olduğundan son sol uçlar \(0,3,6,9\) olur ve
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
Bu da uygulamalardaki doğrulama ile birebir aynıdır.
C++, Python ve Java uygulamaları aynı planı izler. Önce ortak payda \(d\) hesaplanır; ardından her durum, uçları tam sayı olan sıralı yarı açık aralıklar listesi olarak tutulur. \(n\) aralıklı bir durumdan sonraki aşamaya geçmek için uygulama \(n+1\) eşit kutuyu üretir ve bütün boş olmayan aralık-kutu kesişimlerini hesaplar.
Eğer bir aralığın uyumlu olduğu hiçbir kutu yoksa durum anında elenir. Aksi halde arama, seçenek sayısı en az olan aralıktan başlayarak enjektif atamaları dener; bu sıralama dallanmayı ciddi biçimde azaltır. Bir memoize edilmiş arama, bir durumun tamamlanıp tamamlanamayacağını söyler; ikinci memoize edilmiş arama ise o durumdan ulaşılabilecek en küçük \(F\) payını döndürür.
Son ondalık çıktı, \(F/d\) oranının on iki basamağa tam sayı aritmetiğiyle yuvarlanmasıyla elde edilir. Ayrıca uygulamalar üç iç tutarlılık kontrolü yapar: \(4\) noktalı değer \(3/2\)'dir, \(6\) noktalı dinamik program brute-force ile aynıdır ve uygunluk \(17\) için doğru, \(18\) için yanlıştır.
\(n\) aralıklı bir durumda sonraki aşamanın kutularını ve tüm aralık-kutu kesişimlerini kurmak \(O(n^2)\) zaman alır; çünkü \(n\) aralık ve \(n+1\) kutu vardır. Asıl zor kısım enjektif atamalar üzerinde yapılan aramadır; bunun en kötü durum büyüklüğü kombinatoryaldir, dolayısıyla teorik üst sınır hedef büyüklüğe göre üstel davranır.
Pratikte \(17\) için problem üç nedenle çözülebilir hale gelir: aralık kesişimleri seçenekleri hızla daraltır, dallanma en kısıtlı aralıktan başlatılır ve kanonik durum memoization'ı birçok farklı geçmişi tek bir alt problemde birleştirir. Bu yüzden gerçek çalışma süresi esas olarak ziyaret edilen farklı kanonik durum sayısına bağlıdır; bellek kullanımı da önbelleğe alınan durum sayısı ile her durumda saklanan aralık verilerinin çarpımı kadardır.
Se quiere minimizar \(x_1+\cdots+x_{17}\) para una sucesión de \(17\) puntos insertados uno por uno dentro del intervalo unidad. Después de la inserción número \(m\), el conjunto actual de \(m\) puntos debe ocupar exactamente una vez los \(m\) subintervalos semiabiertos
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1.$$
Eso significa que en la etapa \(2\) debe haber un punto en cada mitad, en la etapa \(3\) un punto en cada tercio, y así sucesivamente hasta \(m=17\). Las implementaciones calculan la suma óptima de forma exacta, comprueban que \(17\) etapas sí son posibles y verifican además que la condición deja de ser realizable en \(18\).
La simplificación decisiva consiste en trabajar con intervalos racionales de posiciones posibles, no con números reales individuales. Como todas las decisiones futuras solo recortan por fronteras de particiones iguales, toda la búsqueda puede hacerse con aritmética entera.
Definimos
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Como todo \(m\le 17\) divide a \(d\), cada frontera \(k/m\) se representa exactamente como un múltiplo entero de \(1/d\). En vez de guardar un punto \(x\), guardamos un intervalo
$$I=[l,u)\subseteq[0,d),$$
que significa que el punto real puede estar en
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
Al principio no sabemos nada, así que el estado inicial es simplemente
$$[0,d).$$
Supongamos que un estado con \(n\) intervalos ya codifica todas las restricciones de las etapas \(1\) a \(n\). Para la siguiente etapa ponemos
$$m=n+1.$$
El intervalo unidad se parte ahora en \(m\) cajas iguales; sobre la malla común son
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
Cada intervalo existente \(I_i\) debe asignarse a una caja distinta con intersección no vacía. Si se elige la caja \(B_{\pi(i)}\), el intervalo se refina a
$$I_i'=I_i\cap B_{\pi(i)}.$$
Queda exactamente una caja libre, y esa caja pasa a ser el intervalo del punto nuevo. Si no existe una asignación inyectiva, esa rama de la búsqueda es imposible.
Para una etapa fija \(m\), construimos un grafo bipartito: a la izquierda los intervalos actuales y a la derecha las \(m\) cajas. Unimos \(I_i\) con \(B_k\) exactamente cuando
$$I_i\cap B_k\ne\varnothing.$$
Una transición válida es entonces un emparejamiento inyectivo de los \(n\) intervalos actuales dentro de las \(m\) cajas, dejando una caja sin usar para el nuevo punto. Ese es el núcleo combinatorio tipo Hall del problema. Las implementaciones no llaman a una biblioteca externa de matching; exploran directamente estas asignaciones y podan en cuanto un estado se vuelve imposible.
Una vez que solo importa el conjunto de intervalos supervivientes, los nombres de los puntos dejan de importar. Por eso, después de cada transición, los intervalos se ordenan por sus extremos. Dos historias distintas que producen la misma lista ordenada de intervalos representan exactamente el mismo subproblema futuro.
Así, la búsqueda se convierte en programación dinámica sobre estados canónicos. Un estado queda descrito por su lista ordenada de intervalos semiabiertos, y cualquier estado repetido puede reutilizar el resultado ya calculado.
Cuando la búsqueda llega a \(17\) intervalos, cada intervalo \(I_i=[l_i,u_i)\) contiene todas las posiciones finales admisibles de un punto. Como se quiere minimizar y cada intervalo incluye su extremo izquierdo, la menor suma posible dentro de ese estado terminal es
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
Cualquier elección más a la derecha solo puede aumentar la suma. Por tanto, el problema global se reduce a minimizar el numerador entero
$$F=\sum_{i=1}^{17} l_i$$
y dividir entre \(d\) una sola vez al final.
Las implementaciones incluyen una verificación exacta pequeña para objetivo \(4\). En ese caso
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
Una cadena óptima de estados es
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
En la cuarta etapa, las cajas de cuartos son \([0,3)\), \([3,6)\), \([6,9)\) y \([9,12)\). Un refinamiento óptimo es
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
La caja no usada es \([3,6)\). Por lo tanto, los cuatro extremos izquierdos finales son \(0,3,6,9\), y
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
Ese es exactamente el valor de control que aparece en las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan el denominador común \(d\), y luego representan cada estado como una lista ordenada de intervalos semiabiertos con extremos enteros. Desde un estado con \(n\) intervalos, la implementación construye las \(n+1\) cajas iguales de la etapa siguiente y calcula todas las intersecciones no vacías entre intervalos y cajas.
Si algún intervalo no tiene ninguna caja compatible, el estado se descarta de inmediato. En caso contrario, la búsqueda prueba asignaciones inyectivas, empezando siempre por el intervalo con menos cajas disponibles, porque ese orden reduce mucho la ramificación. Una búsqueda con memoización responde a la pregunta de factibilidad, y otra búsqueda con memoización devuelve el menor numerador \(F\) alcanzable desde ese estado.
La salida decimal final se obtiene redondeando exactamente \(F/d\) a doce cifras decimales mediante aritmética entera. Además, las implementaciones realizan tres comprobaciones internas: el valor con \(4\) puntos es \(3/2\), el programa dinámico con \(6\) puntos coincide con una búsqueda exhaustiva, y la factibilidad es verdadera para \(17\) y falsa para \(18\).
Para un estado con \(n\) intervalos, construir las cajas de la siguiente etapa y todas las intersecciones intervalo-caja cuesta \(O(n^2)\), porque hay \(n\) intervalos y \(n+1\) cajas. La parte difícil es la exploración de asignaciones inyectivas; su tamaño en el peor caso es combinatorio, así que el límite teórico superior es exponencial en el tamaño objetivo.
En la práctica, el problema resulta abordable para \(17\) gracias a tres factores: las intersecciones reducen rápidamente las opciones, la ramificación empieza por el intervalo más restringido y la memoización de estados canónicos fusiona muchas historias distintas en un mismo subproblema. Por eso el tiempo real depende sobre todo del número de estados canónicos diferentes visitados, y la memoria es proporcional al número de estados almacenados por los datos de intervalos guardados en cada uno.
目标是在单位区间内按顺序加入 \(17\) 个点，并使 \(x_1+\cdots+x_{17}\) 尽可能小。加入第 \(m\) 个点以后，当前这 \(m\) 个点必须恰好各自落在下面这 \(m\) 个半开区间之一：
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1.$$
也就是说，第 \(2\) 步时两个点要分别占据两个二等分区间；第 \(3\) 步时三个点要分别占据三个三等分区间；一直持续到 \(m=17\)。程序不仅精确求出了最优和，还验证了这个构造在 \(17\) 时可行，而在 \(18\) 时不可行。
核心简化思想是：不直接追踪单个实数点，而是追踪“这个点还可能落在哪个有理区间里”。由于后续所有约束都只是按等分边界不断裁剪区间，所以整个搜索可以完全用整数完成。
设
$$d=\operatorname{lcm}(1,2,\dots,17).$$
因为每个 \(m\le 17\) 都整除 \(d\)，所以每个边界 \(k/m\) 都能精确写成 \(1/d\) 的整数倍。于是我们不用直接存储点 \(x\)，而是存储一个整数端点的半开区间
$$I=[l,u)\subseteq[0,d),$$
它表示真实点的位置满足
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
初始时还没有任何信息，因此最开始只有一个区间：
$$[0,d).$$
假设当前状态中有 \(n\) 个区间，它们已经完整编码了第 \(1\) 步到第 \(n\) 步的所有限制。下一步令
$$m=n+1.$$
此时单位区间被切成 \(m\) 个等长箱子；在共同分母 \(d\) 的网格上，这些箱子就是
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
每个旧区间 \(I_i\) 都必须分配到一个不同的箱子，而且交集不能为空。如果给它分配的是 \(B_{\pi(i)}\)，那么新区间就变成
$$I_i'=I_i\cap B_{\pi(i)}.$$
恰好会剩下一个没有被使用的箱子，这个箱子就是新加入点的区间。如果不存在这样的单射分配，这个搜索分支就直接失败。
对固定的阶段 \(m\)，可以构造一个二分图：左边是当前的区间，右边是这 \(m\) 个箱子。当且仅当
$$I_i\cap B_k\ne\varnothing$$
时，在 \(I_i\) 与 \(B_k\) 之间连一条边。于是，一个合法转移就等价于把这 \(n\) 个旧区间单射地匹配到 \(m\) 个箱子里，并留下一个空箱子给新点。这正是题目的 Hall 型组合结构。实现并没有调用通用匹配库，而是直接在这些候选分配上做深度搜索，一旦某个状态不可能延伸，就立刻剪枝。
当未来只和“还存活的区间集合”有关时，点本身的名字就不再重要。于是每次转移后，都把所有区间按端点排序。两条不同的历史，只要得到相同的有序区间列表，它们未来面对的就是完全相同的子问题。
这样一来，搜索就变成了对规范化状态做动态规划。一个状态由排序后的半开区间列表唯一确定；只要某个状态已经求过，就可以直接复用结果，不必再把整棵子树重新搜索一遍。
当搜索到 \(17\) 个区间时，每个区间 \(I_i=[l_i,u_i)\) 都表示对应那个点所有仍然允许的最终位置。由于目标是最小化总和，而且每个区间都包含自己的左端点，所以该终止状态下能取得的最小总和就是
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
把点选得更靠右只会让总和更大。因此全局优化问题可以完全改写成：最小化整数分子
$$F=\sum_{i=1}^{17} l_i,$$
最后再统一除以 \(d\)。
程序里包含了一个较小的精确校验目标，即 \(4\) 个点的情形。这时
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
一种最优状态链可以写成
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
到了第 \(4\) 步，四等分箱子是 \([0,3)\)、\([3,6)\)、\([6,9)\)、\([9,12)\)。一种最优细化方式为
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
没有被使用的箱子是 \([3,6)\)。于是四个最终左端点就是 \(0,3,6,9\)，从而
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
这与实现中的校验结果完全一致。
C++、Python 和 Java 实现采用的是同一套思路。首先求出共同分母 \(d\)，然后把每个状态表示成一个按端点排序的半开区间列表，区间端点全部是整数。对于一个含有 \(n\) 个区间的状态，实现会构造下一阶段的 \(n+1\) 个等长箱子，并枚举所有非空的“区间与箱子”的交集。
如果某个区间没有任何兼容箱子，这个状态会立刻被判死。否则，搜索会尝试单射分配，并优先处理可选箱子数最少的区间，因为这种顺序能明显降低分支数。代码中有两个记忆化搜索：一个只回答“这个状态还能不能完成”；另一个返回从该状态出发能达到的最小整数分子 \(F\)。
最终的小数输出不是用浮点数直接计算，而是先保留精确分数 \(F/d\)，再用整数舍入到小数点后 \(12\) 位。实现还做了三个内部自检：\(4\) 点结果是 \(3/2\)，\(6\) 点动态规划和暴力搜索一致，且 \(17\) 可行而 \(18\) 不可行。
对于一个包含 \(n\) 个区间的状态，构造下一阶段的箱子并计算所有区间-箱子交集需要 \(O(n^2)\) 时间，因为有 \(n\) 个区间和 \(n+1\) 个箱子。真正昂贵的部分是对单射分配的搜索；它在最坏情况下具有组合爆炸，因此理论上界是关于目标规模的指数级。
但在实际 \(17\) 点问题上，三种机制显著压缩了搜索空间：区间相交会快速收紧可选范围，搜索总是先扩展最受限制的区间，而规范化状态的记忆化又会把许多不同历史合并成同一个子问题。所以真实运行时间主要取决于访问到了多少个不同的规范状态；内存消耗则与缓存状态数乘以每个状态保存的区间数据规模成正比。
Нужно минимизировать сумму \(x_1+\cdots+x_{17}\) для \(17\) точек, которые добавляются по одной внутри единичного интервала. После добавления \(m\)-й точки текущий набор из \(m\) точек обязан занимать ровно по одной точке в каждом из \(m\) полуоткрытых интервалов
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1.$$
Иными словами, на шаге \(2\) точки должны разойтись по двум половинам, на шаге \(3\) по трём третям и так далее до \(m=17\). Реализации точно вычисляют оптимальную сумму, подтверждают выполнимость для \(17\) и одновременно показывают, что при \(18\) такое условие уже невыполнимо.
Главное упрощение состоит в том, чтобы отслеживать не отдельные вещественные координаты, а интервалы возможного положения точек. Поскольку все будущие ограничения получаются только пересечением с границами равных разбиений, весь поиск можно вести в целых числах.
Положим
$$d=\operatorname{lcm}(1,2,\dots,17).$$
Так как каждое \(m\le 17\) делит \(d\), любая граница \(k/m\) представима точно как целое кратное \(1/d\). Поэтому вместо самой точки \(x\) храним полуоткрытый интервал
$$I=[l,u)\subseteq[0,d),$$
что означает
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
В начале никакой информации нет, поэтому стартовое состояние состоит из одного интервала
$$[0,d).$$
Предположим, что состояние из \(n\) интервалов уже кодирует все ограничения шагов от \(1\) до \(n\). Для следующего шага берём
$$m=n+1.$$
Единичный интервал разбивается на \(m\) равных ячеек; на общей сетке они имеют вид
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
Каждому существующему интервалу \(I_i\) нужно назначить свою собственную ячейку с непустым пересечением. Если выбрана ячейка \(B_{\pi(i)}\), новый интервал равен
$$I_i'=I_i\cap B_{\pi(i)}.$$
Ровно одна ячейка остаётся свободной; она становится интервалом для новой точки. Если инъективного назначения не существует, соответствующая ветвь поиска невозможна.
Для фиксированного шага \(m\) строится двудольный граф: слева текущие интервалы, справа \(m\) ячеек. Ребро между \(I_i\) и \(B_k\) проводится тогда и только тогда, когда
$$I_i\cap B_k\ne\varnothing.$$
Корректный переход эквивалентен инъективному паросочетанию \(n\) текущих интервалов с \(m\) ячейками, при котором одна ячейка остаётся для новой точки. Это и есть Hall-подобное комбинаторное ядро задачи. Реализации не вызывают отдельный алгоритм паросочетания, а напрямую перебирают допустимые назначения и сразу отсекают ветвь, как только состояние становится безнадёжным.
Как только важно только множество оставшихся интервалов, имена точек перестают играть роль. Поэтому после каждого перехода интервалы сортируются по концам. Две разные истории, дающие один и тот же отсортированный список интервалов, приводят к одной и той же дальнейшей подзадаче.
Тем самым поиск превращается в динамическое программирование по каноническим состояниям. Состояние полностью задаётся отсортированным списком полуоткрытых интервалов, и любой повторно встретившийся узел может сразу использовать уже вычисленный ответ.
Когда поиск доходит до \(17\) интервалов, каждый интервал \(I_i=[l_i,u_i)\) содержит все допустимые конечные положения соответствующей точки. Так как нужно минимизировать сумму и каждый интервал включает свой левый конец, минимально возможная сумма в таком терминальном состоянии равна
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
Любой выбор правее только увеличит итог. Поэтому глобальная задача сводится к минимизации целого числителя
$$F=\sum_{i=1}^{17} l_i,$$
а деление на \(d\) выполняется только в самом конце.
В реализациях есть маленькая точная проверка для цели \(4\). В этом случае
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
Одна оптимальная цепочка состояний такова:
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
На четвёртом шаге четвертные ячейки равны \([0,3)\), \([3,6)\), \([6,9)\) и \([9,12)\). Оптимальное уточнение имеет вид
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
Свободной остаётся ячейка \([3,6)\). Значит, четыре конечных левых конца равны \(0,3,6,9\), и потому
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
Именно это проверочное значение зашито в реализациях.
Реализации на C++, Python и Java следуют одному и тому же плану. Сначала вычисляется общий знаменатель \(d\), затем каждое состояние представляется как отсортированный список полуоткрытых интервалов с целыми концами. Из состояния с \(n\) интервалами программа строит \(n+1\) равных ячеек следующего шага и вычисляет все непустые пересечения между интервалами и ячейками.
Если у какого-то интервала нет ни одной совместимой ячейки, состояние немедленно отвергается. Иначе поиск перебирает инъективные назначения, причём сначала берётся интервал с наименьшим числом вариантов: это резко уменьшает ветвление. Один мемоизированный поиск отвечает на вопрос выполнимости, а второй мемоизированный поиск возвращает минимальный числитель \(F\), достижимый из данного состояния.
Финальный десятичный ответ получается точным целочисленным округлением дроби \(F/d\) до двенадцати знаков после запятой. Кроме того, реализации выполняют три внутренние проверки: значение для \(4\) точек равно \(3/2\), динамическая программа для \(6\) совпадает с полным перебором, а выполнимость истинна для \(17\) и ложна для \(18\).
Для состояния с \(n\) интервалами построение ячеек следующего шага и всех пересечений интервал-ячейка стоит \(O(n^2)\), потому что имеется \(n\) интервалов и \(n+1\) ячеек. Самая трудная часть - перебор инъективных назначений; в худшем случае его размер комбинаторен, поэтому теоретическая верхняя оценка экспоненциальна по целевому размеру.
На практике задача для \(17\) становится подъёмной благодаря трём факторам: пересечения быстро сужают варианты, ветвление начинается с наиболее ограниченного интервала, а мемоизация канонических состояний склеивает многие разные истории в одну и ту же подзадачу. Поэтому реальное время работы определяется прежде всего числом различных канонических состояний, которые были посещены, а память пропорциональна числу закэшированных состояний, умноженному на объём интервалов, сохраняемых в каждом из них.
المطلوب هو تصغير المجموع \(x_1+\cdots+x_{17}\) لنقاط تُضاف واحدة بعد الأخرى داخل الفترة الواحدة. بعد إضافة النقطة رقم \(m\)، يجب أن تشغل النقاط الحالية وعددها \(m\) الفترات النصف مفتوحة التالية مرة واحدة بالضبط:
$$\left[\frac{k}{m},\frac{k+1}{m}\right),\qquad k=0,1,\dots,m-1.$$
هذا يعني أن المرحلة \(2\) تفرض وجود نقطة في كل نصف، والمرحلة \(3\) تفرض وجود نقطة في كل ثلث، وهكذا حتى \(m=17\). تقوم التطبيقات بحساب المجموع الأمثل حسابًا دقيقًا، وتثبت أن الشرط ممكن عند \(17\)، كما تتحقق أيضًا من أن الشرط نفسه يفشل عند \(18\).
الفكرة الأساسية هي ألا نتتبع كل عدد حقيقي منفردًا، بل نتتبع فترات عقلانية تمثل أماكنه الممكنة. بما أن جميع القيود اللاحقة لا تفعل أكثر من قص هذه الفترات عند حدود تقسيمات متساوية، فيمكن تنفيذ البحث كله بحسابات صحيحة فقط.
لنعرّف
$$d=\operatorname{lcm}(1,2,\dots,17).$$
وبما أن كل \(m\le 17\) يقسم \(d\)، فإن كل حد من الشكل \(k/m\) يمكن تمثيله بدقة على صورة مضاعف صحيح لـ \(1/d\). لذلك، بدل أن نخزن النقطة \(x\) مباشرة، نخزن فترة
$$I=[l,u)\subseteq[0,d),$$
ومعناها أن موضع النقطة الحقيقي يقع داخل
$$\left[\frac{l}{d},\frac{u}{d}\right).$$
في البداية لا نعرف شيئًا، ولذلك تكون الحالة الابتدائية هي الفترة الوحيدة
$$[0,d).$$
افترض أن لدينا حالة تحتوي على \(n\) فترات، وهذه الحالة تمثل بالفعل جميع قيود المراحل من \(1\) إلى \(n\). للمرحلة التالية نضع
$$m=n+1.$$
الآن تُقسم الفترة الواحدة إلى \(m\) صناديق متساوية، وعلى الشبكة ذات المقام المشترك تصبح
$$B_k=\left[\frac{kd}{m},\frac{(k+1)d}{m}\right),\qquad k=0,1,\dots,m-1.$$
يجب أن تُسند كل فترة حالية \(I_i\) إلى صندوق مختلف يملك تقاطعًا غير فارغ معها. إذا اختير الصندوق \(B_{\pi(i)}\)، فإن الفترة الجديدة تصبح
$$I_i'=I_i\cap B_{\pi(i)}.$$
ويبقى صندوق واحد غير مستخدم، وهذا الصندوق هو فترة النقطة الجديدة. وإذا لم يوجد إسناد أحادي من هذا النوع، فإن ذلك الفرع من البحث يكون مستحيلًا.
عند مرحلة ثابتة \(m\)، يمكن بناء رسم ثنائي الأجزاء: في الجهة اليسرى الفترات الحالية، وفي الجهة اليمنى الصناديق \(m\). نرسم ضلعًا بين \(I_i\) و \(B_k\) إذا وفقط إذا كان
$$I_i\cap B_k\ne\varnothing.$$
إذن الانتقال الصحيح يكافئ مطابقة أحادية للفترات الحالية وعددها \(n\) داخل الصناديق وعددها \(m\)، مع ترك صندوق واحد للنقطة الجديدة. هذا هو الجوهر التوافقي من نوع Hall في المسألة. التطبيقات لا تستدعي خوارزمية مطابقة عامة، بل تبحث مباشرة في هذه الإسنادات وتقص الفرع فورًا عندما تصبح الحالة غير قابلة للإكمال.
ما دام المستقبل يعتمد فقط على مجموعة الفترات الباقية، فإن أسماء النقاط نفسها لا تعود مهمة. لذلك تُرتب الفترات بعد كل انتقال حسب أطرافها. وأي تاريخين مختلفين ينتجان القائمة المرتبة نفسها من الفترات يمثلان في الحقيقة المسألة الفرعية نفسها تمامًا.
بهذا تتحول العملية إلى برمجة ديناميكية على حالات قانونية. فالحالة توصف بالكامل بقائمة مرتبة من الفترات النصف مفتوحة، وأي حالة تتكرر يمكن إعادة استخدام نتيجتها المحفوظة بدل إعادة استكشاف الشجرة كلها.
عندما يصل البحث إلى \(17\) فترة، فإن كل فترة \(I_i=[l_i,u_i)\) تحتوي جميع المواضع النهائية المسموح بها لتلك النقطة. وبما أن المطلوب هو التصغير، وكل فترة تحتوي طرفها الأيسر، فإن أصغر مجموع ممكن داخل تلك الحالة النهائية هو
$$\frac{1}{d}\sum_{i=1}^{17} l_i.$$
وأي اختيار أبعد إلى اليمين لا يمكن إلا أن يزيد المجموع. لذلك يمكن اختزال المسألة العالمية إلى تصغير البسط الصحيح
$$F=\sum_{i=1}^{17} l_i,$$
ثم القسمة على \(d\) مرة واحدة فقط في النهاية.
تحتوي التطبيقات على فحص دقيق صغير عندما يكون الهدف \(4\). عندئذٍ
$$d=\operatorname{lcm}(1,2,3,4)=12.$$
وسلسلة حالات مثلى يمكن أن تكون
$$[0,12)\to [0,6),[6,12)\to [0,4),[4,8),[8,12).$$
في المرحلة الرابعة تكون صناديق الأرباع هي \([0,3)\) و \([3,6)\) و \([6,9)\) و \([9,12)\). وأحد التحسينات المثلى هو
$$[0,4)\to[0,3),\qquad [4,8)\to[6,8),\qquad [8,12)\to[9,12).$$
الصندوق غير المستخدم هو \([3,6)\)، ولذلك تصبح الأطراف اليسرى النهائية \(0,3,6,9\)، ومن ثم
$$F_4=0+3+6+9=18,\qquad \frac{F_4}{12}=\frac{3}{2}.$$
وهذا يطابق تمامًا قيمة التحقق الموجودة داخل التطبيقات.
تسير تطبيقات C++ و Python و Java وفق الخطة نفسها. أولًا يُحسب المقام المشترك \(d\)، ثم تُمثل كل حالة على هيئة قائمة مرتبة من الفترات النصف مفتوحة ذات الأطراف الصحيحة. ومن حالة تحتوي \(n\) فترات، يبني التنفيذ الصناديق المتساوية وعددها \(n+1\) للمرحلة التالية، ثم يحسب جميع التقاطعات غير الفارغة بين الفترات والصناديق.
إذا وُجدت فترة لا تمتلك أي صندوق متوافق، تُرفض الحالة فورًا. وإلا فإن البحث يجرّب الإسنادات الأحادية، مع البدء دائمًا بالفترة ذات أقل عدد من الخيارات، لأن هذا الترتيب يقلل التفرع بشكل واضح. يوجد بحث مذكور يحسم سؤال القابلية فقط، وبحث مذكور آخر يعيد أصغر بسط \(F\) يمكن الوصول إليه من الحالة الحالية.
أما المخرج العشري النهائي فينتج من تقريب دقيق للكسر \(F/d\) إلى اثنتي عشرة خانة عشرية باستخدام حسابات صحيحة. كما تنفذ التطبيقات ثلاثة اختبارات داخلية: قيمة \(4\) نقاط تساوي \(3/2\)، وبرنامج \(6\) نقاط الديناميكي يطابق البحث الشامل، والقابلية صحيحة عند \(17\) وخاطئة عند \(18\).
في حالة تحتوي على \(n\) فترات، فإن بناء صناديق المرحلة التالية وحساب جميع تقاطعات الفترة مع الصندوق يكلف \(O(n^2)\)، لأن هناك \(n\) فترات و \(n+1\) صندوقًا. الجزء الأصعب هو استكشاف الإسنادات الأحادية؛ حجمه في أسوأ الأحوال توافقي، ولذلك فإن الحد النظري الأعلى أسي في حجم الهدف.
عمليًا تصبح المسألة قابلة للحل عند \(17\) بفضل ثلاثة عوامل: التقاطعات تضيق الخيارات بسرعة، والتفرع يبدأ من الفترة الأشد تقييدًا، والتخزين التذكري للحالات القانونية يدمج كثيرًا من المسارات المختلفة في المسألة الفرعية نفسها. لذلك فإن الزمن الفعلي يعتمد أساسًا على عدد الحالات القانونية المختلفة التي زارتها الخوارزمية، بينما تتناسب الذاكرة مع عدد الحالات المخزنة مضروبًا في بيانات الفترات المحفوظة لكل حالة.