4. Žiarivý zádrhel vzorové riešenie

6 3 11

1 4 6

5 2 10

-1

Hrubá sila

Najjednoduchšia vec, ktorá sa dá spraviť, je postupne vyskúšať sčítať všetky \(k\)-tice čísel od \(1\) po \(n\), až kým nenarazíme na niektorú so súčtom \(s\) a tú vypísať. V Pythone sa takéto riešenie hrubou silou dá veľmi jednoducho naprogramovať pomocou knižnice itertools.

from itertools import combinations

n, k, s = map(int, input().split())

for k_tica in combinations(range(1, n + 1), k):
    if sum(k_tica) == s:
        print(' '.join(map(str, k_tica)))
        break
else:
    # else sa za for-cyklom vykoná vtedy, ak cyklus dobehne do konca
    # bez prerušenia break-om
    print(-1)

V najhoršom prípade prejdeme všetký \(k\)-tice, ktorých je \({n \choose k}\) a každú spracujeme v čase \(O(k)\). Časovú zložitosť by sme mohli voľne zhora ohraničiť ako \(O(k \cdot n^{n/2})\) alebo ako \(O(k \cdot 2^n)\) (ak zhora ohraničíme kombinačné číslo veľkosťou súčtu \(n\)-tého riadku Pascalovho trojuholníka \({n \choose k} \leq 2^n\)).

Optimálne riešenie

Ako prvú vec si môžeme všimnúť, že úloha by sa nám výrazne zjednodušila, keby každý súčet mohol byť vybraný ako súvislý úsek čísel. Súčet takejto aritmetickej postupnosti vieme zrátať v konštantnom čase (pre súčet čísel \(1, 2, \dots n\) existuje známy vzorec \(\frac{n(n+1)}{2}\)) a takýchto úsekov je menej. Teda riešenie prechádzajúce všetky takéto postupnosti by malo výrazne lepšiu časovú zložitosť (\(O(n+k)\)). A nielen to, už zo súčtu by sme rovno vedeli povedať, ktoré čísla v tejto postupnosti budú.

Takáto postupnosť sa však nedá nájsť vždy. Napríklad pre vstup (\(n, k, s\)) 6 3 11 je riešenie 2 3 4 primálo a 3 4 5 priveľa. Možno ale existuje postupnosť čísel s takýmto súčtom, ktorá je skoro súvislá.

Na náš príklad sa vieme pozrieť aj takto: keď z 2 3 4 5 vynecháme najväčšie číslo, súčet zvyšku bude primalý. Ak však vezmeme to najmenšie, súčet zvyšku bude priveľký. Nevieme vynechať nejaké číslo v strede tak, aby nám to sedelo? Vieme, a dokonca takéto čislo naozaj vieme vynechať vždy. Vynechávaním postupne čísel \(2, 3, 4, 5\) sa nám zmenšuje súčet úseku a tento súčet dosiahne všetky hodnoty medzi \(3+4+5=12\) a \(2+3+4=9\).

Z postupnosti teda potrebujeme vynechať jedno číslo: (súčet postupnosti \(-~s\)).

Už len potrebujeme nájsť takúto postupnosť, z ktorej vieme jedno číslo vynechať a dostaneme súčet \(s\).

Označme si prvé číslo tejto postupnosti ako \(a\). Vieme, že táto postupnosť bude vyzerať ako \(a, a+1, \ldots a+k\). Chceme, aby súčet \(a + (a+1) + \ldots + (a+k-1) ~ \leq ~s\), a pritom \(a\) bolo čo najväčšie:

\[ a \cdot k + \left(0 + 1 + \ldots + (k-1)\right) \leq s \]

\[ a \leq \frac{\left(s - \left(0 + 1 + \ldots + \left(k-1\right)\right)\right)}{k}\]

Keďže chceme aby \(a\) bolo celé číslo, potrebujeme zaokrúhliť pravú stranu rovnice nadol a dostávame priamo vzorec na jeho výpočet. Zaokrúhlenie za nás bude robiť celočíselné delenie \(k\) na záver.

Zhrňme si teda riešenie. Najprv si vyrátame, ktorá súvislá postupnosť dĺžky \(k+1\) nás zaujíma. Z tejto postupnosti potom vynecháme jedno číslo tak aby súčet zvyšku bol presne \(s\) a postupnosť vypíšeme bez jedného čísla.

Časová zložitosť tohto algoritmu je \(O(k)\) – nájsť postupnosť \(k+1\) čísel vieme v konštantnom čase, rovnako aj nájdenie vhodného čísla na vynechanie. Musíme však vypísať \(k\) čísel.

Algoritmus sa dá implementovať s pamäťovou zložitosťou \(O(1)\). V Pythone sa však rýchlejšie vypisuje po celých riadkoch. Preto si najprv vytvoríme celú postupnosť a potom ju naraz vypíšeme – implementácia teda používa \(O(k)\) pamäte.

n, k, s = map(int, input().split())

# zratame si najvacsi a najmensi dosiahnutelny sucet
low = sum(range(1, k + 1))
high = sum(range(n - k + 1, n + 1))

if s < low or s > high:
    print(-1)
    exit(0)

# najmensie cislo, ktore chceme zobrat v suvislej postupnosti
# low = 1 + 2 + ... + k-1 + k, k vsak odratat nechceme
a = (s - low + k) // k

# sucet [a,a+1..a+k], teda k+1 cisel, z ktorych 1 chceme vynechat
b = (a * (k + 1)) + (k * (k + 1) // 2)

res = [x for x in range(a, a + k + 1) if s + x != b]

print (' '.join(map(str, res)))