Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bt.in, bt.out | Sursă | ONI 2023, Baraj Seniori, ziua 1 |
| Autor | Vlad Adrian Ulmeanu | Adăugată de |  Livia Magureanu •livlivi |
| Timp execuţie pe test | 1.1 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bt
John şi-a investit toate economiile în criptomonede. Acum încearcă să mai recupereze din bani, trecând pe dieta campionilor (brânză topită).
El are o cutie circulară cu N bucăţi de brânză (de mai multe tipuri), iar în fiecare zi ia câte una din cutie. Acesta are grijă ca înainte şi după ce ia o bucată din cutie, oricare două bucăţi adiacente rămase să fie de alt tip.
John s-a apucat să numere în câte moduri poate să termine cutia.
Formal, se dă un vector circular v1, v2, . . . , vN . Vrem să scoatem din el câte un element până rămâne gol vectorul. În urma fiecărei scoateri, inclusiv înaintea primei scoateri, nu trebuie să existe 2 poziţii consecutive în vector cu aceeaşi valoare în ele.
În exemplul din dreapta, bucăţile de bânză de pe poziţiile A şi B au fost deja luate. Singurele bucăţi pe care le-am putea scoate acum ar fi E sau G. Dacă am scoate bucata C, atunci bucăţile D şi H, ambele de tipul 2, ar deveni vecine. Dacă l-am scoate pe D, C şi E ar deveni vecine, deşi sunt ambele de tipul 1, etc.
Cerinţă
Să se numere în câte moduri putem goli vectorul respectând regulile din enunţ (modulo 1 000 000 007).
Un mod de a goli vectorul este definit de ordinea indicilor care părăsesc vectorul. De exemplu, pentru N = 4, sunt 4! = 24 de moduri diferite de a goli vectorul (dintre care nu toate respectă regulile din enunţ).
Date de intrare
Fişierul de intrare bt.in ...
Date de ieşire
În fişierul de ieşire bt.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| bt.in | bt.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
