# Per un pugno di baht. Sono troppo scarso

**URL:** <https://forum.olinfo.it/t/per-un-pugno-di-baht-sono-troppo-scarso/3904>\
**Category:** Aiuto\
**Created:** [22 Marzo 2015, 11:10am UTC](https://forum.olinfo.it/t/per-un-pugno-di-baht-sono-troppo-scarso/3904 "2015-03-22T11:10:50Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![xCoder](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/x/46a35a/32.png) [@xCoder](https://forum.olinfo.it/u/xCoder)\
**Post date:** [22 Marzo 2015, 11:10am UTC](https://forum.olinfo.it/t/per-un-pugno-di-baht-sono-troppo-scarso/3904/1 "2015-03-22T11:10:50Z")

</div>

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.

```auto
// 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 ;

}

```

---

<div class="post-metadata">

**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\
**Post date:** [22 Marzo 2015, 5:14pm UTC](https://forum.olinfo.it/t/per-un-pugno-di-baht-sono-troppo-scarso/3904/2 "2015-03-22T17:14:59Z")

</div>

(perdonami se questo suggerimento sarà abbastanza incomprensibile, l’ho risolto un sacco di tempo fa)  
Invece di provare tutti gli interi, prova invece a costruire la soluzione partendo dalle monete che hai

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [22 Marzo 2015, 8:25pm UTC](https://forum.olinfo.it/t/per-un-pugno-di-baht-sono-troppo-scarso/3904/3 "2015-03-22T20:25:34Z")

</div>

Diversi anni fa chiesi su codeforces una domanda su questo task, magari può tornarti utile la discussione: [http://codeforces.com/blog/entry/2046](http://codeforces.com/blog/entry/2046).