Unosi se beskonačnan niz prirodnih brojeva. U ovom nizu se u toku unosa traže tri broja ai, aj i ak koji zadovoljavaju sledeće uslove:
- ai < aj < ak
- i < j < k
- (ai + aj + ak) - deljivo sa tri
Unos se više ne prima nakon što je tražena kombinacija nađena.
-------------------------------------------
Dakle tražena kombinacija svakako pripada uzlaznom uređenom nizu, i može je činiti više klasa trojki brojeva:
- tri broja čiji je ostatak pri deljenju sa 3 nula (0 0 0)
- tri broja -- // -- jedan (1 1 1)
- tri broja -- // -- dva (2 2 2)
- tri broja čiji su ostatci pri deljenju sa tri nula, jedan i dva (0 1 2)
Ukoliko se u unosnom nizu pak dođe broja koji kvari uzlazni poredak,on se ne može ignorisati, jer je moguće da će sada od njega početi traženi niz. Na primer:
..., 300, 301, 303, 304, 3, 4, 5, ...
Što me navodi na zaključak da svakako treba pamtiti skoro sve brojeve, dok se ne dođe do dobitne kombinacije. Jedina optimizacija koja mi pada na pamet je ignorisanje brojeva jednakih uzastopnih brojeva.
Pritom, ukoliko se desi nešto poput:
10,15,13,3,12, ...
Broj 12 treba da bude posmatran i kao deo 10,12 i kao deo 3,12. Itd.
-------------------------------------------
Ono što me buni je da je uslov zadatka upotreba minimalne količine memorije, dok sa druge strane ne vidim mogućnost neke značajne optimizacije, osim te za jednake brojeve.
Na primer jedan ovakav niz uzlaznih nizova od po dva elementa:
999999, 1000000, 999997, 999998, 999995, 999996, ... 1, 2, 3, ...
Bi morao biti zapamćen u celosti, dok se ne naiđe na 1, 2, 3, ...
Interesuje me postoji li bolji rezon.
[Ovu poruku je menjao Mali Misha dana 12.11.2006. u 13:00 GMT+1]