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 | Victor Manz • vmanz |
Timp de execuție pe test | 2 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.