| Fişierul intrare/ieşire: | vegas.in, vegas.out | Sursă | Baraj Shumen Seniori ICHB-Vianu - 2022 |
| Autor | Adăugată de |  Comisie Seniori Vianu ICHB •comisie_baraj_shumen_ichb_vianu_seniori | |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Vegas
Aceasta problema a fost preluată de pe atcoder: F - Prime Flip
Dl J. a ajuns săptămâna aceasta în Vegas. Dacă nu îl cunoașteți încă pe dl J., nu vă îngrijorați, tot ce trebuie să faceți pentru a intra în cercul lui de apropiați este să existați și să-l ajutați cu o mică problema, dar toate la timpul lor.
Jocul preferat al dlui J. este unul rezervat cunoscătorilor, așa că nu vă vom împovăra cu numele lui. Cât despre reguli, acestea sunt cum nu se poate mai simple. Pe o masa se află un număr infinit de cărți, numerotate de la 1. Inițial cărțile x1, x2, ... xN se află cu fața în sus, iar toate celelalte sunt așezate cu fața în jos. Jucătorul poate aplica asupra cărților, de câte ori vrea, următoarea operație:
- Alege un număr prim p ≥ 3. Apoi alege p cărți consecutive și le întoarce pe fiecare dintre ele.
Jucătorul câștigă dacă reușește să aducă toate cărțile cu fața în jos dintr-un număr minim de mutări.
Aici interveniți voi. Ajutați-l pe dl J. să afle care este numărul minim de mutări pentru a câștiga la o masă de joc dată!
Date de intrare
Fişierul de intrare vegas.in conține T teste. Pe prima linie a fișierului se află T, numărul de teste din fișier.
Fiecare test este format din două linii. Prima dintre acestea conține N, numărul de cărți care se află cu fața în sus. Pe a doua linie a testului, se dau, în ordine crescătoare, separate prin spațiu, cele N cărți.
Date de ieşire
În fişierul de ieşire vegas.out se vor afișa T linii. Pe a i-a linie afișați numărul minim de operații de care are nevoie dl J. pentru a câștiga la masa descrisă în al i-lea test din fișierul de intrare.
Restricţii
- 1 ≤ T ≤ 6
- 1 ≤ N ≤ 100
- 1 ≤ x1 < x2 < ... < xN ≤ 107
Subtask-uri
| Subtask | Punctaj | Restricții |
|---|---|---|
| 1 | 1 punct | 1 ≤ N ≤ 10 |
| 2 | 1 punct | 1 ≤ N ≤ 20 |
| 3 | 1 punct | 1 ≤ xN ≤ 200 |
| 4 | 2 puncte | Fără restricții adiționale |
Exemplu
| vegas.in | vegas.out |
|---|---|
| 2 2 1 2 6 3 4 5 6 7 9 | 2 4 |
Explicaţie
În primul test din exemplu, prima operație este să întoarcă secvența de cărți 1-5 => cărțile cu fața în sus vor fi: 3, 4, 5.
A doua operație este să întoarcă cărțile din secvența 3-5 => toate cărțile ajung cu fața în jos.
Al doilea test din exemplu:
După secvența: 8-12 => cărțile cu fața în sus: 3 4 5 6 7 8 10 11 12
După secvența: 10-12 => cărțile cu fața în sus: 3 4 5 6 7 8
După secvența: 3-13 => cărțile cu fața în sus: 9 10 11 12 13
După secvența: 9-13 => toate cărțile sunt cu fața în jos
