Programozás‎ > ‎Feladatok‎ > ‎Számösszegzés‎ > ‎

Megoldás

Algoritmus

Egy x szám akkor állítható elő, ha

a) osztható valamelyik ai-vel;

VAGY

b) valamelyik ai-re x - ai előállítható.

Ha minden lehetséges x-re kiszámítjuk ezt a logikai értéket, választ kapunk a feladat kérdésére. Amennyiben a legnagyobb előállítandó szám 106 nagyságrendű, akkor a memóriában is elférünk, és a futási idő kényelmesen 1 perc alatt marad. Ha 109 nagyságrendben is vannak számok, amiket elő kell állítani, akkor a memóriaigényt csökkenthetjük az alábbi (Fehér Gábortól származó) ötlettel:

Mivel az ai számok nem haladják meg a 30000-et, a fenti b) esetben legfeljebb 30000-rel kell "visszanézni", tehát elegendő mindig az utolsó 30000 logikai értéket tárolni. Ez hatékonyan programozható, ha lehet[i] helyett a lehet[i mod 30000] értéket használjuk.
Sajnos a futási időn ez nem segít. A legnagyobb teszteset nekem 1 perc 8 másodpercig futott egy négymagos, 3.2 GHz-es gépen, java-ban implementálva. Lehet, hogy egy jó C++ compilerrel ez becsúszik 1 perc alá, de valószínűleg van még valami algoritmikus trükk, amivel a program gyorsítható.

Kódok

Erben Péter (java): szamosszegzesNagy.java