Salta il coniglietto

Consideriamo un vettore V di N numeri interi, in cui le posizioni di V sono numerate da 1 a N.
Inizialmente, un coniglietto è seduto in posizione I=1.
Il tempo è discreto: se all’istante t il coniglietto è seduto in posizione I, all’istante t+1 sarà seduto in posizione

Ricordiamo che l’operazione (X modulo N) restituisce il resto della divisione intera di X per N.

Il tuo compito consiste nello scrivere le posizioni di V che non possono essere mai raggiunte dal coniglietto.

Dati in Input

Il file input.txt è composto da due righe

• La prima riga contiene l’intero N che indica la lunghezza del vettore V.
• La seconda riga contiene i suoi N interi separati da uno spazio.

Dati in Output

Il file output.txt è composto da composto da due righe

• La prima riga contiene l’intero E che indica numero di elementi nella sequenza.
• La seconda riga contiene le E posizioni di V che non possono essere mai raggiunte dal coniglietto, elencate in ordine crescente e separate da uno spazio.

Assunzioni

• 1 <= N <= 10⁶
• 0 <= V[i] <= 10⁶ per 1 <= i <= N

Esempi di input/output

Note

• Viene garantito che esiste sempre almeno una posizione che non viene mai raggiunta dal coniglietto.
• L’operatore modulo è realizzato con % in C/C++ e con mod in Pascal.

---

/*
    www.valcon.it    
    OII 2011 - Olimpiadi italiane - SALTA IL CONIGLIETTO
*/  

#include 

#define NMAX 1000000
#define SALTATO -1

long numeri[NMAX+1];


int main()
{   
    long N;
     
    FILE* fin =fopen( "input.txt", "r");   
    FILE* fout=fopen("output.txt", "w");
   
    fscanf(fin, "%ld", &N);
    for(long i=1; i <= N; i++)
       	fscanf(fin, "%ld", &(numeri[i]));
    
    long E=N;
    long pos=1;
    while(numeri[pos] != SALTATO)
    {
    	long info=numeri[pos];
    	numeri[pos]=SALTATO;
    	E--;
    	pos=(pos+info)%N+1;    	
	}    
    fprintf(fout, "%ld\n", E);
    for(long i=1; i <= N; i++)
        if(numeri[i] != SALTATO)     
	        fprintf(fout, "%ld ", i);

    return 0;
}