Percorso ad ostacoli

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: saltatutto.c
• Scarica la traccia in C++: saltatutto.cpp
• Scarica la traccia in C#: saltatutto.cs
• Scarica la traccia in Go: saltatutto.go
• Scarica la traccia in JavaScript: saltatutto.html
• Scarica la traccia in Java: saltatutto.java
• Scarica la traccia in Pascal: saltatutto.pas
• Scarica la traccia in Python: saltatutto.py
• Scarica la traccia in VisualBasic: saltatutto.vb

Descrizione del problema

Carol si è iscritta ad una gara di corsa ad ostacoli! Il percorso si svolge su una sequenza di rocce di lunghezza $N$. Le rocce possono essere piatte o alte: si può stare solo sulle rocce piatte, mentre le rocce alte sono gli ostacoli ed è possibile solo saltarle. Carol sa che se si avanza o atterra su una roccia alta si cade, perdendo la gara. Carol può fare le seguenti azioni:

• avanza: avanza alla roccia successiva: se Carol è sulla roccia $i$ dopo l'azione avanza sarà sulla roccia $i+1$.
• salta: salta oltre alla prossima roccia, atterrando su quella dopo: se Carol è sulla roccia $i$ dopo l'azione salta sarà sulla $i+2$.

Carol si trova sulla roccia numero $1$ e lo scopo della gara è raggiungere la bandierina alla fine della sequenza di rocce dopo la roccia $N$. Il percorso di rocce è descritto da $N$ numeri. Se l'$i$-esima roccia è alta l'$i$-esimo numero sarà $1$ altrimenti sarà $0$.

Per aiutare Carol le vuoi consegnare un bigliettino con su scritto le azioni da fare per superare il percorso! Carol leggerà le lettere sul bigliettino una alla volta: farà un'azione salta ogni volta che leggerà una S e farà un'azione avanza ogni volta che leggerà una A. Cosa dovrai scrivere sul bigliettino per aiutare Carol a superare il percorso?

Formato di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• una riga contenente l'intero $N$.
• una riga contenente gli $N$ interi $R_{1}, \, \ldots, \, R_{N}$.

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura "Case #test: ", dove test è il numero del caso di test (a partire da $1$), , seguita dalla sequenza di lettere S e A che vuoi scrivere sul biglietto da dare a Carol.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \leq N \leq 1000$.
• $0 \leq R_i \leq 1$.
• È garantito che esista una sequenza di azioni per arrivare alla bandierina.

Esempi di input/output

---

Input:

3

3
0 1 0

4
0 0 0 1

5
0 1 0 0 1

---

Output:

Case #1: SA
Case #2: AAS
Case #3: SAS

---

Spiegazione

Nel primo caso di esempio, Carol deve superare il percorso in figura:

Il bigliettino che dovrai dare a Carol conterrà la scritta SA. Carol leggendolo farà le seguenti azioni:

1. salta dalla roccia $1$ alla roccia $3$ saltando la roccia alta in posizione $2$.
2. avanza dalla roccia $3$ alla bandierina alla fine del percorso.

Nel secondo caso di esempio, Carol deve superare il percorso in figura:

Sul bigliettino che darai a Carol potresti scrivere AAS. Carol leggendolo farebbe le seguenti azioni:

1. avanza dalla roccia $1$ alla roccia $2$.
2. avanza dalla roccia $2$ alla roccia $3$.
3. salta dalla roccia $3$ alla bandierina saltando la roccia alta in posizione $4$.

Per lo stesso percorso sul bigliettino avresti potuto anche scrivere SS. Carol leggendolo farebbe le seguenti azioni:

1. salta dalla roccia $1$ alla roccia $3$ saltando la roccia in posizione $2$.
2. salta dalla roccia $3$ alla bandierina saltando la roccia alta in posizione $4$.

Nel terzo caso di esempio, , Carol deve superare il percorso in figura:

Sul bigliettino che darai a Carol potresti scrivere SAS. Carol leggendolo farà le seguenti azioni:

1. salta dalla roccia $1$ alla roccia $3$ saltando la roccia alta in posizione $2$.
2. avanza dalla roccia $3$ alla roccia $4$.
3. salta dalla roccia $4$ alla bandierina saltando la roccia alta in posizione $5$.