On 30.03.2013 18:39, Roman W wrote:
>
> Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
> Mozna to zrobic w O(1).

Wybierasz pierwszą. W każdym kroku z prawdopodobieństwem P zależącym od
ilości wczytanych linii wybierasz bieżącą a z (1-P) zostajesz przy
poprzednim wyborze. Tylko trzeba mieć dobry generator dla takich
sekwencji i nie nadziać się na zaokrąglenia.

--
Pozdrawiam
Michoo