| 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 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.
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
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.
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.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ vi ≤ N
| # | Punctaj | Restrcţii |
|---|---|---|
| 1 | 10 | 1 ≤ N ≤ 10 |
| 2 | 10 | 1 ≤ N ≤ 20 |
| 3 | 30 | 1 ≤ N ≤ 50 |
| 4 | 50 | Restricţiile iniţiale |
Exemple
| 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. |
