UŽDAVINIO "KAVOS ALGEBRA" SPRENDIMAS
(Koduotė utf-8)

Pirmiausia trumpai aptarkime sprendimą perrinkimu.

Pirmoji įžvalga - tai kad norint iš kavos pakelių <a1 in 1> ... <aN in 1> gauti kavą <b in c> reikės panaudoti lygiai c pakelių. Taigi reikia perrinkti visus pakelių derinius iš N po c, patikrinant, ar jų mišinys yra kava <b in c>. Sudarinėjant derinį galima iškart tikrinti, ar renkama suma neviršija b ir kai kuriuos rinkinius atmesti. (Efektyviau tai daryti išrikiavus pakelius mažėjimo tvarka.)

Sprendimo perrinkimu pavyzdys pateiktas faile "kavaperr.cpp". Toks sprendimas gali įveikti 50% uždavinio testų, su įvairiomis optimizacijomis - ir dar vieną kitą.

Kas blogai su perrinkimu? Ogi tai, kad galimų rinkinių skaičius auga labai greitai didėjant skaičiui N. Daugiausiai gali tekti išnagrinėti 100!/(50!*50!) variantų, tai apytiksliai lygu 10^29.

Kita vertus, mus domina tik mišiniai <x in y>, kuriems x <= b ir y <= c. Pagal uždavinio apribojimus, tokių skirtingų kavų negali būti daugiau negu MAXB*MAXC = 1000000. Tokį kiekį mišinių kompiuteris gali išnagrinėti per pakankamai trumpą laiką.

Vadinasi, spręsdami perrinkimu mes išnagrinėjame daugybę _vienodų_ derinių - tokių, kurių rezultatas yra tokia pati kava. Iš tiesų, mums pakanka žinoti vieną būdą, kaip gauti kavą <x in y>.

Apsiginklavę tokiomis įžvalgomis, uždavinį galime išspręsti dinaminiu programavimu.

UŽDAVINIO SKAIDYMAS MAŽESNIAIS

Ar galima iš duotų pakelių gauti kavą <b in c>? Imkime N-ąjį pakelį. Jo arba prireiks, arba neprireiks. Pirmuoju atveju lieka klausimas: ar galime iš likusių N-1 pakelių gauti kavą <b - a[N] in c - 1>. Antruoju atveju lieka klausimas: ar galime iš likusių N-1 pakelių gauti kavą <b in c>. Abiejais atvejais gauname po analogišką uždavinį, tik mažesnį savo parametrais.

Pats "mažiausias" uždavinys - kai turime 0 pakelių - yra elementarus: tokiu atveju galime pasigaminti tik <0 in 0> kavą, ir jokios kitos.

NUO APAČIOS

Saugokime sąrašą kavų, kokias įmanoma gauti panaudojant k pakelių. Kartu su kava saugokime ir informaciją, iš kokių pakelių ji sudaryta. Sąraše turi būti saugomoas tik skirtingos kavos, tai nesunku efektyviai realizuoti atskirame loginiame masyve įsimenant, kurios kavos jau įtrauktos į sąrašą.

Kai k = 0, sąraše yra vienintelis elementas - <0 in 0>.

Tarkime, kad jau žinome, kokias kavas galime gauti panaudoję k pakelių. Taigi kaip su k + 1 pakelių? Imkime kiekvieną kavą iš sąrašo ir nagrinėkime kiekvieną tai kavai sudaryti nepanaudotą pakelį. Pridėję tą pakelį gausime kavą iš k + 1 pakelių; ją įtraukime į kavų iš k + 1 pakelių sąrašą, tačiau tik tokiu atveju, jei tokia kava dar nebuvo gauta.

Šitaip sudarydami vis naują sąrašą, galiausiai gausime visas kavas, kurias galime sudaryti panaudoję lygiai c pakelių. Belieka patikrinti, ar tarp jų yra kava <b in c>.

Šis algoritmas yra O(N*b*c) sudėtingumo laiko atžvilgiu, jo pakanka uždaviniui išspręsti su visais pradiniais duomenimis.

Saugoti visiems c sąrašų gali nepakakti atminties, todėl reikia pastebėti, jog pakanka atsiminti tik paskutinį sudarytą kavų sąrašą, nes tik jis naudojamas naujam sąrašui sudaryti. Tame sąraše yra daugiausiai b elementų, o kiekviename iš jų yra informacija apie daugiausiai N pakelių. Taigi algoritmui pakanka O(N*b) atminties.

TESTAI

Numeris Komentaras
01      Nedidelis testas - 5 pakeliai.
02      Nedidelis testas - 10 pakelių.
03      Nedidelis testas - 15 pakelių (vienintelis testas, kuriame sprendinio nėra).
04      Vidutinis testas - 20 pakelių, b = 500.
05      Vidutinis testas - 25 pakeliai, b = 4490.
06      Vidutinis testas - 35 pakeliai.
07      Vidutinis testas - 50 pakelių.
08      Didelis testas - 75 pakeliai.
09      Didelis testas - 90 pakelių.
10      Didelis testas - 100 pakelių.