Lootboxes for loop

Aiuto
1

Ciao, scusate il titolo del topic poco informativo ma sono abbastanza confuso dal mio problema.
Non sto a specificare come sono arrivato ai codici ma non capisco come due codici che reputo essere equivalenti diano 65/100 e 100/100. (spoiler, per coloro che non l’hanno ancora risolto, provate prima di leggere la soluzione)
Questo codice fa 65/100

#include <stdio.h>
#include <assert.h>

// constraints
#define MAXN 5000
#define MAXX 10000

// input data
int N, X, i, j;
int P[MAXN], Q[MAXN];
int r[MAXX];
int oldR[MAXX];

int main() {
//  uncomment the following lines if you want to read/write from files
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    assert(2 == scanf("%d %d", &N, &X));
    for(i=0; i<N; i++)
        assert(2 == scanf("%d %d", &P[i], &Q[i]));

    // insert your code here
	for(i=0;i<N;++i){
		for(j=Q[i];j<=X;++j){
			if(P[i]+oldR[j-Q[i]]>r[j]){
				r[j] = P[i]+oldR[j-Q[i]];
			}
		}
		for(j=Q[i];j<=X;++j) oldR[j] = r[j];
	}
	
	
	/*for(i=0;i<=X;++i){
	}*/
	
    printf("%d\n", r[X]); // print the result
    return 0;
}

Mentre questo fa 100/100

#include <stdio.h>
#include <assert.h>

// constraints
#define MAXN 5000
#define MAXX 10000

// input data
int N, X, i, j;
int P[MAXN], Q[MAXN];
int r[MAXX];
int oldR[MAXX];

int main() {
//  uncomment the following lines if you want to read/write from files
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    assert(2 == scanf("%d %d", &N, &X));
    for(i=0; i<N; i++)
        assert(2 == scanf("%d %d", &P[i], &Q[i]));

    // insert your code here
	for(i=0;i<N;++i){
		for(j=Q[i];j<=X;++j){
			if(P[i]+oldR[j-Q[i]]>r[j]){
				r[j] = P[i]+oldR[j-Q[i]];
			}
		}
		for(j=Q[i];j<=X;++j) oldR[j] = r[j];
	}
	
	
	for(i=0;i<=X;++i){
	}
	
    printf("%d\n", r[X]); // print the result
    return 0;
}

E l’unica cosa che cambia è il ciclo for alla fine. Non capisco come quel ciclo possa modificare il punteggio che riesco a fare?

2

Ho provato ora a submittarli e fanno entrambi 65/100, ma aumentando la dimensione degli array mi da 100/100, probabilmente c’e’ un out of bounds da qualche parte, che provoca l’undefined behaviour.

1 Mi Piace
3

Strano che ti vengano entrambi 65/100. Tra prima e adesso penso che ho sottomesso entrami 3-4 volte e davano sempre o 65 o 100.
In effetti bastava modificare la lunghezza del vettore. Il testo originale non dava il MAXX e aggiungendolo mi era sfuggito questo particolare, ora funziona correttamente(la X massima è 10’000 ma siccome conto anche lo 0 diventa 10’001). Comunque rimane ancora un mistero come quel ciclo salvasse il programma ahah