Each input line gives a finite set of positive integers. A candidate set \(A\) is a special sum set when every pair of non-empty disjoint subsets \(B, C \subseteq A\) satisfies both
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
where \(S(X)=\sum_{x\in X}x\). The task is purely a verification problem: test every listed set, keep the ones that satisfy both rules exactly, and add the total \(\sum_{a\in A} a\) of each accepted set.
Write the set in increasing order as \(a_1 \lt a_2 \lt \cdots \lt a_n\). The implementations exploit two facts: the size comparison rule can be collapsed to a short prefix-versus-suffix test, while the equal-sum rule can be checked exactly by enumerating subsets and recording their sums.
The problem only cares about disjoint non-empty subsets. So the exact mathematical object being tested is the subset-sum map
$$\sigma(X)=\sum_{x\in X} x,$$
restricted to pairs \(B,C\) with \(B\cap C=\varnothing\), \(B\ne\varnothing\), and \(C\ne\varnothing\). One rule compares sums when the subset sizes differ, and the other forbids equal sums for any disjoint pair at all.
Define
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
If a disjoint pair has sizes \(m+1\) and \(m\), then the smallest possible sum of the larger subset is \(P_{m+1}\), and the largest possible sum of the smaller subset is \(Q_m\). Therefore the rule
$$|B| \gt |C| \implies S(B) \gt S(C)$$
is guaranteed once
$$P_{m+1} \gt Q_m \qquad \text{for every } m \text{ with } 2m+1 \le n.$$
This is enough because any subset with more than \(m+1\) elements has an even larger sum, and the restriction \(2m+1 \le n\) is exactly the condition that disjoint subsets of sizes \(m+1\) and \(m\) can exist at all. So a potentially huge family of comparisons collapses to a short list of inequalities on the sorted set.
For the second rule, each subset is encoded by a bitmask \(M \in \{1,\dots,2^n-1\}\). Its sum is
$$\sigma(M)=\sum_{i:\text{bit }i\text{ of }M\text{ is }1} a_{i+1}.$$
The exact condition checked by the implementations is
$$\sigma(M) \ne \sigma(N)\qquad \text{whenever } M \ne 0,\ N \ne 0,\ \text{and } M \mathbin{\&} N = 0.$$
That last bitwise condition is the disjointness test. It matters: equal sums coming from overlapping subsets are irrelevant here, so the implementation does not reject them. Only equal sums from disjoint subsets violate the definition.
The C++ implementation fills all subset sums incrementally. If \(r\) is the position of the least significant set bit of \(M\), and \(M'=M\setminus\{r\}\), then
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
This turns the table of all subset sums into a simple recurrence over masks. The Python and Java implementations compute the same mathematical quantity more directly, but the underlying object is identical: every non-empty subset gets a mask and a sum, and only disjoint masks are compared for collisions.
Take \(A=\{3,5,6,7\}\). The size rule only needs one inequality because \(n=4\):
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
So any disjoint 2-element subset already outweighs any 1-element subset, and positivity handles all larger size gaps automatically. The remaining task is to inspect disjoint subset sums. They are all different, so the set is accepted.
By contrast, \(A=\{2,3,4,5\}\) fails immediately because
$$P_2=2+3=5=Q_1,$$
so the size rule breaks. It also fails the equal-sum rule, since the disjoint subsets \(\{2,5\}\) and \(\{3,4\}\) both sum to \(7\). This illustrates why the implementations use a fast prefix-suffix filter first and the exact disjoint-mask check second.
The C++, Python, and Java implementations begin by sorting each candidate set. That produces the canonical order needed for the prefix and suffix inequalities. If any inequality \(P_{m+1} \gt Q_m\) fails, the set is rejected before any exhaustive subset work is done.
After the quick filter, the implementation enumerates every non-empty subset. One version precomputes a full array of subset sums using the least-significant-bit recurrence, another generates combinations and builds the corresponding mask, and another scans all masks directly. Despite those surface differences, all three are doing the same exact test: for every pair of subset masks already seen, reject if the masks are disjoint and their sums coincide.
If a candidate passes both tests, its element sum is added to a running total. The final output is the sum of the totals of all accepted special sum sets from the input list.
For a set of size \(n\), sorting costs \(O(n \log n)\). The prefix-suffix filter is linear if prefix sums are stored explicitly and at worst quadratic in the direct summation style, which is still negligible compared with the exhaustive phase.
The exact verification handles \(2^n-1\) non-empty subsets, so the space usage is \(O(2^n)\) for the stored subset sums or mask-sum pairs. In the worst case, many subset pairs may need to be compared, giving \(O(4^n)\) time for the exact test. That sounds large asymptotically, but the published instances are small enough that exhaustive verification is practical, especially because many candidates are rejected by the prefix-suffix rule before the expensive phase begins.
Jede Eingabezeile beschreibt eine endliche Menge positiver Ganzzahlen. Eine Kandidatenmenge \(A\) ist eine Spezialsummenmenge, wenn für jedes Paar nichtleerer disjunkter Teilmengen \(B, C \subseteq A\) beide Bedingungen gelten:
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
wobei \(S(X)=\sum_{x\in X}x\) ist. Gesucht ist also keine Konstruktion, sondern ein exakter Test: Jede gegebene Menge wird geprüft, und für jede gültige Menge wird ihre Gesamtsumme \(\sum_{a\in A} a\) zum Endergebnis addiert.
Sortiere die Menge als \(a_1 \lt a_2 \lt \cdots \lt a_n\). Die Implementierungen nutzen zwei zentrale Beobachtungen: Die Größenbedingung lässt sich auf wenige Präfix-Suffix-Ungleichungen reduzieren, und die Gleichheit von Teilmengensummen lässt sich mit vollständiger Teilmengenaufzählung exakt prüfen.
Das Problem betrachtet nur disjunkte, nichtleere Teilmengen. Das eigentliche mathematische Objekt ist also die Teilmengensummenfunktion
$$\sigma(X)=\sum_{x\in X} x,$$
eingeschränkt auf Paare \(B,C\) mit \(B\cap C=\varnothing\), \(B\ne\varnothing\) und \(C\ne\varnothing\). Eine Bedingung vergleicht Summen bei unterschiedlicher Mächtigkeit, die andere verbietet gleiche Summen für disjunkte Paare ganz allgemein.
Definiere
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
Hat ein disjunktes Paar die Größen \(m+1\) und \(m\), dann ist die kleinstmögliche Summe der größeren Teilmenge gleich \(P_{m+1}\), während die größtmögliche Summe der kleineren Teilmenge gleich \(Q_m\) ist. Deshalb ist
$$|B| \gt |C| \implies S(B) \gt S(C)$$
bereits gesichert, sobald
$$P_{m+1} \gt Q_m \qquad \text{für alle } m \text{ mit } 2m+1 \le n$$
gilt. Das genügt, weil jede Teilmenge mit mehr als \(m+1\) Elementen nur noch größere Summen haben kann, und die Bedingung \(2m+1 \le n\) genau ausdrückt, wann disjunkte Teilmengen dieser beiden Größen überhaupt existieren können.
Für die zweite Regel wird jede Teilmenge durch eine Bitmaske \(M \in \{1,\dots,2^n-1\}\) codiert. Ihre Summe ist
$$\sigma(M)=\sum_{i:\text{Bit }i\text{ von }M\text{ ist }1} a_{i+1}.$$
Geprüft wird exakt die Bedingung
$$\sigma(M) \ne \sigma(N)\qquad \text{wann immer } M \ne 0,\ N \ne 0,\ \text{und } M \mathbin{\&} N = 0.$$
Die bitweise Bedingung ist also der Disjunktheitstest. Das ist wichtig: Gleiche Summen überlappender Teilmengen sind hier nicht relevant. Nur gleiche Summen disjunkter Teilmengen verletzen die Definition.
Die C++-Implementierung berechnet alle Teilmengensummen inkrementell. Ist \(r\) die Position des niederwertigsten gesetzten Bits von \(M\) und \(M'=M\setminus\{r\}\), dann gilt
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
Damit wird die gesamte Tabelle aller Teilmengensummen zu einer einfachen Maskenrekurrenz. Die Python- und Java-Implementierungen berechnen dieselbe Größe direkter, aber das mathematische Objekt ist identisch: Jede nichtleere Teilmenge erhält eine Maske und eine Summe, und nur disjunkte Masken werden auf Kollisionen verglichen.
Betrachte \(A=\{3,5,6,7\}\). Für die Größenregel ist wegen \(n=4\) nur eine Ungleichung nötig:
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
Damit ist jede disjunkte 2-elementige Teilmenge automatisch größer als jede 1-elementige, und wegen der Positivität sind auch größere Größenabstände kein Problem. Danach bleiben nur noch die disjunkten Teilmengensummen zu prüfen. Sie sind alle verschieden, also wird die Menge akzeptiert.
Dagegen scheitert \(A=\{2,3,4,5\}\) sofort, denn
$$P_2=2+3=5=Q_1.$$
Außerdem verletzt die Menge auch die Summeneindeutigkeit, weil die disjunkten Teilmengen \(\{2,5\}\) und \(\{3,4\}\) beide die Summe \(7\) haben. Genau deshalb verwenden die Implementierungen zuerst den schnellen Präfix-Suffix-Filter und danach erst den exakten Maskentest.
Die C++-, Python- und Java-Implementierungen sortieren jede Kandidatenmenge zuerst. Dadurch entsteht die kanonische Reihenfolge für die Präfix- und Suffix-Ungleichungen. Scheitert eine dieser Ungleichungen, wird die Menge verworfen, bevor irgendeine vollständige Teilmengenaufzählung stattfindet.
Nach dem Vorfilter werden alle nichtleeren Teilmengen erzeugt. Eine Version füllt ein komplettes Array von Teilmengensummen mit der Rekurrenz über das niederwertigste gesetzte Bit, eine andere erzeugt Kombinationen und baut daraus die passende Maske, und eine weitere durchläuft die Bitmasken direkt. Trotz dieser Unterschiede testen alle drei dieselbe Bedingung: Sobald zwei bereits bekannte disjunkte Masken dieselbe Summe besitzen, ist die Menge ungültig.
Besteht eine Kandidatenmenge beide Tests, dann wird ihre Elementsumme zum laufenden Gesamtwert addiert. Die Ausgabe ist also die Summe der Gesamtsummen aller akzeptierten Spezialsummenmengen aus der Eingabe.
Für eine Menge der Größe \(n\) kostet das Sortieren \(O(n \log n)\). Der Präfix-Suffix-Filter ist linear, wenn Präfixsummen explizit gespeichert werden, und höchstens quadratisch bei direkter Summation. Gegenüber der vollständigen Teilmengenprüfung ist das nur ein kleiner Vorabaufwand.
Der exakte Test verarbeitet \(2^n-1\) nichtleere Teilmengen und benötigt daher \(O(2^n)\) Speicher für gespeicherte Summen oder Masken-Summen-Paare. Im Worst Case müssen viele Teilmengenpaare verglichen werden, also \(O(4^n)\) Zeit. Asymptotisch ist das groß, aber die veröffentlichten Instanzen sind klein genug für eine vollständige Verifikation, zumal viele Mengen schon am Präfix-Suffix-Filter scheitern.
Her girdi satırı sonlu bir pozitif tamsayı kümesi verir. Bir aday küme \(A\), boş olmayan ve ayrık her \(B, C \subseteq A\) alt küme çifti için şu iki koşulu sağlıyorsa özel toplam kümesi olur:
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
burada \(S(X)=\sum_{x\in X}x\). Dolayısıyla görev yeni bir küme üretmek değil, verilen her kümeyi tam olarak sınamaktır. Her iki koşulu da geçen her küme için \(\sum_{a\in A} a\) toplamı nihai sonuca eklenir.
Kümeyi artan sırada \(a_1 \lt a_2 \lt \cdots \lt a_n\) biçiminde yazalım. Uygulamalar iki temel gözlem kullanır: büyüklük karşılaştırması birkaç prefix-suffix eşitsizliğine indirgenebilir ve eşit alt küme toplamları da bütün alt kümeleri dolaşarak tam olarak denetlenebilir.
Soruda yalnızca ayrık ve boş olmayan alt kümeler önemlidir. Bu yüzden asıl incelenen nesne
$$\sigma(X)=\sum_{x\in X} x$$
alt küme toplam fonksiyonudur; ancak yalnızca \(B\cap C=\varnothing\), \(B\ne\varnothing\), \(C\ne\varnothing\) olan çiftler üzerinde değerlendirilir. Bir koşul alt küme boyutları farklı olduğunda toplamların da doğru yönde sıralanmasını ister, diğeri ise herhangi bir ayrık çift için eşit toplamı yasaklar.
Şimdi
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n$$
tanımlarını yapalım. Eğer ayrık iki alt kümenin boyutları \(m+1\) ve \(m\) ise, daha büyük olanın alabileceği en küçük toplam \(P_{m+1}\), daha küçük olanın alabileceği en büyük toplam ise \(Q_m\) olur. Bu yüzden
$$|B| \gt |C| \implies S(B) \gt S(C)$$
koşulu, şu eşitsizlikler sağlandığında otomatik olarak doğrudur:
$$P_{m+1} \gt Q_m \qquad \text{tüm } 2m+1 \le n \text{ durumları için.}$$
Bu yeterlidir; çünkü \(m+1\)'den daha büyük bir alt küme ancak daha da büyük toplam verir. Ayrıca \(2m+1 \le n\) sınırı, boyutları \(m+1\) ve \(m\) olan iki ayrık alt kümenin gerçekten var olabileceği durumların tam karşılığıdır.
İkinci koşul için her alt küme \(M \in \{1,\dots,2^n-1\}\) şeklinde bir bit maskesiyle temsil edilir. Bu maskenin toplamı
$$\sigma(M)=\sum_{i:\text{\(M\)'nin }i\text{. biti }1} a_{i+1}$$
olur. Uygulamaların tam olarak denetlediği şart şudur:
$$\sigma(M) \ne \sigma(N)\qquad \text{eğer } M \ne 0,\ N \ne 0,\ \text{ve } M \mathbin{\&} N = 0.$$
Buradaki bit düzeyindeki koşul ayrıklık testidir. Bu ayrıntı önemlidir: örtüşen alt kümelerin eşit toplam vermesi problem için başlı başına bir ihlal değildir. Yasak olan şey, ayrık iki alt kümenin aynı toplama sahip olmasıdır.
C++ uygulaması bütün alt küme toplamlarını artımlı olarak doldurur. Eğer \(r\), maskenin en düşük değerli 1 bitinin konumu ise ve \(M'=M\setminus\{r\}\) olarak yazılırsa
$$\sigma(M)=\sigma(M')+a_{r+1}$$
elde edilir. Böylece bütün alt küme toplamları basit bir maske yinelemesiyle hesaplanır. Python ve Java sürümleri aynı matematiksel niceliği daha doğrudan hesaplasa da temel nesne aynıdır: her boş olmayan alt kümenin bir maskesi ve toplamı vardır; yalnızca ayrık maskeler çakışma için karşılaştırılır.
\(A=\{3,5,6,7\}\) kümesini alalım. \(n=4\) olduğu için boyut kuralında yalnızca tek bir eşitsizlik gerekir:
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
Böylece her ayrık 2 elemanlı alt küme, her 1 elemanlı alt kümeden kesin olarak büyüktür; pozitiflik de daha büyük boyut farklarını otomatik olarak güvenceye alır. Geriye yalnızca ayrık alt kümelerin toplamlarını karşılaştırmak kalır. Bunların hepsi farklı olduğu için küme kabul edilir.
Buna karşılık \(A=\{2,3,4,5\}\) hemen elenir; çünkü
$$P_2=2+3=5=Q_1.$$
Ayrıca eşit toplam kuralı da bozulur; \(\{2,5\}\) ve \(\{3,4\}\) ayrık alt kümelerinin toplamı aynıdır ve \(7\)'dir. Bu örnek, neden önce hızlı prefix-suffix filtresinin, ardından tam ayrık-maske kontrolünün yapıldığını açıkça gösterir.
C++, Python ve Java uygulamaları her aday kümeyi önce sıralar. Bu sıralama, prefix ve suffix toplamlarını anlamlı kılan kanonik düzendir. Eğer \(P_{m+1} \gt Q_m\) testlerinden biri başarısız olursa, daha pahalı alt küme taramasına hiç geçilmeden küme reddedilir.
Ön filtreyi geçen bir kümede bütün boş olmayan alt kümeler üretilir. Bir sürüm en düşük 1 bit yinelemesiyle tam bir alt küme toplamları tablosu kurar, bir sürüm kombinasyonları üretip onlara karşılık gelen maskeleri oluşturur, başka bir sürüm ise tüm maskeleri doğrudan dolaşır. Yüzeyde farklı görünseler de üçü de aynı testi yapar: daha önce görülen iki ayrık maske aynı toplamı veriyorsa küme geçersizdir.
Bir aday küme her iki testten de geçerse, elemanlarının toplamı çalışan toplam değişkenine eklenir. Son çıktı, girdi içindeki bütün geçerli özel toplam kümelerinin toplamlarının toplamıdır.
Boyutu \(n\) olan bir küme için sıralama maliyeti \(O(n \log n)\) olur. Prefix-suffix filtresi prefix toplamları saklanırsa doğrusal, toplamlar doğrudan yeniden hesaplanırsa en fazla kareseldir. Bu bölüm, tam alt küme denetiminin yanında alt düzey bir maliyettir.
Tam doğrulama aşaması \(2^n-1\) adet boş olmayan alt kümeyi işler; dolayısıyla saklanan toplamlar veya maske-toplam çiftleri için alan maliyeti \(O(2^n)\) olur. En kötü durumda çok sayıda alt küme çifti karşılaştırılabileceğinden zaman maliyeti \(O(4^n)\) seviyesindedir. Asimptotik olarak büyük görünse de, yayımlanan örneklerde \(n\) küçük olduğu ve birçok aday hızlı filtrede elendiği için bu yöntem pratiktir.
Cada línea de la entrada describe un conjunto finito de enteros positivos. Un conjunto candidato \(A\) es un conjunto de suma especial si para todo par de subconjuntos no vacíos y disjuntos \(B, C \subseteq A\) se cumplen simultáneamente
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
donde \(S(X)=\sum_{x\in X}x\). La tarea no consiste en construir esos conjuntos, sino en verificarlos exactamente: se revisa cada candidato y, si pasa ambos criterios, se añade su suma total \(\sum_{a\in A} a\) al acumulado final.
Ordenamos el conjunto como \(a_1 \lt a_2 \lt \cdots \lt a_n\). Las implementaciones se apoyan en dos observaciones: la regla de tamaño puede reducirse a unas pocas desigualdades entre prefijos y sufijos, y la regla de sumas distintas puede comprobarse de forma exacta enumerando los subconjuntos.
El problema solo considera subconjuntos no vacíos y disjuntos. Por tanto, el objeto matemático central es la aplicación de suma
$$\sigma(X)=\sum_{x\in X} x,$$
restringida a pares \(B,C\) con \(B\cap C=\varnothing\), \(B\ne\varnothing\) y \(C\ne\varnothing\). Una condición compara las sumas cuando las cardinalidades son distintas; la otra prohíbe cualquier coincidencia de suma entre subconjuntos disjuntos.
Definimos
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
Si un par disjunto tiene tamaños \(m+1\) y \(m\), la suma mínima posible del subconjunto mayor es \(P_{m+1}\), mientras que la suma máxima posible del menor es \(Q_m\). Por eso la regla
$$|B| \gt |C| \implies S(B) \gt S(C)$$
queda garantizada siempre que
$$P_{m+1} \gt Q_m \qquad \text{para todo } m \text{ con } 2m+1 \le n.$$
Eso basta porque cualquier subconjunto con más de \(m+1\) elementos tiene una suma aún mayor, y la restricción \(2m+1 \le n\) es exactamente la condición para que dos subconjuntos disjuntos de tamaños \(m+1\) y \(m\) puedan existir.
Para la segunda regla, cada subconjunto se codifica con una máscara \(M \in \{1,\dots,2^n-1\}\). Su suma es
$$\sigma(M)=\sum_{i:\text{el bit }i\text{ de }M\text{ vale }1} a_{i+1}.$$
La condición exacta que comprueban las implementaciones es
$$\sigma(M) \ne \sigma(N)\qquad \text{siempre que } M \ne 0,\ N \ne 0,\ \text{y } M \mathbin{\&} N = 0.$$
Esa condición bit a bit es el test de disjunción. Es un detalle importante: si dos subconjuntos se solapan, que tengan la misma suma no viola por sí solo la definición. Solo se rechazan colisiones entre subconjuntos disjuntos.
La implementación en C++ rellena todas las sumas de subconjuntos de manera incremental. Si \(r\) es la posición del bit menos significativo encendido de \(M\), y \(M'=M\setminus\{r\}\), entonces
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
Así, toda la tabla de sumas se obtiene mediante una recurrencia simple sobre máscaras. Las implementaciones en Python y Java calculan la misma cantidad matemática de forma más directa, pero el objeto subyacente es el mismo: cada subconjunto no vacío recibe una máscara y una suma, y solo las máscaras disjuntas se comparan para detectar colisiones.
Tomemos \(A=\{3,5,6,7\}\). Como \(n=4\), la regla de tamaño solo necesita una desigualdad:
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
Con eso, cualquier subconjunto disjunto de 2 elementos supera automáticamente a cualquier subconjunto de 1 elemento, y la positividad cubre diferencias de tamaño aún mayores. Después solo queda revisar las sumas de subconjuntos disjuntos. Todas son distintas, por lo que el conjunto se acepta.
En cambio, \(A=\{2,3,4,5\}\) falla de inmediato porque
$$P_2=2+3=5=Q_1.$$
Además falla la regla de sumas distintas, ya que los subconjuntos disjuntos \(\{2,5\}\) y \(\{3,4\}\) tienen ambos suma \(7\). Este contraste muestra por qué las implementaciones aplican primero el filtro rápido de prefijos y sufijos y solo después la comprobación exacta con máscaras disjuntas.
Las implementaciones en C++, Python y Java empiezan ordenando cada conjunto candidato. Esa ordenación produce el orden canónico necesario para las desigualdades de prefijo y sufijo. Si alguna desigualdad \(P_{m+1} \gt Q_m\) falla, el conjunto se rechaza antes de entrar en la parte exhaustiva.
Tras superar el filtro rápido, la implementación genera todos los subconjuntos no vacíos. Una versión precalcula todas las sumas con la recurrencia del bit menos significativo, otra genera combinaciones y construye su máscara correspondiente, y otra recorre las máscaras de forma directa. Aunque cambie la mecánica superficial, el test matemático es el mismo en los tres casos: si dos máscaras disjuntas ya vistas tienen la misma suma, el conjunto no es válido.
Si un conjunto candidato supera ambas comprobaciones, se añade la suma de sus elementos al total acumulado. La salida final es la suma de las sumas de todos los conjuntos de suma especial aceptados.
Para un conjunto de tamaño \(n\), ordenar cuesta \(O(n \log n)\). El filtro de prefijos y sufijos es lineal si se almacenan prefijos y, como mucho, cuadrático si se recalculan las sumas directamente. En cualquier caso, ese coste es menor que el de la verificación exhaustiva.
La fase exacta maneja \(2^n-1\) subconjuntos no vacíos, por lo que el espacio es \(O(2^n)\) para las sumas almacenadas o los pares máscara-suma. En el peor caso pueden compararse muchos pares de subconjuntos, lo que da un tiempo \(O(4^n)\). Asintóticamente es grande, pero las instancias publicadas son lo bastante pequeñas para que la verificación completa sea práctica, sobre todo porque muchos candidatos se eliminan ya en el filtro inicial.
输入中的每一行都给出一个有限的正整数集合。若一个候选集合 \(A\) 对任意一对非空且互不相交的子集 \(B, C \subseteq A\) 都满足
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
其中 \(S(X)=\sum_{x\in X}x\)，那么 \(A\) 就是一个特殊和集合。题目的任务不是构造这种集合，而是逐个验证给出的候选集合；只要某个集合同时通过这两条规则，就把它自身元素和 \(\sum_{a\in A} a\) 加入最终总和。
把集合按升序写成 \(a_1 \lt a_2 \lt \cdots \lt a_n\)。三种实现都围绕同一个数学结构展开：第一条规则可以压缩成很短的一组前缀和与后缀和不等式，第二条规则则通过枚举全部子集并比较它们的和来做精确验证。
题目只关心非空且互不相交的子集对，因此核心对象是子集求和映射
$$\sigma(X)=\sum_{x\in X} x,$$
但只在满足 \(B\cap C=\varnothing\)、\(B\ne\varnothing\)、\(C\ne\varnothing\) 的成对子集上使用。第一条规则要求“元素个数更多的子集，其元素和一定更大”；第二条规则要求“任意两个互不相交的非空子集，元素和都不能相等”。这两条合在一起，才是特殊和集合的完整定义。
定义
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
若一对互不相交子集的大小分别为 \(m+1\) 和 \(m\)，那么较大子集可能取得的最小和就是 \(P_{m+1}\)，较小子集可能取得的最大和就是 \(Q_m\)。因此，只要对所有满足 \(2m+1 \le n\) 的 \(m\) 都有
$$P_{m+1} \gt Q_m,$$
就已经足以推出
$$|B| \gt |C| \implies S(B) \gt S(C).$$
原因很直接：如果一个子集的元素个数比 \(m+1\) 还多，它的和只会更大；而条件 \(2m+1 \le n\) 正好保证大小为 \(m+1\) 与 \(m\) 的两个子集确实有可能互不相交。于是本来需要比较的大量子集对，被压缩成排序后若干个固定的不等式。
第二条规则需要真正遍历子集。把每个非空子集编码成一个位掩码 \(M \in \{1,\dots,2^n-1\}\)。对应的子集和写成
$$\sigma(M)=\sum_{i:\text{\(M\) 的第 }i\text{ 位为 }1} a_{i+1}.$$
实现中真正检查的是下面这条精确条件：
$$\sigma(M) \ne \sigma(N)\qquad \text{只要 } M \ne 0,\ N \ne 0,\ \text{且 } M \mathbin{\&} N = 0.$$
这里 \(M \mathbin{\&} N = 0\) 就表示两个子集没有公共元素，也就是互不相交。这个细节非常关键。题目并不要求所有子集和两两不同；如果两个子集有重叠，它们就不属于题目禁止的情形。被排除的，只是互不相交子集之间的等和碰撞。
C++ 实现没有为每个掩码都重新求和，而是利用最低位的 1 来递推。如果 \(r\) 是掩码 \(M\) 中最低有效 1 位的位置，且 \(M'=M\setminus\{r\}\)，那么
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
这样就能把全部子集和填成一张递推表。Python 与 Java 版本在表面写法上更直接，但数学对象完全一样：每个非空子集都有一个掩码和一个子集和，然后只在掩码互斥时才检查是否出现相同和。
考虑 \(A=\{3,5,6,7\}\)。此时 \(n=4\)，所以大小规则只需要检查一条不等式：
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
这说明任意一个 2 元子集的和都必然大于任意一个 1 元子集的和；再加上所有元素都是正数，更大的大小差也不会出问题。于是剩下的工作只是在互不相交的子集之间寻找是否有等和碰撞。这个集合不会产生这样的碰撞，所以它是有效的特殊和集合。
再看 \(A=\{2,3,4,5\}\)。它立刻失败，因为
$$P_2=2+3=5=Q_1.$$
也就是说，最小的 2 元子集和并没有严格大于最大的 1 元子集和。此外，它还违反了第二条规则：互不相交的子集 \(\{2,5\}\) 与 \(\{3,4\}\) 的和都等于 \(7\)。这个对比恰好说明了程序结构为何是“先做快速的前缀-后缀筛选，再做精确的位掩码冲突检查”。
C++、Python 和 Java 实现都会先把每个候选集合排序。排序后的顺序就是前缀和与后缀和不等式所依赖的标准顺序。只要某个 \(P_{m+1} \gt Q_m\) 不成立，这个集合就会被直接淘汰，不再进入更昂贵的穷举阶段。
通过快速筛选后，程序会枚举全部非空子集。一个实现先用最低位递推预先填好整张子集和表，一个实现按组合生成子集并构造对应掩码，另一个实现直接遍历所有掩码。虽然写法不同，数学操作完全一致：只要发现两个已经生成的互斥掩码具有相同子集和，就立即判定该集合不合法。
若一个候选集合同时通过大小规则与等和规则，就把它所有元素的总和加入运行中的答案。最终输出就是所有合格特殊和集合的元素和之和。
对于大小为 \(n\) 的集合，排序代价是 \(O(n \log n)\)。前缀-后缀筛选在显式维护前缀和时是线性的，即使采用直接重复求和的写法，最多也只是二次时间，因此相比后面的穷举检查仍然是次要成本。
精确验证阶段要处理 \(2^n-1\) 个非空子集，所以存储子集和或“掩码-和”对的空间代价是 \(O(2^n)\)。最坏情况下，需要比较大量子集对，于是时间复杂度达到 \(O(4^n)\)。从渐近角度看这并不小，但题目给出的实例规模足够小，而且很多候选集合会在前缀-后缀筛选阶段就被提前排除，因此这种完全验证方法在这里是可行的。
Каждая строка входа задает конечное множество положительных целых чисел. Кандидат \(A\) является специальным множеством сумм, если для любой пары непустых непересекающихся подмножеств \(B, C \subseteq A\) одновременно выполняются условия
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
где \(S(X)=\sum_{x\in X}x\). Значит, задача не в построении множества, а в точной проверке каждого кандидата: если множество проходит оба условия, в ответ добавляется сумма его элементов \(\sum_{a\in A} a\).
Упорядочим элементы по возрастанию: \(a_1 \lt a_2 \lt \cdots \lt a_n\). Реализации опираются на две идеи: условие сравнения по мощности можно свести к короткому набору неравенств для префиксов и суффиксов, а условие уникальности суммы проверяется точным перебором подмножеств.
В задаче важны только непустые непересекающиеся подмножества. Поэтому центральный объект здесь - отображение суммы подмножества
$$\sigma(X)=\sum_{x\in X} x,$$
рассматриваемое только на парах \(B,C\) с \(B\cap C=\varnothing\), \(B\ne\varnothing\), \(C\ne\varnothing\). Первое правило требует, чтобы подмножество большей мощности обязательно имело большую сумму. Второе запрещает равенство сумм у любых двух непересекающихся непустых подмножеств.
Определим
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
Если размеры двух непересекающихся подмножеств равны \(m+1\) и \(m\), то минимально возможная сумма большего подмножества равна \(P_{m+1}\), а максимально возможная сумма меньшего подмножества равна \(Q_m\). Поэтому условие
$$|B| \gt |C| \implies S(B) \gt S(C)$$
гарантируется, если
$$P_{m+1} \gt Q_m \qquad \text{для всех } m \text{ таких, что } 2m+1 \le n.$$
Этого достаточно, потому что подмножество размера больше \(m+1\) может иметь только еще большую сумму, а ограничение \(2m+1 \le n\) в точности означает, что непересекающиеся подмножества размеров \(m+1\) и \(m\) вообще могут существовать одновременно.
Для второй части каждое непустое подмножество кодируется битовой маской \(M \in \{1,\dots,2^n-1\}\). Его сумма записывается как
$$\sigma(M)=\sum_{i:\text{бит }i\text{ в }M\text{ равен }1} a_{i+1}.$$
Проверяется точное условие
$$\sigma(M) \ne \sigma(N)\qquad \text{всякий раз, когда } M \ne 0,\ N \ne 0,\ \text{и } M \mathbin{\&} N = 0.$$
Последнее битовое равенство - это тест на непересечение. Здесь это принципиально важно: равные суммы у пересекающихся подмножеств сами по себе не запрещены. Нарушением считается только равенство сумм у непересекающихся пар.
В реализации на C++ все суммы подмножеств строятся инкрементально. Если \(r\) - позиция младшего установленного бита маски \(M\), а \(M'=M\setminus\{r\}\), то
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
Так вся таблица сумм получается по простой рекуррентной схеме на масках. Версии на Python и Java вычисляют ту же математическую величину более прямым способом, но объект остается тем же: у каждого непустого подмножества есть маска и сумма, а сравниваются только непересекающиеся маски.
Возьмем \(A=\{3,5,6,7\}\). При \(n=4\) для правила по мощности нужна всего одна проверка:
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
Значит, любое непересекающееся подмножество из 2 элементов гарантированно имеет сумму больше, чем любое подмножество из 1 элемента; положительность чисел автоматически покрывает и более сильный разрыв по мощности. После этого остается проверить только совпадения сумм у непересекающихся подмножеств. Их нет, поэтому множество принимается.
А вот \(A=\{2,3,4,5\}\) отбрасывается сразу, потому что
$$P_2=2+3=5=Q_1.$$
Кроме того, здесь нарушается и второе правило: непересекающиеся подмножества \(\{2,5\}\) и \(\{3,4\}\) имеют одинаковую сумму \(7\). Этот контраст хорошо показывает, почему сначала выгодно выполнить быстрый префиксно-суффиксный фильтр, а уже потом точную проверку по маскам.
Реализации на C++, Python и Java сначала сортируют каждый кандидат. Это дает канонический порядок, необходимый для префиксных и суффиксных неравенств. Если хотя бы одно неравенство \(P_{m+1} \gt Q_m\) не выполнено, множество отбрасывается до полного перебора подмножеств.
После быстрого фильтра генерируются все непустые подмножества. Одна реализация заранее строит массив всех сумм по рекуррентной формуле с младшим установленным битом, другая перебирает комбинации и собирает соответствующую маску, третья проходит по всем маскам напрямую. Несмотря на различия в форме записи, математическая проверка одна и та же: как только находятся две уже рассмотренные непересекающиеся маски с одинаковой суммой, кандидат признается невалидным.
Если кандидат проходит оба условия, сумма его элементов прибавляется к текущему ответу. Итоговый вывод - это сумма сумм всех принятых специальных множеств из входного списка.
Для множества размера \(n\) сортировка стоит \(O(n \log n)\). Префиксно-суффиксный фильтр работает за линейное время при явном хранении префиксных сумм и максимум за квадратичное время при прямом пересчете. На фоне полного перебора это малая часть затрат.
Точная проверка обрабатывает \(2^n-1\) непустых подмножеств, поэтому требует \(O(2^n)\) памяти для хранения сумм или пар вида «маска-сумма». В худшем случае приходится сравнивать много пар подмножеств, что дает \(O(4^n)\) времени. Асимптотически это много, но размеры опубликованных наборов достаточно малы, и к тому же многие кандидаты отсеиваются уже быстрым первым фильтром.
كل سطر في المُدخلات يصف مجموعة منتهية من الأعداد الصحيحة الموجبة. وتكون المجموعة المرشحة \(A\) مجموعة مجاميع خاصة إذا تحققت الشرطان التاليان لكل زوج من المجموعات الجزئية غير الفارغة والمنفصلة \(B, C \subseteq A\):
$$|B| \gt |C| \implies S(B) \gt S(C), \qquad S(B) \ne S(C),$$
حيث \(S(X)=\sum_{x\in X}x\). إذن المطلوب ليس إنشاء هذه المجموعات بل اختبار كل مجموعة معطاة بدقة، ثم إضافة مجموع عناصرها \(\sum_{a\in A} a\) إلى الجواب إذا اجتازت الشرطين معًا.
نرتب عناصر المجموعة تصاعديًا على الصورة \(a_1 \lt a_2 \lt \cdots \lt a_n\). وتستند الحلول إلى فكرتين أساسيتين: شرط المقارنة بحسب عدد العناصر يمكن اختزاله إلى مجموعة قصيرة من متراجحات البادئات والنهايات، وشرط تمايز المجاميع يمكن فحصه بدقة عبر تعداد جميع المجموعات الجزئية.
المسألة تهتم فقط بالأزواج غير الفارغة والمنفصلة من المجموعات الجزئية، لذلك الكائن الرياضي المركزي هو دالة مجموع المجموعة الجزئية
$$\sigma(X)=\sum_{x\in X} x,$$
ولكن مع قصر النظر على الأزواج التي تحقق \(B\cap C=\varnothing\) و \(B\ne\varnothing\) و \(C\ne\varnothing\). الشرط الأول يفرض أن المجموعة الجزئية ذات العناصر الأكثر يجب أن تملك مجموعًا أكبر. والشرط الثاني يمنع تساوي المجموعين لأي زوج منفصل غير فارغ.
نعرف
$$P_k=a_1+a_2+\cdots+a_k,\qquad Q_k=a_{n-k+1}+a_{n-k+2}+\cdots+a_n.$$
إذا كان لدينا زوج منفصل حجماه \(m+1\) و\(m\)، فإن أصغر مجموع ممكن للمجموعة الأكبر هو \(P_{m+1}\)، بينما أكبر مجموع ممكن للمجموعة الأصغر هو \(Q_m\). لذلك يصبح الشرط
$$|B| \gt |C| \implies S(B) \gt S(C)$$
مضمونًا متى تحقق
$$P_{m+1} \gt Q_m \qquad \forall m,\ 2m+1 \le n.$$
وهذا كافٍ لأن أي مجموعة جزئية تضم أكثر من \(m+1\) عنصرًا سيكون مجموعها أكبر بالضرورة، كما أن القيد \(2m+1 \le n\) هو الشرط الدقيق لوجود مجموعتين جزئيتين منفصلتين بالحجمين \(m+1\) و\(m\) أصلًا.
بالنسبة إلى الشرط الثاني، تُمثَّل كل مجموعة جزئية غير فارغة بقناع بتي \(M \in \{1,\dots,2^n-1\}\). ويكون مجموعها
$$\sigma(M)=\sum_{i:M_i=1} a_{i+1}.$$
والشرط الذي تفحصه التطبيقات حرفيًا هو
$$M \ne 0,\ N \ne 0,\ M \mathbin{\&} N = 0 \implies \sigma(M) \ne \sigma(N).$$
والشرط البتي الأخير هو اختبار الانفصال. وهذه نقطة مهمة جدًا: تساوي المجاميع بين مجموعتين جزئيتين متداخلتين لا يعد مخالفة في هذه المسألة. الممنوع فقط هو تساوي المجموعين بين مجموعتين جزئيتين منفصلتين.
تنشئ نسخة C++ جميع مجاميع المجموعات الجزئية تدريجيًا. فإذا كانت \(r\) موضع أقل بِت مضاء في القناع \(M\)، وكتبنا \(M'=M\setminus\{r\}\)، فإن
$$\sigma(M)=\sigma(M')+a_{r+1}.$$
وبهذا تتحول كل مجاميع المجموعات الجزئية إلى جدول بسيط يعتمد على علاقة عودية فوق الأقنعة. أما نسختا Python وJava فتحسبان الكمية الرياضية نفسها بطريقة مباشرة أكثر، لكن البنية الرياضية واحدة: كل مجموعة جزئية غير فارغة لها قناع ومجموع، ولا تُقارَن إلا الأقنعة المنفصلة بحثًا عن تصادمات في المجموع.
خذ \(A=\{3,5,6,7\}\). بما أن \(n=4\)، فإن شرط الحجم يحتاج إلى متراجحة واحدة فقط:
$$P_2=3+5=8,\qquad Q_1=7,\qquad 8 \gt 7.$$
وهذا يعني أن أي مجموعة جزئية منفصلة من عنصرين سيكون مجموعها أكبر حتمًا من أي مجموعة جزئية من عنصر واحد، كما أن إيجابية العناصر تجعل الفوارق الأكبر في الأحجام آمنة تلقائيًا. بعد ذلك يبقى فحص مجاميع المجموعات الجزئية المنفصلة. لا تظهر أي مساواة بينها، ولذلك تُقبل المجموعة.
أما \(A=\{2,3,4,5\}\) فتفشل مباشرة لأن
$$P_2=2+3=5=Q_1.$$
كما أنها تفشل أيضًا في شرط تمايز المجاميع، لأن المجموعتين الجزئيتين المنفصلتين \(\{2,5\}\) و\(\{3,4\}\) لهما المجموع نفسه وهو \(7\). وهذا المثال يوضح سبب بنية الحل: أولًا مرشح سريع يعتمد على البادئات والنهايات، ثم فحص دقيق قائم على الأقنعة المنفصلة.
تبدأ تطبيقات C++ وPython وJava بترتيب كل مجموعة مرشحة. هذا الترتيب هو الصورة القياسية المطلوبة لمقارنات البادئات والنهايات. فإذا فشلت أي متراجحة من الشكل \(P_{m+1} \gt Q_m\)، تُرفض المجموعة قبل الدخول في التعداد الكامل للمجموعات الجزئية.
بعد اجتياز المرشح الأول، تُولَّد جميع المجموعات الجزئية غير الفارغة. إحدى النسخ تبني جدولًا كاملًا للمجاميع باستعمال علاقة أقل بِت مضاء، ونسخة أخرى تولد التوافيق ثم تبني منها القناع الموافق، ونسخة ثالثة تمر على جميع الأقنعة مباشرة. ورغم هذا الاختلاف الشكلي، فالاختبار الرياضي واحد: إذا وُجد قناعان منفصلان سبق توليدهما ولهما المجموع نفسه، تُرفض المجموعة فورًا.
إذا اجتازت المجموعة المرشحة الاختبارين معًا، يُضاف مجموع عناصرها إلى المجموع التراكمي. والناتج النهائي هو مجموع مجاميع جميع المجموعات الخاصة المقبولة في القائمة.
لمجموعة حجمها \(n\)، تكون كلفة الترتيب \(O(n \log n)\). أما مرشح البادئات والنهايات فهو خطي إذا حُفظت المجاميع التراكمية صراحة، وفي أسوأ الأحوال تربيعي إذا أعيد حساب المجاميع مباشرة. وفي كلتا الحالتين يبقى هذا الجزء صغيرًا مقارنة بمرحلة الفحص الشامل.
مرحلة التحقق الدقيقة تتعامل مع \(2^n-1\) مجموعة جزئية غير فارغة، ولذلك تكون كلفة الذاكرة \(O(2^n)\) لتخزين المجاميع أو أزواج «القناع-المجموع». وفي أسوأ حالة قد نحتاج إلى مقارنة عدد كبير من أزواج المجموعات الجزئية، فتصل كلفة الزمن إلى \(O(4^n)\). هذا كبير من ناحية نظرية، لكن أحجام الحالات المنشورة صغيرة بما يكفي لجعل الفحص الكامل عمليًا، خاصة لأن كثيرًا من المرشحين يُستبعدون مبكرًا بواسطة المرشح الأول.