Ciao a tutti, ho bisogno di aiuto per risolvere il problema Pranzo dalla nonna.
Tutti i testcase sono corretti tranne il primo della seconda subtask (testcase 002). Il problema è che il margine (nel mio caso 100000) è troppo basso per quel testcase e se lo alzo troppo risolve il testcase 002 ma va in TLE per gli ultimi testcase.
Ecco il mio codice:
#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
#define MAXSOMMA MAXN * MAXP
long long mangia(int N, int K, vector<int> P) {
//sort(P.begin(), P.end(), greater<int>());
bool pesi[MAXK +100001] = {false};
pesi[0] = true;
for (int i = 0; i < N; i++) {
for (int j = K+100000; j >= P[i]; j--) {
if (pesi[j - P[i]] == true) {
pesi[j] = true;
}
}
}
for (int maxP = K; maxP <= K+100000; maxP++) {
if (pesi[maxP] == true) {
return maxP;
}
}
return 0;
}
vector<int> P(MAXN);
int main() {
FILE *fr, *fw;
int N, K, i;
/*cin>>N>>K;
for(i=0; i<N; i++)
cin>>P[i];
cout<<mangia(N, K, P);*/
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%d", &P[i]));
fprintf(fw, "%d\n", mangia(N, K, P));
fclose(fr);
fclose(fw);
return 0;
}
Ciao, combinare i piatti che pesano piu di K può essere utile ad esempio nell’ultimo testcase (fornito tra gli allegati del problema) dove tutti i valori sono maggiori di K. Bisogna comunque prenderne uno (quello più vicino a K, nel caso dell’ultimo testcase 5600). Grazie della risposta
#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000
#define MAXSOMMA MAXN * MAXP
long long mangia(int N, int K, vector<int> P) {
int min = *min_element(P.begin(), P.end());
if(min >= K){
return min;
}
bool pesi[MAXK +100001] = {false};
pesi[0] = true;
for (int i = 0; i < N; i++) {
for (int j = K+100000; j >= P[i]; j--) {
if (pesi[j - P[i]] == true) {
pesi[j] = true;
}
}
}
for (int maxP = K; maxP <= K+100000; maxP++) {
if (pesi[maxP] == true) {
return maxP;
}
}
return 0;
}
vector<int> P(MAXN);
int main() {
FILE *fr, *fw;
int N, K, i;
/*cin>>N>>K;
for(i=0; i<N; i++)
cin>>P[i];
cout<<mangia(N, K, P);*/
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &K));
for(i=0; i<N; i++)
assert(1 == fscanf(fr, "%d", &P[i]));
fprintf(fw, "%d\n", mangia(N, K, P));
fclose(fr);
fclose(fw);
return 0;
}
Ora effettuo un controllo sull’elemento minimo di P e, se maggiore o uguale di K, lo restituisco direttamente senza ulteriori cicli. Nonostante ciò il testcase 002 continua a non funzionare.
L’idea e’ che se un insieme S di piatti ha portata P \geq K , allora non ha senso combinarlo con altri piatti, perche’ la portata del nuovo insieme di piatti S' sara’ una risposta sicuramente peggiore di P.
Continuo a non capire come risolvere il problema dell’unico testcase dove l’output non è corretto, in quanto (almeno da ciò che ho testato) non si tratta di un problema logico del programma. In teoria l’errore è causato dal numero enorme di piatti fornito in input in quel testcase, infatti se al posto di 100000 inserisco 300000 l’output è corretto per il testcase 002. Avete qualche consiglio su come aumentare il margine (attualmente di 100000) senza andare in TLE per gli ultimi testcase? Grazie dell’aiuto e scusate per l’insistenza.
Il test case 2 fa parte del subtask2 dove N<=10, ma la min_element lavora su un vector da 5000 elementi.
Con
int min = *min_element(P.begin(), P.begin()+N);
tutto si sistema.
Non era più per la risposta diretta ma le implicazioni che ne derivano.
Tutte le somme maggiori di K possono essere ignorante (per cui iterare dalla somma massima raggiungibile è inutile).
Sapendo che le somme utili sono tutte minore di K, ha senso iterare da 0 fino a K. Dovresti riformulare un’altro modo di per creare le combinazioni.
In questo modo ottieni una soluzione O(NK) \approx O(10^6) che entra ampliamente nei limiti di tempo invece di una O(NP) \approx O(10^9).
Vedi come si comporta la tua soluzione per il caso in cui N = 5000, K = 5000 e P_i=1 .
