Accensione dei PC

Alle OII, gli N computer dei partecipanti sono numerati da 1 a N.
Al momento solo alcuni di essi sono accesi, e Gabriele deve accenderli tutti prima dell’inizio della gara!
Sfortunatamente, l’accensione e lo spegnimento dei computer può avvenire solamente attraverso un sofisticato sistema di pulsanti.
Nella Sala Controllo vi sono infatti N pulsanti, anch’essi numerati da 1 a N.
Il pulsante K ha, come effetto, quello di cambiare lo stato di tutti i computer il cui numero identificativo sia un divisore di K.
Ad esempio, il pulsante 12 cambia lo stato dei computer 1, 2, 3, 4, 6, 12.
Ogni pulsante può essere premuto al massimo una volta, ed è necessario premere i pulsanti in ordine crescente (non si può premere il pulsante K1 dopo aver premuto il pulsante K2, se K1 < K2).
Un computer può venire acceso e/o spento anche varie volte; l’importante è che alla fine tutti i computer risultino accesi.
Sapendo quali sono i computer inizialmente accesi, dovete decidere quali pulsanti premere in modo da accenderli tutti.
Ad esempio, supponiamo che i computer siano N=6.
Ci sono quindi N=6 pulsanti, che cambiano lo stato dei computer secondo la tabella seguente.

(…)

Scarica il testo originale in PDF.


La funzione richiesta (ottiene il 77% del punteggio…)

#include 

void Accendi(int N, int acceso[], int pulsante[]) 
{ 
    int i, j, jj, ultimo; 
    for(i=N; i >= 1; i--) 
        if(!acceso[i]) 
        {  
            pulsante[i]=1; 
            ultimo=(int)sqrt(i);
            for(j=1; j <= ultimo; j++) 
               if(i%j == 0) 
               { 
                   jj=i/j; 
                   acceso[j ]=!acceso[j ]; 
                   acceso[jj]=!acceso[jj]; 
               }  
            if(ultimo*ultimo == i) 
               acceso[ultimo]=!acceso[ultimo]; 
        } 
}

grader.cpp ufficiale

#include  
#include  
#define MAXN 1000000 
static FILE *fr, *fw; 
static int N; 
static int acceso[MAXN + 1], pulsante[MAXN + 1]; 
void Accendi(int N, int acceso[], int pulsante[]); 

int main() { 
   int i; 
   fr = fopen("input.txt", "r"); 
   fw = fopen("output.txt", "w"); 
   assert(1 == fscanf(fr, "%d", &N)); 
   for (i=1; i<=N; i++) 
      assert(1 == fscanf(fr, "%d", acceso + i)); 
   Accendi(N, acceso, pulsante); 
   for (i=1; i<=N; i++) { 
      if (i > 1) fprintf(fw, " "); 
          fprintf(fw, "%d", pulsante[i]); 
   } 
   fprintf(fw, "\n"); 
   return 0; 
}