Salve ragazzi, ancora problemi in quanto a tempi di esecuzione :(. Il problema è “Per un pugno di baht” (per chi non lo ricordasse in pratica ti viene dato uno o più vettori di interi e bisogna elaborare il minimo intero che non è ottenibile come somma di sottovettori per ogni vettore (spero di essermi spiegato bene)). Ad ogni modo il mio codice supera il primo test impiegando 0.003 s però gli altri non li supera in quanto impiega qualcosa come 6 secondi O.o ! Vi spiego brevemente cosa fa il mio codice…
Prende in input il vettore da esaminare e lo ordina in modo decrescente, a questo punto per ogni intero da esaminare “taglia” ogni volta gli interi che sono più grandi del numero da esaminare , prendendo prima il più grande intero minore uguale all’intero da esaminare e così via. Appena l’intero da esaminare diventa 0 significa che il numero da esaminare all’inizio è ottenibile come somma di qualche sottovettore del vettore iniziale. Il primo intero che non riesce a esprimere come somma di qualche sottovettore ovviamente è la risposta al problema.
Ora chiedo a voi come posso farlo per farlo stare sotto sti cavoli di 5 secondi. E io che pensavo fossero tanti.
Grazie in anticipo ragazzi.
// Per un pugno di Baht (selezione nazionale)
#include <fstream>
#include <iostream>
#include <math.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
typedef long long ll;
typedef long int li;
#define MAX 100000
typedef vector<li> V;
li N ;
bool trv = false;
void conto(li num, V v1,li ind)
{
if (num==0)
{
trv=true;return;}
V v = v1;
if (ind!=-1)
v.erase(v.begin(),v.begin()+ind+1); // tolgo elementi superflui
for (li i = 0; i<v.size() && !trv; i++)
{
if (v[i]<=num)
conto(num-v[i],v,i);
}
}
bool myF(li i, li y){return (i>y);}
int main() {
in >> N ;
li x ;
for (int i = 0; i < N ; i++)
{
V v; // dichiaro il vettore che contiene i valori da leggere
in >> x ;
for (int i = 0; i < x ; i++)
{
li y ; in >> y ;
v.push_back(y);
}
sort(v.begin(),v.end(),myF); // ordino il vettore
li num = 1;
for (trv=true ; trv ; num++)
{
trv = false;
conto(num,v,-1);
}
out << num-1 << endl ;
}
in.close();
out.close();
return 0 ;
}