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

Zadatak: Stringsobits

[es] :: Art of Programming :: Zadatak: Stringsobits

[ Pregleda: 4165 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stf

Član broj: 51276
Poruke: 65
*.157.eunet.yu.



Profil

icon Zadatak: Stringsobits29.08.2005. u 12:22 - pre 226 meseci
Ovaj zadatak nikako neće da mi prođe na USACO-u kroz sve test primere. Zna li neko optimalno rešenje?

Stringsobits

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.
This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.
Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)
5 3 19

OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)
10011

If you don't live for something, you will die for nothing.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 15:21 - pre 226 meseci
Kreiras sve reci u kojima se pojavljuje tacno L jedinica i sve ostalo su nule. Potom svaku tu rec prebacis u decimalni broj, pa ih sve lepo sortiras, i onda na kraju I-ti broj ispises u binarnom sistemu (dodas vodece nule ako je potrebno). Meni se cini da sam tako radio taj zadatak ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 17:29 - pre 226 meseci
Ja sam sad nesto kreno preko binomnog koeficijenta, gde vrednost matrice m(a,b) prestavlja broj pojavljivanja jedinica (ukupno a) u stringu duzine b. Ako ni ovako ne bude radilo pokusacu i to tvoje resenje..
If you don't live for something, you will die for nothing.
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 17:50 - pre 226 meseci
Ne verujem da tvoje resenje moze da prodje kroz sve test primere. Mozda gresim, al evo primer iz zadatka:
Sve reci koje imaju 3 jedinice u sortiranom poretku su:
00111=7
01011=11
01101=13
01110=14
10011=19
10101=21
10110=22
11001=25
11010=26
11100=28
Ovde se trazi I-ti broj sa 3 ili MANJE jedinica, ne samo tacno toliko.
Ukupno reci sa nula, jedan, dve ili tri jedinice ima 26 (u sortiranom poretku, decimalni sistem):
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,17,18,19,20,21,22,24,25,26,28.
Ovde je 19. broj 19, i sad ga ispisem kao binaran.
Ali sta naprimer ako se trazi 123456789. broj u nizu. Tada quicksort (n log n) ne moze da prodje.

Imao sam staro resenje slicno tvome, al ne moze da prodje! Mozda moze nesto da se uradi sa ovim binomnim koeficijentom (generisem pomocu njega vrednost m(a,b)) ili neko drugo resenje?

If you don't live for something, you will die for nothing.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 18:09 - pre 226 meseci
Sad sam bas poslao moje staro resenje da vidim da li prolazi ... i kao sto se ocekivalo, ne prolazi :) (meni je onda proslo; mislim da su od tada pomerili malo vremenske granice ...)

Na USACO-u me malkice nervira sto imaju tako mali time limit ... zna posteno da smori :)

Posto me mrzelo da ga ponovo resavam, pogledao sam analysis :)
Problem se reshava dinamichkim programiranjem ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 18:33 - pre 226 meseci
Aj postuj ono objasnjenje iznad koda u Analysis
If you don't live for something, you will die for nothing.
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Zadatak: Stringsobits29.08.2005. u 22:51 - pre 226 meseci
Nasao sam u medjuvremenu resenje preko binomnog koeficijenta.

Slozenost je veoma mala: O(31*31*vreme za trazenje bin. koef.)

Takodje, algoritam nije tezak toliko za implementaciju

Thanks anyway :)

[Ovu poruku je menjao stf dana 29.08.2005. u 23:51 GMT+1]
If you don't live for something, you will die for nothing.
 
Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249



+96 Profil

icon Re: Zadatak: Stringsobits30.08.2005. u 09:39 - pre 226 meseci
Niz koji je ovde potreban je A000120, za objašnjenje videti link http://www.research.att.com/projects/OEIS?Anum=A000120. Sve što treba uraditi je proći kroz niz, ignorišući one vrednosti koje su veće od L, sve dok ne nađemo I-ti takav broj. Problem se sada svodi na računanje elemenata tog niza.
 
Odgovor na temu

[es] :: Art of Programming :: Zadatak: Stringsobits

[ Pregleda: 4165 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

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