RSS Feed
Următoarea

Problema 364

24 Decembrie 2011

Distanță confortabilă


Sunt N scaune într-un rând. N oameni vin pe rând pentru a le ocupa respectând următoarele reguli:

  1. Dacă există un scaun care are doua scaune adiacente libere, ocupă acel scaun.
  2. Daca nu există un astfel de scaun dar există un scaun cu un singur scaun adiacent liber, ocupă acel scaun.
  3. Altfel, ocupă unul din scaunele libere.
Fie T(N) numărul de posibilități ca N scaune să fie ocupate de N oameni respectând regulile date.
Următoarea figură ilustrează situația T(4)=8.

Se poate verifica că T(10) = 61632 si T(1 000) mod 100 000 007 e egal cu 47255094.

Află T(1 000 000) mod 100 000 007.


>> Vezi problema originală <<