Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Ne vidim drugi način... (ACM-oliki zadatak)

[es] :: Art of Programming :: Ne vidim drugi način... (ACM-oliki zadatak)

[ Pregleda: 2871 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
85.187.163.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Ne vidim drugi način... (ACM-oliki zadatak)12.11.2006. u 11:32 - pre 211 meseci
Dakle, naišao sam skoro na jedan zadatak koji zahteva da se pri njegovom rešavanju upotrebi minimum potrebne memorije.

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]
Ipak se ++uje.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.12.*



+1 Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)12.11.2006. u 23:18 - pre 211 meseci
Nisam bas ukapirao sta si heteo da kazes, ali kako vidim ti mozes samo da pamtis indekse brojeva koji imaju ostatan 0, 1, i 2 i za svaki od tih ostataka najvise njih 3. I cim dobijes jednu dobitnu kombinaciju, stampas indeske iz tih brojeva (znaci samo pamtis matricu 3 x 3).
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
85.187.163.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)13.11.2006. u 19:52 - pre 211 meseci
Citat:
Nisam bas ukapirao sta si heteo da kazes

Šta tačno? Da pojasnimo ako treba...

Uglavnom, po čitanju odgovora mogu da ponovim da nađeni brojevi kao i njihovi indeksi trebaju da zadovoljavaju uzlazni poredak, uz to što nađena kombinacija treba da bude prva moguća koja zadovoljava uslov. Dakle ako imaš niz poput:

98,99,96,97,94,95,92,93,90,91,88,89,86,87,84,85,82,83,80,81,94

Traženi rezultat je 92,93,94 ( 98,99,96,97,94,95,92,93,90,91,88,89,86,87,84,85,82,83,80,81,94 ) .
Ipak se ++uje.
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
89.190.198.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)17.11.2006. u 17:46 - pre 211 meseci
Što se mene tiče, dokazano je da ima slučajeva kada se milionski nizovi moraju u celosti smeštati u memoriju.
Ipak se ++uje.
 
Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dynamic.sbb.co.yu.

Sajt: toroman.wordpress.com


Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)18.11.2006. u 21:31 - pre 211 meseci
Citat:
Mali Misha: Što se mene tiče, dokazano je da ima slučajeva kada se milionski nizovi moraju u celosti smeštati u memoriju.
--
Ne, hvala. Neću pingvina.


Mozda pingvini mogu ;)
Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)20.11.2006. u 21:38 - pre 211 meseci
Jel ovaj zadatak sa nekog ACM-a? Samo mi kazi vremensko i memorijsko ogranicenje (a i bitno je koja su ogranicenja za brojeve u nizu, i da li imas ogranicenje do kog n ce sigurno da postoji trojka).

I sta znaci recenica: "...dokazano je da ima slučajeva kada se milionski nizovi moraju u celosti smeštati u memoriju." Inace ti mozes da cuvas (barem na ACM-ovima) i niz do 25000000 miliona int-a. Zavisio od memorijskog ogranicenja, koje je obicno 64MB. Tako da ako je ogranicenje za niz tip 10,000,000 ti to mozes da cuvas.
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
89.190.198.*

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Ne vidim drugi način... (ACM-oliki zadatak)20.11.2006. u 21:57 - pre 211 meseci
Ne, nije sa ACM, samo mi je ličio na tako nešto, ali izgleda da samo nema smisla. Zašto nema:

Problem je sasvim rešiv na način koji si spomenuo ako se traži "ikakvo rešenje". Ali kada se traži kombinacija prve moguće trojke brojeva (dakle zbir indeksa nađenih brojeva je još i minimalan) ima slučajeva kada treba pamtiti sve brojeve, pošto niz nije sortiran a ponavljanja brojeva su moguća. Zbog toga ne bi imalo smisla zahtevati ikakvu optimizaciju po pitanju memorije.

Što se mene tiče, ovo je mrtva tema ali evo jednog primera:

98, 99, 96, 97, 94, 95, 92, 93, 90, 91, 88, 89, 86, 87, 84, 85, 82,
83, 80, 81, 78, 79, 76, 77, 74, 75, 72, 73, 70, 71, 68, 69, 66, 67,
64, 65, 62, 63, 60, 61, 58, 59, 56, 57, 54, 55, 52, 53, 50, 51, 48,
49, 46, 47, 44, 45, 42, 43, 40, 41, 38, 39, 36, 37, 34, 35, 32, 33,
30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14,
15, 12, 13, 10, 11, 8, 9, x

ukoliko je x paran broj u rasponu 10 do 100, rešenje bi bilo x-2, x-1, x, što pokriva ceo niz.
Ipak se ++uje.
 
Odgovor na temu

[es] :: Art of Programming :: Ne vidim drugi način... (ACM-oliki zadatak)

[ Pregleda: 2871 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.