CSES - Shakkilauta
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Shakkilaudan jokaisessa ruudussa on robotti. Robotit liikkuvat laudalla satunnaisesti toisistaan riippumattomasti k vuoron ajan. Samassa ruudussa voi olla monta robottia.

Robotti voi liikkua oikealle, vasemmalle, ylöspäin ja alaspäin mutta ei laudan ulkopuolelle. Kullakin vuorolla robotti valitsee suunnan satunnaisesti niiden suuntien joukosta, joihin se voi liikkua, ja jokaisen suunnan todennäköisyys tulla valituksi on sama.

Tehtäväsi on laskea odotusarvo, moniko ruuduista on tyhjiä k vuoron jälkeen.

Syöte

Syötteen ainoalla rivillä on kokonaisluku k.

Tuloste

Tulosta odotusarvo pyöristettynä niin, että siinä on tasan 6 desimaalia.

Rajat

  • 1 \le k \le 100

Esimerkki

Syöte:

10

Tuloste:

23.120740