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:
- Dacă există un scaun care are doua scaune adiacente libere, ocupă acel scaun.
- Daca nu există un astfel de scaun dar există un scaun cu un singur scaun adiacent liber, ocupă acel scaun.
- Altfel, ocupă unul din scaunele libere.
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.