Mi mancano 20 punti al problema “gelati costosi”. La cosa strana è che la mia soluzione funziona per tutti i test-case dell’ultimo sub-task (con nessuna limitazione) e in nessun test-case del sub-task 2 (con N ridotto). Non penso che ci sia qualche problema nei casi di test. Resto in attesa di qualche suggerimento.
Il subtask 2 dice che tutti gli amici possono prestare la stessa somma (quindi che tutti i i valori P[i] sono uguali). Detto ciò, per aiutarti sarebbe utile vedere il tuo codice.
Ciao
Attenzione che nel sub-task 2 non è affatto garantita una riduzione di N e dal report si vede in effetti che non c’è.
Sorry. Si tratta del sub-task 3 e non il 2!
Sorgente:
#include <vector>
#include <algorithm>
using namespace std;
int presta(int N, int C, vector<int> P) {
// Inserisci il codice qui
//ordina il vettore P contenente i denari che l'i-esimo amico può prestare a Luca
//in base al loro poteziale presito
sort(P.begin(), P.end());
//crea un prefix_sum
vector<long long> S;
S.resize(N);
S[0]=P[0];
for (int i=1; i<N; i++) {
S[i]=S[i-1]+P[i];
}
//
if (S[N-1]<C) {
//gli amici non hanno abbastanza soldi da permettere a Luca di comprare il gelato
return 0; //nessun contribuente
}
if (S[N-1]==C) {
//tutti gli amici dovranno contribuire per permettere a Luca di comprare il gelato
return N; //tutti
}
//gli amici hanno insieme più denaro del costo del gelato
int contribuenti=0;
int resto=C;
int j=N-1;
while (resto>0) {
//vai indietro fino a trovare il contributo minimo >= al costo del gelato
bool trovato=false;
for (; j>=0 && !trovato; j--) {
if (P[j]<=C) {
trovato=true;
}
}
j++;
if (j>=0) {
if (P[j]==C) {
return 1;
} else { //se <
if (S[j]>=C) {
contribuenti++;
resto -= P[j];
} else {
//da qui fino al primo neanche se contribuissero tutti arriverebbe al costo del gelato
//Luca deve per forza chiedere al j+1-esimo amico un prestito (anche se > del costo del gelato)
return 1; //l'unico possibile
}
}
} else {
return 1; //l'unico possibile
}
}
return contribuenti;
}
Crdo tu abbia mal interpretato la consegna. Non chiede di trovare la minima somma >= a C ma il numero minimo di amici la cui somma sia >= a C.
Quindi si tratta di un problema greedy.
Matteo vuoi dire che con il seguente input:
5 7
1 1 2 3 5 10
l’output è 1 e non 2 (2+3)?
Credo che intendessi
6 5 → 6 amici e costo 5
1 1 2 3 5 10
Sì, l’output sarebbe 1 perché gli basta chiedere ad un amico ( P[4] o P[5] ) per avere una somma sufficiente a comprare il gelato.
Credo che il tuo esempio non fosse proprio efficace perché, secondo il modo in cui te l’hai inteso, la risposta poteva essere 1, chiedendo all’amico che gli dà 5 euro.
1 Mi Piace
Ho fatto 100. In effetti avevo interpretato male la traccia. Così diventa quasi banale.
Pensavo che i contributi degli amici dovevano possibilmente coincidere o avvicinarsi il più possibile al costo del gelato. Come problema sarebbe stato anche più interessante 
Thanks.
Questo esatto problema c’è sulla piattaforma e si chiama “Pranzo dalla nonna” (nonna):
https://training.olinfo.it/#/task/nonna/statement
Spoiler, la tua strategia risolutiva di prima non funziona, devi risolverlo tramite DP 
1 Mi Piace
Vero. Nonna risolto con DP infatti.