Each word in the given list is converted into a word value by replacing every letter with its alphabetical position and adding the results. Thus \(A=1\), \(B=2\), ..., \(Z=26\), and a word \(w\) receives the value
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
A word is called a triangle word when its value is a triangular number, that is, one of the numbers
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
The task is to count how many words in the supplied list satisfy \(V(w)=T_n\) for some \(n\).
The implementations do not test each word value with a separate quadratic check. Instead, they build the finite set of all triangular numbers that could possibly occur, and then reduce the problem to repeated set membership.
If a word is written as \(w=c_1c_2\cdots c_\ell\), then its value is simply
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
This is the only numerical object attached to a word. Once \(V(w)\) is known, the original ordering of the letters no longer matters for the triangle-word test.
Let
$$M=\max_w V(w)$$
be the largest word value appearing in the input. Any triangle word must have value in the set
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$$
This works because the triangular numbers form a strictly increasing sequence. Once \(T_n\gt M\), every later triangular number is even larger, so it cannot match any word value from the file. The problem therefore collapses to a finite lookup problem.
The bound is small: the number of relevant triangular numbers is the largest \(n\) with \(n(n+1)/2 \le M\), which is \(O(\sqrt{M})\).
The standard example is the word "SKY". Its letters contribute
$$S=19,\qquad K=11,\qquad Y=25,$$
so
$$V(\text{SKY})=19+11+25=55.$$
Now compare this with the triangular sequence:
$$1,3,6,10,15,21,28,36,45,55,\dots$$
Since \(55=T_{10}\), "SKY" is a triangle word. The same logic applies to every other word in the list: compute its value once, then ask whether that value belongs to \(\mathcal{T}(M)\).
If the input words are \(w_1,w_2,\dots,w_N\), then the answer is
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}},$$
where the indicator is 1 exactly when the word value is triangular. There is no deeper recurrence or search tree hidden here: the mathematical core is to replace repeated triangular-number tests by one precomputed finite set.
The input is a single comma-separated line whose words are enclosed in double quotes. The implementations scan the text character by character, switch an "inside quotes" state on and off when they meet a quote, and collect characters only while that state is active. Every time a closing quote is reached, one complete word is stored.
After parsing, the implementation evaluates each word by summing the contributions of its uppercase letters from \(1\) through \(26\). During that same pass it records the maximum word value \(M\). This maximum is the key invariant for the rest of the algorithm: no triangular number above \(M\) can ever be useful.
Next, the implementation generates
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
until the values exceed \(M\), storing every valid triangular number in a hash-based set. A second pass over the parsed words recomputes each word value and checks whether it belongs to that set. The total number of successful lookups is the required answer.
The C++, Python, and Java implementations also include small sanity checks around this logic, such as verifying that "SKY" has value \(55\) and that \(55\) appears in the triangular set while \(54\) does not.
Let \(N\) be the number of words, let \(C=\sum_{i=1}^{N}|w_i|\) be the total number of letters across all words, and let \(K=\max\{n:T_n\le M\}\). Parsing the input costs \(O(C)\). The first pass that computes word values and finds \(M\) also costs \(O(C)\). Building the triangular set costs \(O(K)=O(\sqrt{M})\). The second pass that counts triangle words is again \(O(C)\).
So the overall running time is
$$O(C+\sqrt{M}),$$
with the linear scans over the letters dominating in practice. The implementations store the parsed words explicitly, so the space usage is \(O(C+\sqrt{M})\): \(O(C)\) for the words themselves and \(O(\sqrt{M})\) for the set of triangular numbers up to the maximum word value.
Jedes Wort der gegebenen Liste wird in einen Wortwert umgewandelt, indem man jede Letter durch ihre alphabetische Position ersetzt und alles addiert. Also gilt \(A=1\), \(B=2\), ..., \(Z=26\), und fur ein Wort \(w\) ist
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
Ein Wort heiBt Dreieckswort, wenn sein Wert eine Dreieckszahl ist, also eine Zahl der Form
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
Gesucht ist die Anzahl der Worter aus der Liste, fur die \(V(w)=T_n\) fur ein geeignetes \(n\) gilt.
Die Implementierungen prufen nicht fur jedes Wort getrennt mit einer quadratischen Gleichung, ob der Wert dreieckig ist. Stattdessen bestimmen sie zuerst alle Dreieckszahlen, die uberhaupt vorkommen konnen, und reduzieren das Problem dann auf Mengenmitgliedschaft.
Ist ein Wort als \(w=c_1c_2\cdots c_\ell\) geschrieben, dann gilt
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
Das ist das zentrale mathematische Objekt des Problems. Sobald \(V(w)\) feststeht, spielt die Reihenfolge der Buchstaben fur den Dreieckstest keine Rolle mehr.
Sei
$$M=\max_w V(w)$$
der groBte Wortwert der gesamten Eingabe. Dann kann ein Dreieckswort nur einen Wert aus
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}$$
besitzen. Die Folge der Dreieckszahlen ist streng wachsend. Sobald also \(T_n\gt M\) erreicht ist, ist auch jede spatere Dreieckszahl zu groB. Genau diese Monotonie ist die Invariante, auf der die Vorberechnung beruht.
Die Anzahl der benotigten Dreieckszahlen ist klein: Gesucht ist nur das groBte \(n\) mit \(n(n+1)/2 \le M\), also eine GroBe von Ordnung \(O(\sqrt{M})\).
Fur das bekannte Beispiel "SKY" gilt
$$S=19,\qquad K=11,\qquad Y=25,$$
also
$$V(\text{SKY})=19+11+25=55.$$
Vergleicht man mit den ersten Dreieckszahlen
$$1,3,6,10,15,21,28,36,45,55,\dots,$$
dann sieht man sofort \(55=T_{10}\). Daher ist "SKY" ein Dreieckswort. Das ist genau das Muster fur alle Worter: Wert berechnen, dann Mitgliedschaft in \(\mathcal{T}(M)\) testen.
Sind die Eingabeworter \(w_1,w_2,\dots,w_N\), dann lautet die gesuchte Anzahl
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}.$$
Der mathematische Kern ist also kein kompliziertes Suchverfahren, sondern die Beobachtung, dass alle moglichen Zielwerte vorher bekannt und endlich sind.
Die Eingabe ist eine einzige kommaseparierte Zeichenkette mit in Anfuhrungszeichen eingeschlossenen Wortern. Die Implementierung lauft Zeichen fur Zeichen durch den Text, schaltet bei jedem Anfuhrungszeichen einen "innerhalb von Quotes"-Zustand um und sammelt nur in dieser Phase Buchstaben. Beim schlieBenden Quote wird das vollstandige Wort gespeichert.
Nach dem Parsen werden die Wortwerte berechnet, indem nur GroBbuchstaben von \(A\) bis \(Z\) auf \(1\) bis \(26\) abgebildet und addiert werden. Gleichzeitig wird der maximale Wortwert \(M\) mitgefuhrt. Diese Obergrenze ist die entscheidende Invariante fur den Rest der Losung.
AnschlieBend erzeugt die Implementierung die Folge
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
bis der aktuelle Wert \(M\) ubersteigt, und speichert alle zulassigen Werte in einer hashbasierten Menge. Danach folgt ein zweiter Durchgang uber die bereits eingelesenen Worter. Fur jedes Wort wird der Wert erneut berechnet und in der Menge nachgeschlagen. Die Anzahl erfolgreicher Nachschlage ist die gesuchte Antwort.
Zusatzlich enthalten die C++-, Python- und Java-Implementierungen kleine Konsistenztests, etwa dass "SKY" den Wert \(55\) hat und dass \(55\) zur vorberechneten Dreiecksmenge gehort, \(54\) aber nicht.
Seien \(N\) die Anzahl der Worter, \(C=\sum_{i=1}^{N}|w_i|\) die Gesamtzahl aller Buchstaben und \(K=\max\{n:T_n\le M\}\). Das Parsen kostet \(O(C)\). Der erste Durchgang fur Wortwerte und Maximum kostet ebenfalls \(O(C)\). Das Erzeugen der Dreieckszahlen kostet \(O(K)=O(\sqrt{M})\). Der zweite Durchgang fur die eigentliche Zahlung kostet nochmals \(O(C)\).
Damit ergibt sich insgesamt
$$O(C+\sqrt{M}).$$
Der Speicherverbrauch ist \(O(C+\sqrt{M})\), weil die Implementierungen die gelesenen Worter explizit speichern und zusatzlich nur die Menge der Dreieckszahlen bis zur maximalen Wortsumme halten.
Verilen listedeki her kelime, harflerinin alfabetik konumlari toplanarak bir kelime degerine donusturulur. Yani \(A=1\), \(B=2\), ..., \(Z=26\) ve bir \(w\) kelimesi icin
$$V(w)=\sum_{c \in w}\operatorname{pos}(c)$$
olur. Bir kelime degeri bir ucgen sayiya esitse o kelimeye ucgen kelime denir. Ucgen sayilar
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1)$$
biçimindedir. Amac, listedeki kac kelimenin bu kosulu sagladigini saymaktir.
Uygulamalar her kelime icin ayri ayri bir diskriminant testi yapmiyor. Bunun yerine once ortaya cikabilecek tum ucgen sayilari sonlu bir kume olarak hazirliyor, sonra problemi basit bir uyelik testine indiriyor.
Bir kelime \(w=c_1c_2\cdots c_\ell\) ise
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
Problemdeki temel sayisal nesne budur. \(V(w)\) hesaplandiktan sonra harflerin sirasi artik onemli degildir; ucgen kelime olup olmamayi belirleyen sey yalnizca bu toplamdir.
Girdideki en buyuk kelime degerini
$$M=\max_w V(w)$$
ile gosterebiliriz. O zaman aradigimiz tum uygun degerler su sonlu kume icindedir:
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$$
Buradaki ana invariant sudur: ucgen sayilar strikt artandir. Dolayisiyla bir kez \(T_n\gt M\) oldugunda, daha sonraki hicbir ucgen sayi herhangi bir kelime degerine esit olamaz. Bu gozlem, problemi acik bir arama uzayindan sonlu bir tabloya indirir.
Ayrica gereken ucgen sayi adedi de kucuktur; \(n(n+1)/2 \le M\) kosulunu saglayan en buyuk \(n\), buyukluk olarak \(O(\sqrt{M})\) mertebesindedir.
Problemin klasik ornegi "SKY" kelimesidir. Harf degerleri
$$S=19,\qquad K=11,\qquad Y=25$$
oldugundan
$$V(\text{SKY})=19+11+25=55$$
elde edilir. Ucgen sayi dizisinin basi
$$1,3,6,10,15,21,28,36,45,55,\dots$$
oldugu icin \(55=T_{10}\) bulunur. Demek ki "SKY" bir ucgen kelimedir. Listedeki her kelime icin yapilan islem de aynidir: degeri hesapla, sonra \(\mathcal{T}(M)\) icinde olup olmadigina bak.
Girdi kelimeleri \(w_1,w_2,\dots,w_N\) olsun. O zaman cevap
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}$$
ifadesidir. Buradaki gostergede kosul saglaniyorsa 1, aksi halde 0 alinır. Dolayisiyla matematiksel oz, dogru sonlu hedef kumesini once olusturmaktir.
Girdi, cift tirnak icindeki kelimelerden olusan tek satirlik bir CSV dizgesidir. Uygulama metni karakter karakter gezer, bir cift tirnak gorunce "tirnak icindeyim" durumunu degistirir ve yalnizca bu durum aktifken karakter toplar. Kapanis tirnagina gelindiginde bir tam kelime elde edilmis olur ve listeye eklenir.
Ayrıştırma bittikten sonra her kelime icin \(A\) ile \(Z\) arasindaki buyuk harfler \(1\) ile \(26\) arasina cevrilir ve toplanir. Ayni gecis sirasinda en buyuk kelime degeri \(M\) de bulunur. Algoritmanin geri kalani bu ust sinira dayanir; \(M\)'den buyuk ucgen sayilarin hicbiri yararli olmayacaktir.
Daha sonra uygulama
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
dizisini \(M\)'yi gecene kadar uretir ve bu sayilari karmali bir kumede saklar. Son bir geciste her kelimenin degeri yeniden hesaplanir ve bu kumede aranir. Basarili arama sayisi dogrudan cevaptir.
C++, Python ve Java uygulamalari ayrica kucuk saglama adimlari da icerir; ornegin "SKY" icin degerin \(55\) oldugu ve \(55\)'in ucgenler kumesinde bulunup \(54\)'un bulunmadigi dogrulanir.
\(N\) kelime sayisi, \(C=\sum_{i=1}^{N}|w_i|\) tum kelimelerdeki toplam harf sayisi ve \(K=\max\{n:T_n\le M\}\) olsun. Ayrıştırma \(O(C)\), ilk deger ve maksimum bulma gecisi \(O(C)\), ucgen kumesini uretme asamasi \(O(K)=O(\sqrt{M})\), son sayma gecisi de yine \(O(C)\) zaman alir.
Toplam karmaşıklık
$$O(C+\sqrt{M})$$
olur. Bellek kullanimi \(O(C+\sqrt{M})\) seviyesindedir; cunku uygulamalar ayrıştırılmış kelimeleri tutar ve buna ek olarak yalnizca maksimum kelime degerine kadar olan ucgen sayilarin kumesini saklar.
Cada palabra de la lista se transforma en un valor de palabra al sustituir cada letra por su posicion alfabetica y sumar los resultados. Asi, \(A=1\), \(B=2\), ..., \(Z=26\), y para una palabra \(w\) se define
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
Una palabra es triangular cuando su valor coincide con un numero triangular, es decir, con un numero de la forma
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
El objetivo es contar cuantas palabras de la lista cumplen \(V(w)=T_n\) para algun \(n\).
Las implementaciones no aplican una prueba algebraica independiente a cada palabra. Primero construyen el conjunto finito de todos los numeros triangulares que pueden aparecer y luego convierten el resto del trabajo en consultas de pertenencia a un conjunto.
Si \(w=c_1c_2\cdots c_\ell\), entonces
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
Ese es el unico objeto numerico importante del problema. Una vez calculado \(V(w)\), el orden interno de las letras ya no influye en la prueba triangular.
Sea
$$M=\max_w V(w)$$
el mayor valor de palabra presente en la entrada. Entonces toda palabra triangular debe tener un valor dentro de
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$$
La razon es que la sucesion triangular crece estrictamente. En cuanto algun \(T_n\gt M\), todos los terminos posteriores tambien superan \(M\), de modo que ya no pueden coincidir con ningun valor de palabra del archivo. Esa monotonia es la invariante que justifica la precalculacion.
Ademas, el numero de triangulares relevantes es pequeno: basta llegar hasta el mayor \(n\) que satisface \(n(n+1)/2 \le M\), lo cual es \(O(\sqrt{M})\).
Para la palabra "SKY" se tiene
$$S=19,\qquad K=11,\qquad Y=25,$$
y por tanto
$$V(\text{SKY})=19+11+25=55.$$
La sucesion de numeros triangulares comienza
$$1,3,6,10,15,21,28,36,45,55,\dots,$$
asi que \(55=T_{10}\). Por eso "SKY" cuenta como palabra triangular. Todas las demas palabras se tratan del mismo modo: se calcula el valor y se pregunta si pertenece a \(\mathcal{T}(M)\).
Si las palabras son \(w_1,w_2,\dots,w_N\), la respuesta es
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}.$$
El problema no requiere una busqueda compleja; requiere identificar de antemano el conjunto correcto de objetivos posibles y contar cuantas palabras caen en el.
La entrada es una sola cadena CSV con palabras entre comillas dobles. La implementacion recorre el texto caracter por caracter, alterna un estado de "dentro de comillas" cada vez que encuentra una comilla y solo acumula letras mientras ese estado esta activo. Al llegar a una comilla de cierre, ya se ha completado una palabra.
Despues del analisis, cada palabra se evalua sumando las contribuciones de sus letras mayusculas entre \(A\) y \(Z\). En esa misma pasada tambien se calcula el maximo \(M\). Ese maximo controla toda la fase matematica siguiente, porque ningun triangular mayor que \(M\) puede volver a ser util.
Luego la implementacion genera
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
hasta que el valor sobrepasa \(M\), y guarda todos los triangulares validos en un conjunto basado en hash. En una segunda pasada por la lista de palabras vuelve a calcular cada valor y comprueba si esta en ese conjunto. El numero de aciertos es la respuesta pedida.
Las versiones en C++, Python y Java tambien incorporan comprobaciones pequenas de consistencia, por ejemplo verificar que "SKY" vale \(55\) y que \(55\) esta en el conjunto triangular mientras que \(54\) no lo esta.
Sean \(N\) el numero de palabras, \(C=\sum_{i=1}^{N}|w_i|\) el numero total de letras y \(K=\max\{n:T_n\le M\}\). El analisis del archivo cuesta \(O(C)\). La primera pasada para calcular valores y hallar \(M\) cuesta \(O(C)\). La construccion del conjunto triangular cuesta \(O(K)=O(\sqrt{M})\). La segunda pasada para contar palabras triangulares cuesta otra vez \(O(C)\).
En conjunto, el tiempo total es
$$O(C+\sqrt{M}).$$
El espacio usado es \(O(C+\sqrt{M})\), porque las implementaciones almacenan explicitamente las palabras ya analizadas y, ademas, el conjunto de numeros triangulares hasta el maximo valor observado.
题目把每个单词都映射成一个单词值：把字母替换为它们在字母表中的位置并求和。也就是 \(A=1\), \(B=2\), ..., \(Z=26\)，对任意单词 \(w\) 定义
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
如果一个单词的值恰好等于某个三角数，那么它就是一个三角单词。三角数满足
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
题目的目标就是统计给定单词表中一共有多少个单词满足 \(V(w)=T_n\)。
这道题真正的关键不是对每个单词单独做复杂判定，而是先找出“所有可能出现的三角数”。实现采用的正是这个思路：先根据输入中出现的最大单词值构造一个有限三角数集合，然后把整个问题化为集合成员测试。
如果单词写成 \(w=c_1c_2\cdots c_\ell\)，那么
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
这就是本题唯一重要的数值对象。只要 \(V(w)\) 已经算出来，字母原本的排列顺序就不再重要，因为是否为三角单词完全由这个总和决定。
设输入中最大的单词值为
$$M=\max_w V(w).$$
那么所有可能成为答案的值都必须落在集合
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}$$
里。理由很直接：三角数序列严格递增。一旦某个 \(T_n\gt M\)，后面的 \(T_{n+1},T_{n+2},\dots\) 只会更大，因此不可能再与任何输入单词的值相等。这个“超过最大值以后就可以停止”的单调性，就是代码预计算阶段依赖的不变量。
而且相关的三角数个数很少。只需要找到最大的 \(n\) 使得 \(n(n+1)/2 \le M\)，数量级就是 \(O(\sqrt{M})\)。
经典例子是单词 "SKY"。它的字母值分别为
$$S=19,\qquad K=11,\qquad Y=25,$$
所以
$$V(\text{SKY})=19+11+25=55.$$
而三角数序列开头是
$$1,3,6,10,15,21,28,36,45,55,\dots$$
因此 \(55=T_{10}\)，所以 "SKY" 就是三角单词。对整个文件中的每一个单词，数学判断都完全一样：先求 \(V(w)\)，再判断它是否属于 \(\mathcal{T}(M)\)。
如果输入单词依次为 \(w_1,w_2,\dots,w_N\)，那么答案可以写成
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}.$$
这里的指示函数在条件成立时取 1，否则取 0。也就是说，本题并不需要深层递推或搜索树，真正的数学整理工作是先把所有可能命中的三角值一次性准备好。
输入是一整行被双引号包围、用逗号分隔的单词。实现逐字符扫描文本，每遇到一个双引号就切换一次“当前是否在引号内”的状态，只在引号内收集字符；当遇到结束引号时，就得到一个完整单词并存入列表。
解析结束后，程序对每个单词计算字母和。实现只把 \(A\) 到 \(Z\) 的大写字母映射到 \(1\) 到 \(26\)。在同一次遍历中，还会维护全局最大单词值 \(M\)。这个上界控制了后续全部预处理，因为任何大于 \(M\) 的三角数都已经没有意义。
接着，程序生成序列
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
直到当前值第一次超过 \(M\)。所有不超过 \(M\) 的三角数都被放入一个基于哈希的集合中。随后程序再次遍历所有单词，重新计算每个单词值，并查询它是否在该集合中。命中的次数就是最终答案。
C++、Python 和 Java 实现还加了几个小型自检，例如确认 "SKY" 的值是 \(55\)，并确认当上界至少为 100 时，集合包含 \(55\) 而不包含 \(54\)。
设 \(N\) 是单词个数，\(C=\sum_{i=1}^{N}|w_i|\) 是所有单词总字符数，\(K=\max\{n:T_n\le M\}\)。解析文本需要 \(O(C)\)。第一次遍历单词来计算值并求最大值需要 \(O(C)\)。生成三角数集合需要 \(O(K)=O(\sqrt{M})\)。第二次遍历做统计又需要 \(O(C)\)。
因此总时间复杂度为
$$O(C+\sqrt{M}).$$
空间复杂度为 \(O(C+\sqrt{M})\)：实现会显式保存解析后的单词列表，这部分是 \(O(C)\)；另外还要保存不超过最大单词值的三角数集合，这部分是 \(O(\sqrt{M})\)。
Каждое слово из списка переводится в значение слова: каждой букве ставится в соответствие ее номер в алфавите, после чего эти числа складываются. То есть \(A=1\), \(B=2\), ..., \(Z=26\), а для слова \(w\) определяется
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
Слово называется треугольным, если его значение является треугольным числом, то есть числом вида
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
Нужно посчитать, сколько слов из входного набора удовлетворяют условию \(V(w)=T_n\).
Реализации не выполняют для каждого слова отдельную алгебраическую проверку. Вместо этого они сначала строят конечное множество всех треугольных чисел, которые вообще могут понадобиться, а затем сводят задачу к повторяющейся проверке принадлежности значений этому множеству.
Если записать слово как \(w=c_1c_2\cdots c_\ell\), то
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
Это и есть главный числовой объект задачи. После вычисления \(V(w)\) порядок букв уже не влияет на то, будет ли слово треугольным: важна только сумма.
Обозначим через
$$M=\max_w V(w)$$
максимальное значение слова во всем входе. Тогда любое подходящее слово должно иметь значение из множества
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$$
Причина в том, что последовательность треугольных чисел строго возрастает. Как только очередное \(T_n\gt M\), все следующие треугольные числа тоже будут больше \(M\), а значит, уже не смогут совпасть ни с одним значением слова из файла. Эта монотонность и является ключевым инвариантом предвычисления.
Количество нужных треугольных чисел невелико: требуется лишь наибольшее \(n\), удовлетворяющее \(n(n+1)/2 \le M\), что дает порядок \(O(\sqrt{M})\).
Для слова "SKY" имеем
$$S=19,\qquad K=11,\qquad Y=25,$$
следовательно,
$$V(\text{SKY})=19+11+25=55.$$
Начало последовательности треугольных чисел выглядит так:
$$1,3,6,10,15,21,28,36,45,55,\dots$$
Поэтому \(55=T_{10}\), и слово "SKY" действительно является треугольным. Ровно та же схема применяется к каждому слову из входа: сначала считается \(V(w)\), затем проверяется принадлежность множеству \(\mathcal{T}(M)\).
Если входные слова обозначить \(w_1,w_2,\dots,w_N\), то ответ равен
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}.$$
Здесь индикатор равен 1, когда значение слова треугольное, и 0 в противном случае. Таким образом, математическая суть задачи состоит в правильном построении конечного набора целевых значений.
Во входе содержится одна CSV-строка, где слова заключены в двойные кавычки. Реализация проходит по тексту посимвольно, переключает состояние "внутри кавычек" при встрече кавычки и накапливает символы только в этом состоянии. Когда встречается закрывающая кавычка, собранное содержимое добавляется как очередное слово.
После разбора каждое слово оценивается суммой букв от \(A\) до \(Z\), отображенных в числа от \(1\) до \(26\). В том же проходе вычисляется максимальное значение \(M\). Эта граница управляет всем следующим этапом: треугольные числа больше \(M\) больше никогда не понадобятся.
Далее программа генерирует последовательность
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
пока текущий член не превысит \(M\), и сохраняет все допустимые треугольные числа в хеш-множестве. Затем выполняется второй проход по словам: для каждого слова снова вычисляется значение и проверяется наличие этого значения в множестве. Число успешных проверок и есть ответ.
Во всех трех реализациях, на C++, Python и Java, добавлены также небольшие контрольные проверки: например, подтверждается, что "SKY" дает \(55\), а число \(55\) входит в множество треугольных значений, тогда как \(54\) не входит.
Пусть \(N\) - количество слов, \(C=\sum_{i=1}^{N}|w_i|\) - суммарное число букв во всех словах, а \(K=\max\{n:T_n\le M\}\). Разбор входа требует \(O(C)\). Первый проход для вычисления значений и нахождения \(M\) стоит \(O(C)\). Построение множества треугольных чисел стоит \(O(K)=O(\sqrt{M})\). Второй проход для подсчета снова требует \(O(C)\).
Итоговая временная сложность равна
$$O(C+\sqrt{M}).$$
Память составляет \(O(C+\sqrt{M})\), поскольку реализации явно хранят разобранные слова и дополнительно поддерживают множество треугольных чисел до максимального значения слова.
تقوم المسالة بتحويل كل كلمة في القائمة الى قيمة كلمة عن طريق استبدال كل حرف بموضعه في الابجدية ثم جمع القيم. اي ان \(A=1\)، و\(B=2\)، ...، و\(Z=26\)، ولذلك تكون قيمة الكلمة \(w\) هي
$$V(w)=\sum_{c \in w}\operatorname{pos}(c).$$
وتسمى الكلمة كلمة مثلثية اذا كانت قيمتها عددا مثلثيا، اي عددا من الشكل
$$T_n=\frac{n(n+1)}{2}\qquad(n \ge 1).$$
المطلوب هو عد الكلمات في القائمة التي تحقق \(V(w)=T_n\) لبعض \(n\).
التنفيذ لا يفحص كل كلمة على حدة باختبار جبري مستقل، بل يبني اولا المجموعة المحدودة من جميع الاعداد المثلثية التي يمكن ان تظهر فعليا، ثم يحول المسالة كلها الى اختبار انتماء قيمة الكلمة الى تلك المجموعة.
اذا كتبنا الكلمة على الصورة \(w=c_1c_2\cdots c_\ell\)، فان
$$V(w)=\operatorname{pos}(c_1)+\operatorname{pos}(c_2)+\cdots+\operatorname{pos}(c_\ell).$$
هذا هو الكائن العددي المركزي في المسالة. بعد حساب \(V(w)\) لا يعود ترتيب الحروف مهما بالنسبة لفحص كون الكلمة مثلثية؛ المهم فقط هو مجموع القيم.
لنرمز باكبر قيمة كلمة في الادخال الى
$$M=\max_w V(w).$$
عندئذ لا بد ان تكون كل قيمة ناجحة ضمن المجموعة
$$\mathcal{T}(M)=\left\{T_n=\frac{n(n+1)}{2}: T_n \le M\right\}.$$
والسبب هو ان متتالية الاعداد المثلثية متزايدة بازدياد صارم. فبمجرد ان يصبح \(T_n\gt M\)، ستكون جميع الحدود اللاحقة اكبر من \(M\) ايضا، وبالتالي يستحيل ان تطابق اي قيمة كلمة في الملف. هذا هو الثابت الاساسي الذي تعتمد عليه مرحلة التهيئة المسبقة.
كما ان عدد الحدود المطلوبة صغير؛ فنحن نحتاج فقط الى اكبر \(n\) يحقق \(n(n+1)/2 \le M\)، وهذا من رتبة \(O(\sqrt{M})\).
في المثال المعروف "SKY" تكون القيم
$$S=19,\qquad K=11,\qquad Y=25,$$
ومن ثم
$$V(\text{SKY})=19+11+25=55.$$
وبما ان بداية متتالية الاعداد المثلثية هي
$$1,3,6,10,15,21,28,36,45,55,\dots,$$
فنجد ان \(55=T_{10}\)، ولذلك تكون "SKY" كلمة مثلثية. وبالطريقة نفسها تماما تعالج كل كلمة اخرى: نحسب \(V(w)\) ثم نتحقق هل تنتمي الى \(\mathcal{T}(M)\) ام لا.
اذا كانت الكلمات في الادخال هي \(w_1,w_2,\dots,w_N\)، فالجواب يكتب على الصورة
$$\sum_{i=1}^{N}\mathbf{1}_{\{V(w_i)\in \mathcal{T}(M)\}}.$$
تساوي دالة المؤشر 1 عندما تكون قيمة الكلمة مثلثية و0 خلاف ذلك. لذلك فجوهر الحل الرياضي هو بناء مجموعة الاهداف الممكنة مرة واحدة ثم عد العناصر التي تقع فيها.
الادخال عبارة عن سطر CSV واحد، والكلمات فيه محاطة بعلامات اقتباس مزدوجة. يمر التنفيذ على النص حرفا حرفا، ويبدل حالة "داخل الاقتباس" كلما صادف علامة اقتباس، ولا يجمع الاحرف الا عندما تكون هذه الحالة مفعلة. وعند الوصول الى الاقتباس الختامي تكون كلمة كاملة قد اكتملت وتخزن في القائمة.
بعد التحليل، تحسب قيمة كل كلمة بجمع مساهمات الحروف الكبيرة من \(A\) الى \(Z\) بعد تحويلها الى الاعداد من \(1\) الى \(26\). وفي المرور نفسه يحفظ اكبر مقدار \(M\). هذا الحد الاعلى هو الذي يحكم ما بعده، لان اي عدد مثلثي اكبر من \(M\) لن يكون مفيدا بعد ذلك.
بعد ذلك يولد التنفيذ المتتالية
$$1,\ 3,\ 6,\ 10,\ \dots,\ \frac{n(n+1)}{2}$$
الى ان تتجاوز القيمة الحالية \(M\)، ويخزن جميع الحدود الصالحة في مجموعة مبنية على التجزئة. ثم يجري مرورا ثانيا على الكلمات المحللة، ويحسب قيمة كل كلمة من جديد، ويتحقق هل توجد في المجموعة ام لا. وعدد مرات النجاح هو الجواب المطلوب.
كما تتضمن تطبيقات C++ وPython وJava اختبارات تحقق صغيرة، مثل التاكد من ان قيمة "SKY" هي \(55\)، وان \(55\) موجودة في مجموعة الاعداد المثلثية بينما \(54\) غير موجودة فيها.
ليكن \(N\) عدد الكلمات، و\(C=\sum_{i=1}^{N}|w_i|\) مجموع اطوال الكلمات، و\(K=\max\{n:T_n\le M\}\). تحليل النص يكلف \(O(C)\). والمرور الاول لحساب القيم وايجاد \(M\) يكلف \(O(C)\). وبناء مجموعة الاعداد المثلثية يكلف \(O(K)=O(\sqrt{M})\). ثم يكلف المرور الثاني للعد \(O(C)\) مرة اخرى.
اذن زمن التنفيذ الكلي هو
$$O(C+\sqrt{M}).$$
اما الذاكرة فهي \(O(C+\sqrt{M})\)، لان التنفيذ يحتفظ بالكلمات المحللة صراحة، ويحتفظ ايضا بمجموعة الاعداد المثلثية حتى اكبر قيمة كلمة موجودة.