Fişierul intrare/ieşire:arena.in, arena.outSursăOlimpiada pe scoala 2017 clasele a 11-a si a 12-a
AutorLivia TocaAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Arena

Un dresor lucrează cu animale din speciile leu, urs, vulpe şi gâscă. Fiecare trupă pe care o pregăteşte este formată din câte N animale, care sunt scoase în arenă unul câte unul, o trupă fiind definită prin ordinea în care speciile de animale se succed. Dresorul dispune de oricâte animale este nevoie, dar la alcătuirea unei trupe trebuie să ţină seama de anumite restricţii, precizate mai jos.
Ştiţi cum sunt leii: toţi vor să fie şefi! Un leu se simte şef doar dacă între el şi următorul leu sunt cel puţin două animale din altă specie.
Urşii sunt animale citite: încă din copilărie ştiu povestea "Ursul păcălit de vulpe" şi, având resentimente la adresa vulpilor, devin nervoşi în apropierea acestora; de aceea, între un urs şi o vulpe trebuie să apară cel puţin un animal din altă specie.
Două gâşte nu se pot abţine să vorbească dacă intră în arenă pe poziţii consecutive, aşa că între ele trebuie să apară cel puţin un animal din altă specie. Societatea din arenă este cosmopolită dar totuşi, gâştele, deşi emancipate, ţin la tradiţii: nicio gâscă nu acceptă să intre o vulpe în arenă imediat după ea, aşa că dresorul trebuie să evite şi această situaţie.
Dresorul a pregătit toate trupele posibile pentru că va avea multe spectacole în anii aceştia şi, fiind un artist care se respectă, vrea ca fiecare astfel de trupă, având propria coregrafie, să apară în cel mult un spectacol.

Cerinţă

Determinaţi numărul total T de trupe care pot fi pregătite, având în vedere restricţiile impuse.

Date de intrare

Fişierul de intrare arena.in conţine numărul natural N, având semnificaţia precizată mai sus.

Date de ieşire

În fişierul de ieşire arena.out se scrie numărul natural T, având semnificaţia precizată mai sus.

Restricţii

  • 1 ≤ N ≤ 2000
  • Pentru 50% dintre teste, numărul cerut respectă condiţia: T < 2 64

Exemplu

arena.inarena.out
4
64

Explicaţie

Dacă se notează cu 1 leii, cu 2 urşii, cu 3 vulpile şi cu 4 gâştele, se pot obţine următoarele 64 de trupe: 1221, 1222, 1224, 1241, 1242, 1331, 1333, 1334, 1341, 1342, 1421, 1422, 1424, 2122, 2124, 2133, 2134, 2142, 2212, 2213, 2214, 2221, 2222, 2224, 2241, 2242, 2412, 2413, 2414, 2421, 2422, 2424, 3122, 3124, 3133, 3134, 3142, 3312, 3313, 3314, 3331, 3333, 3334, 3341, 3342, 3412, 3413, 3414, 3421, 3422, 3424, 4122, 4124, 4133, 4134, 4142, 4212, 4213, 4214, 4221, 4222, 4224, 4241, 4242.

Trebuie sa te autentifici pentru a trimite solutii. Click aici