== include(page="template/taskheader" task_id="bt") ==
John şi-a investit toate economiile în criptomonede. Acum încearcă să mai recupereze din bani, trecând pe dieta campionilor (brânză topită).
_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.
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.
!{float: right; width: 400px; }problema/bt?enunt-bt.png!
Formal, se dă un vector circular $v{~1~}, v{~2~}, ... , v{~N~}$. 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 brâ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.
h2. 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ţ).
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ţ).
h2. Date de intrare
Pe prima linie a fişierului de intrare $bt.in$ se găseşte un singur număr natural N, reprezentând lungimea vectorului.
Pe a doua linie se găsesc N numere naturale, v1 , v2 , . . . , vN, reprezentând valorile din vector.
Pe prima linie a fişierului de intrare $bt.in$ se găseşte un singur număr natural $N$, reprezentând lungimea vectorului.
Pe a doua linie se găsesc $N$ numere naturale, $v{~1~} , v{~2~} , ... , v{~N~}$, reprezentând valorile din vector.
h2. Date de ieşire
În fişierul de ieşire $bt.in$ se va afişa un singur număr, reprezentând numărul de moduri de a goli vectorul (modulo 1 000 000 007).
Problema are 2 moduri de punctare: vectorul este circular (pentru 100% din punctajul de pe un test) sau vectorul nu este circular - v1 şi vN nu sunt consideraţi vecini (pentru 80% din punctaj).
Iniţial, numărul afişat este comparat cu răspunsul corespunzător vectorului circular pentru 100% din punctajul testului.
Dacă răspunsurile diferă, numărul este apoi comparat cu răspunsul corespunzător vectorului normal (v1 şi vN nu sunt consideraţi vecini) pentru 80% din punctajul testului.
În fişierul de ieşire $bt.in$ se va afişa un singur număr, reprezentând numărul de moduri de a goli vectorul (modulo $1 000 000 007$).
Problema are 2 moduri de punctare: vectorul este circular (pentru $100%$ din punctajul de pe un test) sau vectorul nu este circular - $v{~1~}$ şi $v{~N~}$ nu sunt consideraţi vecini (pentru $80%$ din punctaj).
Iniţial, numărul afişat este comparat cu răspunsul corespunzător vectorului circular pentru $100%$ din punctajul testului.
Dacă răspunsurile diferă, numărul este apoi comparat cu răspunsul corespunzător vectorului normal ($v{~1~}$ şi $v{~N~}$ nu sunt consideraţi vecini) pentru $80%$ din punctajul testului.
h2. Restricţii
* $1 ≤ N ≤ 500$
* $1 ≤ v~i~ ≤ N$
h2. Exemplu
table(example). |_. bt.in |_. bt.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* $1 ≤ v{~i~} ≤ N$
h3. Explicaţie
table(subtasks). |_. # |_. Punctaj |_. Restrcţii |
| 1 | 10 | $1 ≤ N ≤ 10$ |
| 2 | 10 | $1 ≤ N ≤ 20$ |
| 3 | 30 | $1 ≤ N ≤ 50$ |
| 4 | 50 | Restricţiile iniţiale |
h2. Exemple
table(example). |_. bt.in |_. bt.out |_. Explicaţii |
| 4
1 2 1 2
| 0
| În primul exemplu, orice am scoate am avea ulterior doi de $1$ vecini sau doi de $2$ vecini,
deci nu putem goli vectorul. Dacă am avea un delimitator între ultimul element şi primul,
răspunsul ar fi $8$. Secvenţele de indici corecte în acest caz ar fi:
• $1, 2, 3, 4$
• $1, 2, 4, 3$
• $1, 4, 2, 3$ (vectorul ar arăta: $(1,2,1,2) → (2,1,2) → (2,1) → (1) → gol$)
• $1, 4, 3, 2$
• $4, 1, 2, 3$
• $4, 1, 3, 2$
• $4, 3, 1, 2$
• $4, 3, 2, 1$
|
| 8
1 2 1 3 1 2 1 3
| 1728
| În al doilea exemplu, răspunsul corect dacă ar exista un delimitator este $6912$.
|
| 4
1 2 3 4
| 24
| În al treilea exemplu, deoarece orice element din vector este distinct, acestea pot fi
scoase în orice ordine. Răspunsul pentru celălalt caz este tot $4! = 24$.
|
| 6
1 2 3 1 3 2
| 96
| În al patrulea exemplu, răspunsul corect dacă ar exista un delimitator este $312$.
|
| 1
1
| 1
| În al cincilea exemplu, avem un singur element în vector, deci există o singură cale de
a-l scoate. Răspunsul pentru celălalt caz este tot $1$.
|
...
== include(page="template/taskfooter" task_id="bt") ==
