Scatole di cartone

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: scatole.c
• Scarica la traccia in C++: scatole.cpp
• Scarica la traccia in C#: scatole.cs
• Scarica la traccia in Go: scatole.go
• Scarica la traccia in JavaScript: scatole.html
• Scarica la traccia in Java: scatole.java
• Scarica la traccia in Pascal: scatole.pas
• Scarica la traccia in Python: scatole.py
• Scarica la traccia in VisualBasic: scatole.vb

Descrizione del problema

Edoardo ha due scatole vuote e un sacco di palline. Ogni giorno, Edoardo può fare una sola operazione: aggiungere a una delle due scatole un numero di palline uguale al numero del giorno corrente. Ad esempio, il primo giorno può aggiungere una pallina a una delle due scatole, il secondo giorno può aggiungerne due, e così via.

Edoardo si chiede se, dopo un certo numero di giorni, può fare in modo che una delle due scatole contenga esattamente $A$ palline e l'altra esattamente $B$ palline. Aiutalo a trovare una sequenza di operazioni che gli permetta di raggiungere il suo obiettivo.

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 da una sola riga che contiene due interi $A$ e $B$.

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 #t: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è

• se il problema è impossibile: IMPOSSIBLE
• se il problema è possibile: una stringa formata dai caratteri 1 e 2 che rappresenta la sequenza di operazioni da fare per ottenere il risultato. L'$i$-esimo carattere della stringa deve essere 1 se l'$i$-esimo giorno Edoardo deve mettere una pallina nella prima scatola e 2 se la deve mettere nella seconda.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \le A, B \le 10^5$.

Nei primi $4$ casi di test vale $A, B \le 500$.

Esempi di input/output

Input:

4
2 4
13 16
18 10
17 19

Output:

Case #1: 212
Case #2: IMPOSSIBILE
Case #3: 2222111
Case #4: 21222211

Spiegazione

Nel primo caso d'esempio, eseguiamo le seguenti operazioni:

• Aggiungi $1$ pallina alla seconda scatola
• Aggiungi $2$ palline alla prima scatola
• Aggiungi $3$ palline alla seconda scatola Alla fine, la prima scatola contiene $2$ palline e la seconda scatola contiene $4$ palline.

Nel secondo caso d'esempio, non è possibile mettere $13$ palline in una scatola e $16$ nell'altra, quindi la risposta è IMPOSSIBILE.