Let \(F(m,n)\) be the number of ways to fill a row of length \(n\) with black squares and red blocks of length at least \(m\), under the rule that any two red blocks must be separated by at least one black square. The all-black row is allowed and must be counted. Problem 115 fixes \(m=50\) and asks for the smallest row length \(n\) such that \(F(50,n) \gt 1{,}000{,}000\).
This is the same fill-count function that appears in the previous problem, but the role of \(n\) changes: instead of evaluating one fixed row length, we must understand how the count grows and detect the first row where it crosses the threshold.
Write \(F_m(n)=F(m,n)\). The key is to count arrangements by looking at what happens at the left end of the row. That point of view leads directly to the recurrence used by the implementations.
If \(0 \le n \lt m\), no red block fits at all, so the only legal arrangement is the all-black row. Therefore
$$F_m(0)=1,\qquad F_m(n)=1 \text{ for } 1 \le n \lt m.$$
Those values are the first invariant of the problem: before the row is long enough to hold a red block, the count stays at 1.
Now assume \(n \ge m\). A legal arrangement of length \(n\) falls into two disjoint classes.
First, the row may begin with a black square. Removing that first square leaves any valid arrangement of length \(n-1\), so this case contributes \(F_m(n-1)\).
Second, the row may begin with a red block of length \(b\), where \(m \le b \le n\). If \(b=n\), the whole row is one red block, contributing exactly 1 arrangement. If \(b \lt n\), the separator rule forces the next cell to be black, leaving a residual row of length \(n-b-1\). That contributes \(F_m(n-b-1)\).
So for \(n \ge m\) we obtain the recurrence that the C++, Python, and Java implementations compute directly:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
Equivalently, separating the full-row block from the rest gives
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
The block-length sum becomes clearer if we substitute \(r=n-b-1\). Then \(r\) runs from \(0\) up to \(n-m-1\), so
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
This form shows the structure nicely: every new row length inherits all arrangements of length \(n-1\), adds the single full-row red block, and also adds every earlier arrangement that can sit behind a leading red block and one mandatory separator.
If one subtracts the same formula for \(n-1\), the sum collapses and yields a shorter linear recurrence:
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
The implementations do not need this compressed form, but it is a useful consequence of the same counting argument.
A concrete small example makes the recurrence easy to trust. For minimum red length \(m=3\), the formula gives
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
Using the earlier values \(F_3(6)=11\), \(F_3(3)=2\), and \(F_3(2)=F_3(1)=F_3(0)=1\), we get
$$F_3(7)=11+2+1+1+1+1=17.$$
The terms have a direct interpretation: the row begins with a black square, or with a red block of length \(3\), \(4\), \(5\), \(6\), or \(7\). Whenever the block does not fill the row, one black separator is forced before the remainder.
The function \(F_m(n)\) is monotone in \(n\). Every valid arrangement of length \(n-1\) becomes a valid arrangement of length \(n\) by prefixing one black square, so \(F_m(n) \ge F_m(n-1)\). Once \(n \ge m\), there is also at least one genuinely new arrangement, namely a single red block of length \(n\).
For the target case \(m=50\), the growth starts slowly because no red block fits before length 50:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
Continuing the recurrence shows that the threshold is crossed between 167 and 168:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
Therefore the least \(n\) with \(F(50,n) \gt 10^6\) is \(168\).
The C++, Python, and Java implementations all build a one-dimensional dynamic-programming table for a fixed row length. The entry for length \(n\) begins with the count for \(n-1\), representing a leading black square. Then the implementation tries every admissible red block length from \(m\) to \(n\). A full-row block contributes 1; a shorter block contributes the table entry for the remaining suffix after subtracting the block and the mandatory separator.
Because the table is filled from shorter rows to longer rows, every quantity on the right-hand side has already been computed when it is needed. That is the core invariant that makes the bottom-up approach correct.
After defining the counting routine, the implementation checks row lengths \(n=0,1,2,\dots\) in increasing order and stops at the first one whose fill count exceeds the target. Since the counts are monotone, the first hit is the desired answer. A standard sanity check is the warm-up case \(m=3\), where the first value above one million occurs at \(n=30\); the target instance simply repeats the same search with \(m=50\).
For one fixed length \(L\), building the table up to \(L\) costs
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
time, because each state scans all feasible red block lengths. The memory usage is \(O(L)\) for the dynamic-programming table.
The implementations then repeat that computation for \(L=0,1,2,\dots,N\) until the threshold is first exceeded at \(N=168\). In asymptotic terms, that makes the total running time \(O(N^3)\) with \(O(N)\) peak memory for the code exactly as written. For this problem size the computation is still tiny, which is why the straightforward implementation is perfectly adequate.
Sei \(F(m,n)\) die Anzahl der Möglichkeiten, eine Reihe der Länge \(n\) mit schwarzen Quadraten und roten Blöcken der Länge mindestens \(m\) zu füllen, wobei zwischen zwei roten Blöcken mindestens ein schwarzes Quadrat liegen muss. Die vollständig schwarze Reihe ist erlaubt und wird mitgezählt. In Problem 115 ist \(m=50\) fest vorgegeben, und gesucht ist die kleinste Länge \(n\), für die \(F(50,n) \gt 1{,}000{,}000\) gilt.
Damit wird dieselbe Zählfunktion wie im vorherigen Problem verwendet, aber mit einer anderen Fragestellung: Nicht ein festes \(n\) ist gegeben, sondern der erste Schwellenwertüberschritt muss gefunden werden.
Wir schreiben \(F_m(n)=F(m,n)\). Der natürliche Zugang ist eine Fallunterscheidung am linken Rand der Reihe. Genau daraus entsteht die Rekurrenz, die in allen drei Implementierungen verwendet wird.
Für \(0 \le n \lt m\) passt kein roter Block in die Reihe. Deshalb gibt es genau eine zulässige Füllung, nämlich die komplett schwarze:
$$F_m(0)=1,\qquad F_m(n)=1 \text{ für } 1 \le n \lt m.$$
Das ist die erste zentrale Invariante: Solange die Reihe kürzer als \(m\) ist, bleibt der Wert konstant bei 1.
Nun sei \(n \ge m\). Jede zulässige Füllung der Länge \(n\) gehört genau zu einer von zwei Klassen.
Entweder beginnt die Reihe mit einem schwarzen Quadrat. Entfernt man dieses, bleibt eine beliebige gültige Füllung der Länge \(n-1\). Dieser Fall liefert also \(F_m(n-1)\).
Oder die Reihe beginnt mit einem roten Block der Länge \(b\) mit \(m \le b \le n\). Im Sonderfall \(b=n\) füllt ein einzelner roter Block die ganze Reihe, also gibt es genau 1 Möglichkeit. Für \(b \lt n\) erzwingt die Abstandsbedingung direkt danach ein schwarzes Quadrat; übrig bleibt dann eine Restreihe der Länge \(n-b-1\), die auf \(F_m(n-b-1)\) Arten gefüllt werden kann.
Für \(n \ge m\) erhält man damit genau die Rekurrenz, die der Code auswertet:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
Getrennt nach dem Vollblockfall geschrieben:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
Setzt man \(r=n-b-1\), dann läuft \(r\) von \(0\) bis \(n-m-1\), und die Rekurrenz wird zu
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
Diese Form macht die Struktur besonders klar: Von der Länge \(n-1\) wird alles übernommen, dazu kommt der eine Vollblock und außerdem jede frühere Füllung, die hinter einen führenden roten Block plus verpflichtenden Trenner gesetzt werden kann.
Subtrahiert man die entsprechende Formel für \(n-1\), fällt die Summe zusammen, und man bekommt die kürzere lineare Rekurrenz
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
Diese kompaktere Gleichung wird im Code nicht benötigt, folgt aber aus derselben Zählidee.
Ein kleines Beispiel macht die Rekurrenz greifbar. Für Mindestblocklänge \(m=3\) gilt
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
Mit \(F_3(6)=11\), \(F_3(3)=2\) und \(F_3(2)=F_3(1)=F_3(0)=1\) folgt
$$F_3(7)=11+2+1+1+1+1=17.$$
Die Summanden entsprechen genau den Möglichkeiten, dass die Reihe mit Schwarz beginnt oder mit einem roten Block der Länge \(3\), \(4\), \(5\), \(6\) oder \(7\). Füllt der Block die Reihe nicht komplett, muss danach sofort ein schwarzer Trenner kommen.
Die Funktion \(F_m(n)\) ist monoton in \(n\). Jede gültige Füllung der Länge \(n-1\) liefert durch Voranstellen eines schwarzen Quadrats eine gültige Füllung der Länge \(n\). Also gilt stets \(F_m(n) \ge F_m(n-1)\). Für \(n \ge m\) kommt sogar mindestens eine echte neue Füllung hinzu, nämlich ein einzelner roter Block der Länge \(n\).
Im Zielproblem mit \(m=50\) beginnt das Wachstum deshalb langsam:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
Führt man die Rekurrenz weiter aus, liegt der erste Überschritt der Millionenschwelle zwischen 167 und 168:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
Damit ist die gesuchte kleinste Länge \(n=168\).
Die C++-, Python- und Java-Implementierungen bauen für eine feste Reihenlänge eine eindimensionale Dynamic-Programming-Tabelle auf. Der Eintrag für Länge \(n\) startet mit dem Wert für \(n-1\), also dem Fall eines führenden schwarzen Quadrats. Danach werden alle zulässigen roten Blocklängen von \(m\) bis \(n\) ausprobiert. Ein Block, der die ganze Reihe füllt, trägt 1 bei; ein kürzerer Block trägt den Tabellenwert der verbleibenden Restlänge nach Block und Trenner bei.
Da die Tabelle von kurzen zu langen Reihen gefüllt wird, sind alle benötigten rechten Seiten bereits bekannt, wenn ein neuer Wert berechnet wird. Genau diese bottom-up-Invariante macht den Ansatz korrekt.
Nach der Definition der Zählroutine werden die Reihenlängen \(n=0,1,2,\dots\) der Reihe nach getestet. Beim ersten \(n\), dessen Fill-Count den Zielwert überschreitet, stoppt das Programm. Wegen der Monotonie ist dieser erste Treffer genau die gesuchte Antwort. Als Plausibilitätscheck dient der bekannte Fall \(m=3\): Dort wird die Million erstmals bei \(n=30\) überschritten; für Problem 115 wird dieselbe Suche nur mit \(m=50\) wiederholt.
Für eine feste Länge \(L\) kostet der Aufbau der Tabelle bis \(L\)
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
Zeit, weil für jeden Zustand alle zulässigen Blocklängen durchlaufen werden. Der Speicherbedarf liegt bei \(O(L)\).
Die Implementierungen wiederholen diese Berechnung dann für \(L=0,1,2,\dots,N\), bis die Schwelle erstmals bei \(N=168\) überschritten ist. Asymptotisch ergibt das für den vorliegenden Code insgesamt \(O(N^3)\) Zeit bei \(O(N)\) Spitzenspeicher. Für diese Eingabegröße ist das trotzdem mühelos schnell.
\(F(m,n)\), uzunluğu \(n\) olan bir satırı siyah kareler ve uzunluğu en az \(m\) olan kırmızı bloklarla doldurma sayısı olsun. Kural şudur: iki kırmızı blok arasında en az bir siyah kare bulunmalıdır. Tamamen siyah satır da geçerli kabul edilir ve sayıya dahildir. Problem 115, \(m=50\) için \(F(50,n) \gt 1{,}000{,}000\) koşulunu sağlayan en küçük \(n\) değerini sorar.
Bu, bir önceki problemdeki dolum sayısı fonksiyonunun aynısıdır; fark şu ki burada sabit bir satır uzunluğu değerlendirilmez. Bunun yerine sayının ilk kez hangi uzunlukta bir milyon eşiğini geçtiğini bulmak gerekir.
\(F_m(n)=F(m,n)\) yazalım. En doğal ayrım satırın sol ucunda yapılır. Kodun kullandığı yineleme bağıntısı doğrudan bu ayrımdan çıkar.
\(0 \le n \lt m\) iken hiçbir kırmızı blok satıra sığmaz. Bu yüzden tek geçerli düzenleme tamamen siyah olandır:
$$F_m(0)=1,\qquad F_m(n)=1 \text{ for } 1 \le n \lt m.$$
Bu ilk temel invariandır: satır uzunluğu \(m\)'ye ulaşana kadar değer sürekli 1 kalır.
Şimdi \(n \ge m\) olsun. Uzunluğu \(n\) olan her geçerli düzenleme iki ayrık sınıftan birine girer.
Birinci olasılık, satırın siyah kare ile başlamasıdır. İlk siyah kareyi kaldırınca geriye uzunluğu \(n-1\) olan herhangi bir geçerli düzenleme kalır. Bu dalın katkısı \(F_m(n-1)\) olur.
İkinci olasılık, satırın uzunluğu \(b\) olan bir kırmızı blokla başlamasıdır; burada \(m \le b \le n\). Eğer \(b=n\) ise blok tüm satırı tek başına doldurur ve tam 1 düzenleme verir. Eğer \(b \lt n\) ise ayırma kuralı gereği bloktan hemen sonra bir siyah kare gelmek zorundadır; böylece geriye uzunluğu \(n-b-1\) olan bir kuyruk kalır ve bunun katkısı \(F_m(n-b-1)\) olur.
Böylece \(n \ge m\) için uygulamaların doğrudan hesapladığı bağıntı elde edilir:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
Tüm satırı dolduran blok durumunu ayırırsak aynı bağıntı
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1$$
şeklinde yazılır.
\(r=n-b-1\) değişkenini koyarsak \(r\), \(0\) ile \(n-m-1\) arasında dolaşır ve formül
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m)$$
biçimine gelir. Bu yazım, yapıyı daha açık gösterir: yeni uzunluk, önceki uzunluğun tüm düzenlemelerini miras alır; ayrıca tek bir tam-kaplayan kırmızı blok eklenir ve bir de başta kırmızı blok artı zorunlu ayraç kullanılarak daha kısa tüm kuyruklar eklenir.
Bir önceki uzunluk için yazılan formül çıkarılırsa toplam çöker ve daha kısa lineer bağıntı ortaya çıkar:
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
Kod bu sıkıştırılmış biçime ihtiyaç duymaz; yine de aynı sayım mantığının doğal sonucudur.
Küçük bir örnek bağıntıyı somutlaştırır. Minimum kırmızı blok uzunluğu \(m=3\) için
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1$$
olur. Daha önceki değerler \(F_3(6)=11\), \(F_3(3)=2\) ve \(F_3(2)=F_3(1)=F_3(0)=1\) olduğundan
$$F_3(7)=11+2+1+1+1+1=17.$$
Buradaki terimler doğrudan şu başlangıç seçeneklerine karşılık gelir: satır siyahla başlar ya da uzunluğu \(3\), \(4\), \(5\), \(6\) veya \(7\) olan bir kırmızı blokla başlar. Blok tüm satırı kaplamıyorsa ardından mutlaka bir siyah ayraç gelir.
\(F_m(n)\) fonksiyonu \(n\)'ye göre monotondur. Uzunluğu \(n-1\) olan her geçerli düzenleme başına bir siyah kare eklenerek uzunluğu \(n\) olan geçerli bir düzenlemeye dönüştürülebilir; dolayısıyla \(F_m(n) \ge F_m(n-1)\). Üstelik \(n \ge m\) olduğunda en az bir gerçekten yeni düzenleme de vardır: tüm satırı kaplayan tek kırmızı blok.
Hedef durum olan \(m=50\) için büyüme bu yüzden çok yavaş başlar:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
Bağıntı sürdürüldüğünde bir milyon eşiğinin 167 ile 168 arasında aşıldığı görülür:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
Böylece istenen en küçük uzunluk \(n=168\) olur.
C++, Python ve Java uygulamaları sabit bir satır uzunluğu için tek boyutlu bir dinamik programlama tablosu kurar. Uzunluk \(n\) için değer, önce önde gelen siyah kare durumunu temsil eden \(n-1\) sayısından başlatılır. Ardından \(m\) ile \(n\) arasındaki her geçerli kırmızı blok uzunluğu denenir. Tüm satırı kaplayan blok 1 katkı verir; daha kısa blok ise blok ve zorunlu ayraç çıkarıldıktan sonra kalan kuyruğun tablo değerini ekler.
Tablo kısa satırlardan uzun satırlara doğru doldurulduğu için sağ tarafta kullanılan bütün değerler ihtiyaç anında zaten hazırdır. Bottom-up yaklaşımın doğruluğunu sağlayan temel invariant budur.
Sayım yordamı tanımlandıktan sonra uygulama \(n=0,1,2,\dots\) değerlerini artan sırayla dener ve dolum sayısı hedefi geçtiği anda durur. Sayılar monoton olduğu için ilk bulunan değer doğrudan cevaptır. Isınma örneği olarak \(m=3\) için ilk milyon aşımı \(n=30\)'da gerçekleşir; Problem 115 aynı aramayı yalnızca \(m=50\) ile tekrarlar.
Sabit bir \(L\) uzunluğu için tabloyu \(L\)'ye kadar kurmanın maliyeti
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
zamandır; çünkü her durumda bütün uygun kırmızı blok uzunlukları dolaşılır. Bellek kullanımı tablo için \(O(L)\)'dir.
Daha sonra uygulamalar bu hesabı eşik ilk kez \(N=168\)'de aşılana kadar \(L=0,1,2,\dots,N\) için tekrarlar. Bu nedenle, kod tam mevcut haliyle değerlendirildiğinde toplam çalışma süresi asimptotik olarak \(O(N^3)\), tepe bellek kullanımı ise \(O(N)\) olur. Problem boyutu küçük olduğu için bu yalın yaklaşım fazlasıyla yeterlidir.
Sea \(F(m,n)\) el número de maneras de rellenar una fila de longitud \(n\) usando cuadrados negros y bloques rojos de longitud al menos \(m\), con la condición de que dos bloques rojos cualesquiera deben estar separados por al menos un cuadrado negro. La fila completamente negra está permitida y cuenta. El Problema 115 fija \(m=50\) y pide el menor \(n\) para el cual \(F(50,n) \gt 1{,}000{,}000\).
La función de conteo es la misma que en el problema anterior, pero aquí la incógnita no es el valor de \(F\) para una longitud dada, sino la primera longitud en la que ese conteo supera un umbral.
Escribamos \(F_m(n)=F(m,n)\). La forma natural de derivar la solución es clasificar las configuraciones por lo que ocurre en el extremo izquierdo de la fila. Esa descomposición produce exactamente la recurrencia usada por las implementaciones.
Si \(0 \le n \lt m\), ningún bloque rojo cabe en la fila. Por tanto, solo existe una disposición válida: la fila totalmente negra.
$$F_m(0)=1,\qquad F_m(n)=1 \text{ para } 1 \le n \lt m.$$
Esta es la primera invariante importante del problema: antes de llegar a longitud \(m\), el conteo permanece fijado en 1.
Supongamos ahora \(n \ge m\). Toda disposición válida de longitud \(n\) pertenece exactamente a una de dos clases disjuntas.
La primera clase consiste en las filas que empiezan con un cuadrado negro. Al eliminar ese cuadrado inicial queda cualquier disposición válida de longitud \(n-1\), así que esta parte aporta \(F_m(n-1)\).
La segunda clase consiste en las filas que empiezan con un bloque rojo de longitud \(b\), donde \(m \le b \le n\). Si \(b=n\), el bloque ocupa toda la fila y aporta exactamente 1 disposición. Si \(b \lt n\), la regla de separación obliga a colocar un cuadrado negro inmediatamente después del bloque, quedando una cola de longitud \(n-b-1\), que puede rellenarse de \(F_m(n-b-1)\) maneras.
Por ello, para \(n \ge m\) se obtiene la recurrencia calculada directamente por el código:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
Separando el caso del bloque que llena la fila completa:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
Si hacemos el cambio \(r=n-b-1\), entonces \(r\) recorre los valores de \(0\) a \(n-m-1\), y la recurrencia adopta la forma
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
Esta escritura aclara el mecanismo del crecimiento: toda fila de longitud \(n\) hereda las soluciones de longitud \(n-1\), añade el bloque rojo que cubre toda la fila y además añade todas las colas más cortas que pueden colocarse detrás de un bloque rojo inicial y de un separador obligatorio.
Restando la fórmula correspondiente a \(n-1\), la suma telescopa y aparece una recurrencia lineal más compacta:
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
El código no necesita esta versión reducida, pero es una consecuencia útil de la misma descomposición combinatoria.
Un ejemplo pequeño ayuda a verificar la fórmula. Con longitud mínima roja \(m=3\), se obtiene
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
Usando \(F_3(6)=11\), \(F_3(3)=2\) y \(F_3(2)=F_3(1)=F_3(0)=1\), resulta
$$F_3(7)=11+2+1+1+1+1=17.$$
Cada sumando corresponde a una elección inicial concreta: la fila empieza con negro, o bien con un bloque rojo de longitud \(3\), \(4\), \(5\), \(6\) o \(7\). Siempre que el bloque no ocupe toda la fila, queda forzado un separador negro antes del resto.
La función \(F_m(n)\) es monótona con respecto a \(n\). Toda disposición válida de longitud \(n-1\) produce una disposición válida de longitud \(n\) al anteponer un cuadrado negro, de modo que \(F_m(n) \ge F_m(n-1)\). Además, cuando \(n \ge m\), aparece al menos una disposición nueva: un único bloque rojo de longitud \(n\).
En el caso objetivo \(m=50\), el crecimiento empieza despacio porque antes de la longitud 50 no cabe ningún bloque rojo:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
Continuando la recurrencia se observa que el umbral se cruza entre 167 y 168:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
Por tanto, la menor longitud pedida es \(n=168\).
Las implementaciones en C++, Python y Java construyen una tabla unidimensional de programación dinámica para una longitud de fila fija. La entrada correspondiente a \(n\) empieza copiando el valor de \(n-1\), que representa el caso de un cuadrado negro inicial. Después la implementación recorre todas las longitudes de bloque rojo admisibles entre \(m\) y \(n\). Un bloque que llena la fila completa aporta 1; un bloque más corto aporta la entrada de la tabla correspondiente a la cola restante tras descontar el bloque y el separador obligatorio.
Como la tabla se rellena de filas cortas a largas, cada cantidad de la parte derecha ya ha sido calculada cuando se necesita. Esa es la invariante central del enfoque bottom-up.
Una vez definida la rutina de conteo, la implementación prueba \(n=0,1,2,\dots\) en orden creciente y se detiene en el primer valor cuyo fill-count supera el objetivo. Como la función es monótona, ese primer acierto es exactamente la respuesta buscada. Un control útil es el caso \(m=3\), donde el primer valor superior a un millón aparece en \(n=30\); el problema real repite el mismo procedimiento con \(m=50\).
Para una longitud fija \(L\), construir la tabla hasta \(L\) cuesta
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
tiempo, porque cada estado examina todas las longitudes rojas posibles. La memoria usada es \(O(L)\).
Después, las implementaciones repiten ese cálculo para \(L=0,1,2,\dots,N\) hasta que el umbral se supera por primera vez en \(N=168\). Así, el tiempo total del código tal como está escrito es \(O(N^3)\), con memoria máxima \(O(N)\). Dado lo pequeño del valor final, esta estrategia directa sigue siendo sobradamente rápida.
设 \(F(m,n)\) 表示用黑色方块和长度至少为 \(m\) 的红色块去填满长度为 \(n\) 的一行的方法数，其中任意两个红色块之间至少要隔一个黑色方块。全黑方案也是合法方案，必须计入。第 115 题固定 \(m=50\)，要求找出满足 \(F(50,n) \gt 1{,}000{,}000\) 的最小行长 \(n\)。
这道题沿用了上一题的同一个填充计数函数，但问法不同。这里不是计算某个固定长度的方案数，而是要找出这个函数第一次超过给定阈值的位置。
记 \(F_m(n)=F(m,n)\)。最自然的切入点是观察一行最左端发生了什么。只要按左端分类，代码中使用的递推关系就会直接出现。
当 \(0 \le n \lt m\) 时，任何红色块都放不进去，因此唯一合法的方案就是整行全黑：
$$F_m(0)=1,\qquad F_m(n)=1 \text{ for } 1 \le n \lt m.$$
这就是问题的第一个不变量：只要行长还没有达到最小红块长度 \(m\)，计数就始终等于 1。
现在设 \(n \ge m\)。任何一个长度为 \(n\) 的合法填充，恰好属于下面两类之一。
第一类是最左端放一个黑色方块。去掉这个黑方块后，剩下的是一行长度为 \(n-1\) 的任意合法填充，因此这一类贡献 \(F_m(n-1)\)。
第二类是最左端放一个长度为 \(b\) 的红色块，其中 \(m \le b \le n\)。如果 \(b=n\)，说明一个红色块正好铺满整行，这一类只贡献 1。若 \(b \lt n\)，由于两个红块之间必须至少隔一个黑方块，红块后面紧接着必须放一个黑方块，于是还剩下一段长度为 \(n-b-1\) 的尾部，它可以用 \(F_m(n-b-1)\) 种方式填充。
因此，对所有 \(n \ge m\)，得到与 C++、Python、Java 实现完全一致的递推式：
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
把“红块恰好铺满整行”的情况单独写出来，也可以写成
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
令 \(r=n-b-1\)，那么 \(r\) 从 \(0\) 取到 \(n-m-1\)，递推式就变成
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
这个形式更容易看出结构：长度为 \(n\) 的所有方案，先完整继承长度为 \(n-1\) 的所有方案；再加上“整行只有一个红块”的那 1 种方案；最后再加上所有“前面放一个红块和一个强制黑色分隔，再接一段较短合法尾部”的方案。
如果把 \(n-1\) 对应的公式从上式中减掉，求和部分会塌缩，于是得到更短的线性递推：
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
代码本身并没有利用这个压缩后的形式，但它确实是同一个组合计数思路的直接推论。
用一个小例子可以更直观地验证公式。设最小红块长度 \(m=3\)，则
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
已知 \(F_3(6)=11\)、\(F_3(3)=2\)，并且 \(F_3(2)=F_3(1)=F_3(0)=1\)，所以
$$F_3(7)=11+2+1+1+1+1=17.$$
每一项都有明确含义：这一行要么先放一个黑方块，要么先放长度分别为 \(3\)、\(4\)、\(5\)、\(6\)、\(7\) 的红块。只要红块没有铺满整行，后面就必须立即放一个黑色分隔块，然后尾部继续按照同样规则计数。
\(F_m(n)\) 关于 \(n\) 是单调不减的。因为任何一个长度为 \(n-1\) 的合法方案，在最前面补一个黑方块，就得到一个长度为 \(n\) 的合法方案，所以总有 \(F_m(n) \ge F_m(n-1)\)。而当 \(n \ge m\) 时，还至少会多出一个真正的新方案，即“整行恰好由一个长度为 \(n\) 的红块组成”。
对目标参数 \(m=50\) 来说，增长一开始非常慢，因为在长度到达 50 之前根本放不下任何红块：
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
继续用递推往前算，就会发现阈值恰好在 167 和 168 之间被越过：
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
因此，满足 \(F(50,n) \gt 10^6\) 的最小 \(n\) 是 \(168\)。
C++、Python 和 Java 实现都先针对某个固定行长构造一维动态规划表。长度为 \(n\) 的表项，先从长度 \(n-1\) 的计数开始，对应“最左端放一个黑方块”的情况。随后程序枚举所有允许的红块长度 \(b \in [m,n]\)。如果红块恰好铺满整行，就加 1；如果红块更短，就把“去掉红块和强制分隔黑块以后剩下的尾部”的计数加进来。
由于表是按长度从小到大填的，所以每次用到的右侧值都已经算好。这就是自底向上的核心不变量，也是实现正确性的基础。
定义好计数过程以后，程序从 \(n=0,1,2,\dots\) 按顺序尝试，直到第一次出现填充数超过目标值的长度为止。由于函数单调，这个第一次命中的长度就是答案。题目里的热身参数 \(m=3\) 会在 \(n=30\) 首次超过一百万；目标实例只是把同样的搜索改为 \(m=50\)。
对于一个固定长度 \(L\)，把动态规划表算到 \(L\) 的时间代价为
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2),$$
因为每个状态都要枚举所有可行的红块长度。所需空间是存储这张表的 \(O(L)\)。
接着，程序会把这个过程对 \(L=0,1,2,\dots,N\) 重复执行，直到阈值首次在 \(N=168\) 被超过。因此，对当前实现本身来说，总时间复杂度是 \(O(N^3)\)，峰值空间复杂度是 \(O(N)\)。由于最终答案只有 168，这样的直接写法仍然非常轻量。
Пусть \(F(m,n)\) обозначает число способов заполнить ряд длины \(n\) черными клетками и красными блоками длины не меньше \(m\), причем между любыми двумя красными блоками должна стоять хотя бы одна черная клетка. Полностью черный ряд разрешен и тоже считается. В задаче 115 фиксируется \(m=50\), и требуется найти наименьшее \(n\), для которого \(F(50,n) \gt 1{,}000{,}000\).
Это та же функция подсчета, что и в предыдущей задаче, но теперь нужно не вычислить значение в одной точке, а определить первую длину ряда, на которой число допустимых заполнений превышает заданный порог.
Будем писать \(F_m(n)=F(m,n)\). Удобнее всего разбирать допустимые раскладки по тому, что находится у левого края ряда. Именно так получается рекуррентная формула, реализованная в коде.
Если \(0 \le n \lt m\), то ни один красный блок не помещается в ряд. Поэтому существует ровно одна допустимая раскладка: весь ряд черный.
$$F_m(0)=1,\qquad F_m(n)=1 \text{ для } 1 \le n \lt m.$$
Это первый важный инвариант задачи: пока длина меньше \(m\), значение функции не меняется и остается равным 1.
Теперь предположим, что \(n \ge m\). Любая допустимая раскладка длины \(n\) относится ровно к одному из двух непересекающихся случаев.
Первый случай: ряд начинается с черной клетки. Если убрать ее, останется любая допустимая раскладка длины \(n-1\). Значит, этот случай дает вклад \(F_m(n-1)\).
Второй случай: ряд начинается с красного блока длины \(b\), где \(m \le b \le n\). Если \(b=n\), один красный блок заполняет весь ряд и дает ровно 1 раскладку. Если \(b \lt n\), условие разделения красных блоков заставляет поставить сразу после него черную клетку, а затем остается хвост длины \(n-b-1\), который можно заполнить \(F_m(n-b-1)\) способами.
Поэтому для \(n \ge m\) получаем точную рекурсию, которую вычисляют реализации на C++, Python и Java:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
Если вынести случай полного заполнения отдельным слагаемым, получится
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
Положим \(r=n-b-1\). Тогда \(r\) пробегает значения от \(0\) до \(n-m-1\), и формула принимает вид
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
Теперь структура роста видна особенно ясно: новая длина наследует все раскладки длины \(n-1\), добавляет единственный вариант с одним красным блоком на весь ряд и добавляет все более короткие хвосты, которые можно поставить после начального красного блока и обязательного разделителя.
Если вычесть такую же формулу для \(n-1\), сумма схлопывается, и получается более короткая линейная рекурсия:
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
В программе эта сокращенная форма не используется, но она полезна для понимания поведения той же самой счетной схемы.
Небольшой пример позволяет быстро проверить корректность формулы. Для \(m=3\) имеем
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
Подставляя \(F_3(6)=11\), \(F_3(3)=2\) и \(F_3(2)=F_3(1)=F_3(0)=1\), получаем
$$F_3(7)=11+2+1+1+1+1=17.$$
Слагаемые имеют прямой смысл: ряд либо начинается с черной клетки, либо с красного блока длины \(3\), \(4\), \(5\), \(6\) или \(7\). Если блок не занимает весь ряд, после него обязателен один черный разделитель.
Функция \(F_m(n)\) монотонна по \(n\). Любую допустимую раскладку длины \(n-1\) можно превратить в допустимую раскладку длины \(n\), дописав слева одну черную клетку. Следовательно, всегда выполняется \(F_m(n) \ge F_m(n-1)\). А когда \(n \ge m\), появляется и по крайней мере одна новая раскладка: один красный блок длины \(n\).
Для целевого случая \(m=50\) рост начинается медленно, потому что до длины 50 красный блок вообще не помещается:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
Дальнейшее применение рекурсии показывает, что порог пересекается между 167 и 168:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
Значит, искомая наименьшая длина равна \(168\).
Реализации на C++, Python и Java строят одномерную таблицу динамического программирования для фиксированной длины ряда. Значение для длины \(n\) начинается с числа для \(n-1\), что соответствует случаю ведущей черной клетки. Затем программа перебирает все допустимые длины красного блока от \(m\) до \(n\). Если блок закрывает весь ряд, добавляется 1; если блок короче, добавляется значение таблицы для оставшегося хвоста после удаления блока и обязательного черного разделителя.
Таблица заполняется снизу вверх, от коротких рядов к длинным, поэтому каждая величина в правой части уже известна к моменту использования. Это и есть основной инвариант, обеспечивающий корректность метода.
После этого программа проверяет длины \(n=0,1,2,\dots\) по порядку и останавливается на первой длине, для которой значение fill-count превосходит целевой порог. Из-за монотонности первый найденный успех и есть ответ. Удобная проверка правильности - случай \(m=3\), где миллион впервые превышается при \(n=30\); для основной задачи выполняется точно такой же поиск, только с \(m=50\).
Для одной фиксированной длины \(L\) построение таблицы до \(L\) требует
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
времени, потому что в каждом состоянии перебираются все допустимые длины красного блока. Память составляет \(O(L)\).
Затем реализации повторяют тот же расчет для \(L=0,1,2,\dots,N\), пока порог впервые не будет превышен при \(N=168\). Поэтому для кода именно в таком виде суммарное время равно \(O(N^3)\), а пиковая память - \(O(N)\). При таком маленьком конечном значении это все равно очень быстро.
لتكن \(F(m,n)\) هي عدد الطرق لملء صف طوله \(n\) باستخدام مربعات سوداء وكتل حمراء طول كل منها لا يقل عن \(m\)، مع شرط وجود مربع أسود واحد على الأقل بين أي كتلتين حمراوين. الصف الأسود بالكامل مسموح ويُحسب ضمن العدد. في المسألة 115 نثبت \(m=50\)، والمطلوب هو أصغر طول \(n\) يحقق \(F(50,n) \gt 1{,}000{,}000\).
هذه هي دالة العد نفسها التي ظهرت في المسألة السابقة، لكن السؤال هنا مختلف: لا نريد قيمة الدالة عند طول ثابت، بل أول طول يتجاوز عنده العدد عتبة المليون.
سنكتب \(F_m(n)=F(m,n)\). الفكرة الطبيعية هي تصنيف جميع الترتيبات بحسب ما يحدث عند الطرف الأيسر من الصف. ومن هذا التصنيف تخرج مباشرة علاقة التكرار التي تعتمد عليها التطبيقات.
إذا كان \(0 \le n \lt m\)، فلا توجد أي كتلة حمراء يمكن أن تدخل في الصف. لذلك يوجد ترتيب قانوني واحد فقط، وهو الصف الأسود بالكامل:
$$F_m(0)=1,\qquad F_m(n)=1 \text{ for } 1 \le n \lt m.$$
وهذا هو أول ثابت بنيوي في المسألة: ما دام الطول أصغر من \(m\)، يبقى العدد مساويًا لـ 1.
الآن افترض أن \(n \ge m\). كل ترتيب قانوني لطول \(n\) يقع بالضبط في واحدة من حالتين منفصلتين.
الحالة الأولى أن يبدأ الصف بمربع أسود. إذا حذفنا هذا المربع الأول، بقي لدينا أي ترتيب قانوني لطول \(n-1\)، ولذلك تساهم هذه الحالة بمقدار \(F_m(n-1)\).
الحالة الثانية أن يبدأ الصف بكتلة حمراء طولها \(b\)، حيث \(m \le b \le n\). إذا كان \(b=n\)، فكتلة حمراء واحدة تملأ الصف كله، وهذه تعطي ترتيبًا واحدًا فقط. وإذا كان \(b \lt n\)، فإن شرط الفصل يفرض أن يكون الموضع التالي مباشرة مربعًا أسود، ثم يتبقى ذيل طوله \(n-b-1\) يمكن ملؤه بعدد \(F_m(n-b-1)\) من الطرق.
إذن، عندما \(n \ge m\)، نحصل على علاقة التكرار التي تحسبها تطبيقات C++ وPython وJava مباشرة:
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n}\begin{cases}1,& b=n,\\\\ F_m(n-b-1),& b \lt n.\end{cases}$$
وبفصل حالة الكتلة التي تملأ الصف كاملًا، يمكن كتابة العلاقة أيضًا على الصورة
$$F_m(n)=F_m(n-1)+\sum_{b=m}^{n-1}F_m(n-b-1)+1.$$
إذا وضعنا \(r=n-b-1\)، فإن \(r\) يتحرك من \(0\) حتى \(n-m-1\)، وعندها تصبح العلاقة
$$F_m(n)=F_m(n-1)+1+\sum_{r=0}^{n-m-1}F_m(r)\qquad (n \ge m).$$
هذه الصيغة توضح البنية بجلاء: كل صف جديد بطول \(n\) يرث جميع ترتيبات الطول \(n-1\)، ثم يضيف ترتيب الكتلة الحمراء الواحدة التي تغطي الصف كله، ثم يضيف كل الذيول الأقصر التي يمكن وضعها بعد كتلة حمراء في البداية وبعد فاصل أسود إجباري.
وإذا طرحنا منها الصيغة المقابلة لـ \(n-1\)، ينهار المجموع إلى علاقة خطية أقصر:
$$F_m(n)=2F_m(n-1)-F_m(n-2)+F_m(n-m-1)\qquad (n \ge m+1).$$
الكود لا يحتاج إلى هذه الصيغة المختصرة، لكنها نتيجة مباشرة للفكرة العدّية نفسها.
مثال صغير يجعل العلاقة ملموسة. عندما يكون الحد الأدنى لطول الكتلة الحمراء \(m=3\)، فإن
$$F_3(7)=F_3(6)+F_3(3)+F_3(2)+F_3(1)+F_3(0)+1.$$
وباستخدام القيم \(F_3(6)=11\) و\(F_3(3)=2\) و\(F_3(2)=F_3(1)=F_3(0)=1\)، نحصل على
$$F_3(7)=11+2+1+1+1+1=17.$$
كل حد هنا له معنى مباشر: الصف إما أن يبدأ بمربع أسود، أو يبدأ بكتلة حمراء طولها \(3\) أو \(4\) أو \(5\) أو \(6\) أو \(7\). وإذا لم تملأ الكتلة الصف كله، فبعدها مباشرة يأتي فاصل أسود إلزامي.
الدالة \(F_m(n)\) رتيبة بالنسبة إلى \(n\). فكل ترتيب قانوني لطول \(n-1\) يمكن تحويله إلى ترتيب قانوني لطول \(n\) بإضافة مربع أسود في البداية، ولذلك دائمًا \(F_m(n) \ge F_m(n-1)\). وعندما \(n \ge m\)، يظهر على الأقل ترتيب جديد واحد فعلًا، وهو صف مكوَّن من كتلة حمراء واحدة طولها \(n\).
في الحالة الهدف \(m=50\)، يبدأ النمو ببطء شديد لأن الكتل الحمراء لا تدخل قبل الطول 50:
$$F_{50}(0)=1,\quad F_{50}(49)=1,\quad F_{50}(50)=2,\quad F_{50}(51)=4.$$
وبمتابعة التكرار نجد أن تجاوز عتبة المليون يحدث بين 167 و168:
$$F_{50}(167)=978181,\qquad F_{50}(168)=1053389.$$
إذًا أصغر طول مطلوب هو \(168\).
تقوم تطبيقات C++ وPython وJava ببناء جدول برمجة ديناميكية أحادي البعد لطول صف ثابت. تبدأ قيمة الطول \(n\) من قيمة \(n-1\)، وهي تمثل حالة البدء بمربع أسود. بعد ذلك يجرّب التنفيذ كل طول مسموح للكتلة الحمراء من \(m\) إلى \(n\). إذا كانت الكتلة تملأ الصف كله، يُضاف 1. وإذا كانت أقصر، تُضاف قيمة الجزء المتبقي بعد حذف الكتلة والفاصل الأسود الإجباري.
ولأن الجدول يُملأ من الأطوال الصغيرة إلى الكبيرة، فإن كل قيمة موجودة في الطرف الأيمن تكون قد حُسبت مسبقًا عند الحاجة إليها. وهذا هو الثابت الأساسي الذي يجعل أسلوب البناء من الأسفل إلى الأعلى صحيحًا.
بعد تعريف روتين العد، يبدأ التنفيذ بفحص \(n=0,1,2,\dots\) بترتيب تصاعدي، ويتوقف عند أول طول يتجاوز فيه عدد الترتيبات الهدف المطلوب. وبما أن الدالة رتيبة، فإن أول نجاح هو الجواب مباشرة. وتوجد حالة تحقق معيارية عندما \(m=3\)، حيث يحدث أول تجاوز للمليون عند \(n=30\)؛ أما المسألة الأصلية فتكرر الفكرة نفسها مع \(m=50\).
بالنسبة إلى طول ثابت \(L\)، فإن بناء الجدول حتى \(L\) يحتاج إلى
$$\sum_{n=1}^{L}\max(0,n-m+1)=O(L^2)$$
من الزمن، لأن كل حالة تمر على جميع أطوال الكتل الحمراء الممكنة. أما الذاكرة فهي \(O(L)\) لتخزين الجدول.
بعد ذلك تعيد التطبيقات الحساب نفسه للأطوال \(L=0,1,2,\dots,N\) حتى يتم تجاوز العتبة لأول مرة عند \(N=168\). لذلك، وبالنسبة إلى الكود كما هو مكتوب فعلًا، يكون الزمن الكلي \(O(N^3)\) والذاكرة القصوى \(O(N)\). ومع صغر قيمة الجواب النهائية يبقى هذا الحل المباشر سريعًا جدًا.