# Problema Pacchetti corrotti

**URL:** <https://forum.olinfo.it/t/problema-pacchetti-corrotti/4708>\
**Category:** Aiuto\
**Created:** [9 Luglio 2017, 6:45am UTC](https://forum.olinfo.it/t/problema-pacchetti-corrotti/4708 "2017-07-09T06:45:09Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![DanMarz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e47c2d/32.png) [@DanMarz](https://forum.olinfo.it/u/DanMarz)\
**Post date:** [9 Luglio 2017, 6:45am UTC](https://forum.olinfo.it/t/problema-pacchetti-corrotti/4708/1 "2017-07-09T06:45:09Z")

</div>

Salve ragazzi sto cercando di risolvere il suddetto esercizio da qualche ora ma senza avere un esito favorevole. Vi allego il codice che ho sviluppato che però purtroppo non funziona.

```auto
#include <stdlib.h>
int P, M;
int p[10];
//(int *)malloc(1000*sizeof(int));

int mcd(int a, int b){
    int r;
    while(b){
         r = a%b;
         a=b; 
         b=r;
    }
    return a;
}

void inizializza(int current_P, int current_M) {
    // Salviamo P e M in due variabili globali.
    P = current_P;
    M = current_M;
}

int controlla(int checksum) {
    static int in=0;
    p[in++]=checksum; //non funziona
    for(int i=0; i<in; i++){
        printf("p[in]: %d\n", p[in]);
        printf("in: %d\n", in);
        if(mcd(p[in],checksum)!=1){
                return p[in];
        }
    }
    return 0;
}

```

Ho pensato di salvare i vari checksum che vengono passati alla funzione in un array globale e di utilizzare una variabile statica per memorizzare la lunghezza occupata dell’array. Il problema è che l’array che uso per salvare i checksum, cioè p, rimane sempre vuoto cioè tutti i valori risultano essere uguali a 0. Qui in basso vi allego l’output in relazione ad un esempio di input.

```
4 10

```

3 2 6 4  
p[in]: 0  
in: 1  
p[in]: 0  
in: 2  
p[in]: 0  
in: 3  
p[in]: 0  
in: 4  
0 0 0 0

Grazie per eventuali consigli su come risolvere il problema.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [13 Luglio 2017, 3:11pm UTC](https://forum.olinfo.it/t/problema-pacchetti-corrotti/4708/2 "2017-07-13T15:11:39Z")

</div>

Non ho ben capito come funziona il tuo codice, se vuoi [qua](https://github.com/lucach/abc/blob/master/2017/checksum/sol/naive.cpp) puoi trovare una versione funzionante simile alla tua.  
Comunque il tuo algoritmo ha complessità O(P^2) (se ti interessa puoi approfondire [qua](https://forum.olinfo.it/t/complessita-computazionale-di-abc-checksum/4670)) che è troppo elevata e ti darà al massimo 55 punti.  
Quindi ti consiglio di cercare una strategia diversa, oppure puoi guardare il [booklet](https://abc.chiodini.org/2017/booklet.pdf) con le soluzioni ufficiali.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [14 Luglio 2017, 10:17am UTC](https://forum.olinfo.it/t/problema-pacchetti-corrotti/4708/3 "2017-07-14T10:17:48Z")

</div>

> [@DanMarz](#):
>
> ```auto
> p[in++]=checksum; //non funziona
> for(int i=0; i&lt;in; i++){
> printf("p[in]: %d\n", p[in]);
> printf("in: %d\n", in);
> if(mcd(p[in],checksum)!=1){
> return p[in];
> }
> }
> 
> ```

In aggiunta alle risorse che ti ha segnalato @bortoz, l’errore è nel frammento di codice che ho riportato qua sopra. Nel ciclo accedi sempre alla posizione `in` (che indica invece il primo posto libero nel vettore), mentre dovresti accedere a tutte le posizioni `i` (con i \< in).