🚀 go-pugleaf

> Czy mnie RAM nie myli czy tam ilosc bitow nie odpowiadala ilosci bramek ?
> ;) Anyway, algorytm w ksiazce nie byl wykladniczy tylko liniowy (to po
> prustu kwestia podejscia) ... i zlozonosc byla okolo
> iloscbramek*ilosckombinacji. Poniewaz zliczanie kombinacji po wstepnych
> obliczeniach sprowadzalo sie tak naprawde do
> log(iloscbramek)*ilosckombinacji. Dla pesymistycznych danych wynosilo to 
> 7 (log(100)) * 100 000 = 700.000 czyli ponizej 0.1 sekundy na pentium
> a optymalny to bylo
> iloscbramek*(Iloscbitow ktore trzeba sprawdzic), co w pesymistycznej
> sytuacji dawalo
> 100 * 100 = 10.000 , czyli ponizej 0.01 sekundy na pentium ... 
Bramek bylo AFAIR 1000, tak wiec algorytm "wzorcowy" dziala na pentiumie
sekunde. W instytucji ktora sprawdza rozwiazania raczej pentiumow bym sie
nie spodziewal, liczylbym raczej na 386 lub 486, tak wiec rozwiazanie
wzorcowe liczy dlugo. Miesci sie w czasie z definicji ;-) 
> Rozwiazanie optymalne polegalo na zliczaniu po calych blokach liczb,
> rozwiazanie trywialne sprowadzalo sie do sprawdzenia po kolei wszystkich
> kombinacji. To drugie bylo o wiele prostsze i latwiejsze do napisania
> (chociaz akurat to bylo zadanie z pierwszego etapu.... wiec nieduzy
> problem, choc np. mi udalo sie niedpatrzyc jednej literowki w optymalnym
> ;) 
Nie sadze. Wtedy jeszcze uczestniczylem w Olimpiadzie, robilem to zadanie
i mi taki algorytm nie przyszedl do glowy. Wedlug mnie najprosciej jest
policzyc ilosc liczb od zera do gornej granicy, od zera do dolnej granicy
i odjac.

*   *        *          ****          *                    
*  *   *     *          *   *       *****
* *          *     ***  *   *         *    ***
**     *     *    *   * ****  *   *   *   *   *
* *    *     *    *   * *   * *   *   *   *****
*  *   *     *    *   * *   * *   *   *   *
*   *   **    **   ***  ****   ***     **  ***
Where do YOU want to die today? *
                              **
 e-mail: kilobyte@iname.com
 URL   : http://free.polbox.pl/k/kilobyte/