Problema "easy3"

Aiuto
1

Ciao a tutti,
ho difficoltà a raggiungere il punteggio massimo nel problema “easy3”…
non riesco a trovare la soluzione per ottenere anche gli ultmi 30 punti, infatti mi fermo sempre a 70/100.

In sintesi io calcolo le somme e, dopo aver controllato che sono numeri pari, le confronto con max che ho impostato a -1, ma con questo metodo risolutivo non raggiungo il punteggio pieno.

    max=-1;
    
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            if ((vettore[i]+vettore[j])%2==0&&(vettore[i]+vettore[j])>max)
                max=vettore[i]+vettore[j];
        }
    }

Qualcuno lo ha risolto e vuole aiutarmi?

2

Indizio: se invece di chiedere “la somma pari massima” il problema chiedesse semplicemente “la somma massima” di una coppia, potrebbe esserci una strategia più veloce di provare tutte le coppie? (se sì, prova a lavorare su tale idea in modo da farla funzionare per il caso richiesto dal testo, se no, altro indizio: conviene considerare solo la coppia “più promettente”)

3

100/100

Ho riordinato tramite un ‘sort’ il vettore e ho considerato solo le due possibili somme piu promettenti riuscendo cosi ad ottenere il punteggio massimo…

Grazie :wink:

1 Mi Piace
4

Di nulla :smile:

Tieni conto però che con l’ordinamento ottieni una soluzione O(n \log n), però è possibile risolvere il problema in O(n) e senza l’ordinamento :wink:

5

e come si fa senza ordinamento?

6

Scorri gli elementi una volta tenendoti i due numeri più grandi pari e i due numeri più grandi dispari

1 Mi Piace