[es] - humble numbers problem

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.

Profil

^{25.09.2004. u 00:22 - pre 238 meseci}

Evo jedan zadatak sa USACO-a koji nisam uspeo da reshim ( a bash sam se potrudio :). U svakom sluchaju :

dat je skup prostih brojeva S=(p1,p2,...,pk) gde je k maximalno 100. Treba naci koji je n-ti chlan rastuceg niza u kome su svi brojevi oblika
p1^a1*p2^a2*...*pk^ak.
npr. s=(2,3,5,7); n=19
trazeni broj je 27.

ogranichenje za k je 100, a za n je 100000. Trazeni broj staje u LongInt.

potrebne su mi ideje ... (poshto sam sve svoje ispucao:(

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: humble numbers problem

^{25.09.2004. u 13:39 - pre 238 meseci}

Probaj recimo ovako:

Napravi strukturu koja će da sadrži tri polja:
- prost_broj (ceo broj)
- indeks_množitelja (ceo broj)
- trenutni_proizvod (veliki ceo broj),
a zatim i niz A koji će da prihvati k takvih elemenata.

Takođe, formiraj i niz B velikih celih brojeva u koji možeš da smestiš tih n proizvoda.

1. Za svaki prost broj iz skupa popuni jedan element niza A tako da poljima prost_broj i trenutni_proizvod dodeliš vrednost tog prostog broja, a indeks_množitelja postavi na nulu.
2. Sortiraj niz A u rastućem poretku po vrednosti polja trenutni_proizvod (ili prost_broj, pošto nema razlike).
3. Za i=1..n
3.1. Postavi vrednost i-tog elementa niza B na vrednost polja trenutni_proizvod prvog elementa niza A.
3.2. Povećaj vrednost polja indeks_množitelja prvog elementa niza A za jedan.
3.3. Pomnoži vrednost polja prost_broj prvog elementa niza A sa elementom niza B sa indeksom ideks_množitelja (dobijenim u prethodnom koraku) i rezultat množenja upiši u polje trenutni_proizvod prvog elementa niza A (u prevodu A[1].trenutni_proizvod = B[A[1].indeks_množitelja] * A[1].prost_broj).
3.4. Prvi element niza A prebaci na novu poziciju tako da niz ostane sortiran u rastućem poretku po vrednosti polja trenutni_proizvod.

To bi moglo da bude sve. Na kraju će traženi broj biti n-ti element niza B.

Odgovor na temu

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

+1 Profil

Re: humble numbers problem

^{26.09.2004. u 03:12 - pre 238 meseci}

Uf, opet previd - zaboravih da će se ovako javiti duplikati. Postupak je, dakle, potrebno izmeniti.

Prva dva koraka ista.
3. Postavi j na jedan.
4. Postavi B[0] na nulu (da se osigura početno zadovoljenje uslova u koraku 5.1 i startuje popunjavanje)
5. Ponavljaj dok je j manje od n+1
5.1. Ako je vrednost polja trenutni_proizvod prvog elementa niza A različita od (j-1)-og elementa niza B, onda:
5.1.1 Postavi vrednost j-tog elementa niza B na vrednost polja trenutni_proizvod prvog elementa niza A.
5.1.2. Povećaj j za jedan.

5.2, 5.3 i 5.4 isti kao 3.2, 3.3 i 3.4 u prethodnom pokušaju.

Odgovor na temu