Ois_muffin(rischiesta aiuto)

Aiuto
1

qualcuno gentilmente può spiegarci per quale motivo, nonostante il programma funzioni con i file input e output, il compilatore del sito dice che non funziona? Il problema è Muffin, e in seguito il nostro programma:

#include <stdio.h>
#include <assert.h>
#define MAXN 1000000
int N, K, i;
int T[MAXN];
int somTmp=0;
int som = 0;

int main() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

    assert(2 == scanf("%d %d", &N, &K));
    for (i = 0; i < N; i++)
        assert(1 == scanf("%d", &T[i]));   
    int s = K;  
    for (i = 0; i <= N-s; i++)
    {
	  somTmp =0;
      for(int j = i; j < K; j++)
      { 		
		 somTmp += T[j];
	  }
	  K++;
	  if (som < somTmp)
	      som = somTmp;  
    }
    printf("%d\n", som); 
    return 0;
}
2

L’ esercizio richiede di trovare la belezza massima di K elementi consecutivi.
La belezza è data dalla somma degli elementi consecutivi presenti in un insieme.
Quello che stai cercando di fare è calcolare tutti gli insiemi possibili in modo tale da salvare la somma massima, ma lo stai facedo in modo errato.

K rimane una costante, quindi j deve ciclare partendo da i cioé la posizione attuale fino a i + K che sarebbe la posizione finale del inisieme che stai considerando.
Guardando le assunzioni noterai che la belezza può essere negativa e quindi impostare la bellezza massima a 0 è un errore. Prova a considerare questo caso :

5 3 
-1 -1 -1 -1 -1

output :
-3
Una volta fatti questi accorgimenti dovresti riuscire a ottenere 60/100, per il 100 su 100 devi trovare una soluzione più veloce.
Attualmente la complessita del tuo algoirmto è O(N * K), dovresti riuscire a trovare una soluzione O(N).
Prova a stampre le somme di tutti gli insiemi possibili, cosa noti ?

3

Cosa intendi per " il tuo algoritmo è O(N∗K) e dovresti riuscire a trovare una soluzione O(N)" ?
Ottengo 60 ma non capisco perchè

4

Che l’ algoritmo per ogni insieme continuo di K elementi si ricalcola la somma.
Questa soluzione è troppo lenta per N <= 1 000 000.
Dovresti calcolare la somma senza riesaminare K elementi.
In poche parole dovresti ciclare una sola volta su tutto il vettore.

5

Il modo più semplice per capirlo è: scrivi 15 numeri e calcolare la somma degli insiemi di lunghezza 6 e guarda quale ragionamento fai manualmente.

2 Mi Piace