Output non corretto su Greedy Santa, subtask non valide quando dovrebbero


#1

Salve ragazzi! Ultimamente ho alcuni problemi con la sottposizione e la valutazione sulla piattaforma… Oggi in particolare sto provando a risolvere greedy santa, ma ritorna errata la subtask di esempio nr 001, che richiede output 10. Provando in locale, ottengo come risultato 10, ma il grader non ne vuole sapere. Come potrei fare a risolvere? Allego codice per ulteriori chiaramenti

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int nRegali;
int budget;
int santa[100];

int greedySanta(int nRegali){
	
	int somma = 0;
	
		
	for(int i=0; i<nRegali; i++){
		for(int j=0; j<nRegali; j++){
			somma = (santa[i] + santa[j]);
			
			
			if(somma >= budget){
				return max(somma, greedySanta(nRegali-1));
			}
		}
	}
	
}

int main(){
		
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	int budgetMax;
	
	in >> nRegali;
	in >> budget;
	
	for(int i=0; i<nRegali; i++){
		in >> santa[i];
	} 
	
	for(int i=0; i<nRegali; i++){
		budgetMax += santa[i];
	}
	
	if(budgetMax < budget){
		if(budgetMax == budget){
			out << budget;
		}
		out << budgetMax;
	} else out << greedySanta(nRegali);
	
	
	
}

#2
int greedySanta(int nRegali){
	
	int somma = 0;
	
		
	for(int i=0; i<nRegali; i++){
		for(int j=0; j<nRegali; j++){
			somma = (santa[i] + santa[j]);
			
			
			if(somma >= budget){
				return max(somma, greedySanta(nRegali-1));
			}
		}
	}
}

Manca il valore di return nel caso in cui non vengano trovati 2 regali che sommati superino il budget, di conseguenza non è detto che il tuo compilatore restituisca lo stesso valore restiruito dal compilatore del server.

Il testcase è corretto sulla piattaforma, inviando un codice che stampa solamente 10 quel caso risulta corretto.

Inoltre a prescindere dalla logica del tuo programma c’è un’istruzione che per come è scritta è inutile:

	1)if(budgetMax < budget){
		2)if(budgetMax == budget){
			out << budget;
		}
		out << budgetMax;
	} else out << greedySanta(nRegali);

La condizione 1) implica che la condizione 2) non sia mai verificata.

Fabio.


#3

Ok, grazie mille per avermi spiegato il problema, domani cerco di risolvere insieme alla svista degli if…