Fișierul intrare/ieșire arena.in, arena.out Sursă Olimpiada pe scoala 2017 clasele a 11-a si a 12-a
Autor Livia Țoca Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 2 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in arena.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii