# Mazzi di carte (itday\_carte)

**URL:** <https://forum.olinfo.it/t/mazzi-di-carte-itday-carte/8857>\
**Category:** Aiuto\
**Created:** [14 Maggio 2024, 4:06pm UTC](https://forum.olinfo.it/t/mazzi-di-carte-itday-carte/8857 "2024-05-14T16:06:18Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![ByteBusters](https://forum.olinfo.it/user_avatar/forum.olinfo.it/bytebusters/32/2470_2.png) [@ByteBusters](https://forum.olinfo.it/u/ByteBusters)\
**Post date:** [14 Maggio 2024, 4:06pm UTC](https://forum.olinfo.it/t/mazzi-di-carte-itday-carte/8857/1 "2024-05-14T16:06:18Z")

</div>

Ciao a tutti!

Pensando al problema, non mi sembra ci possa essere un modo facile di prevedere qual’è la scelta di carte da fare in un dato istante, quindi l’ho risolto tramite back-tracking.

Il codice:

```auto
int solve(int N, int K, vector<vector<int>> decks, int max_pick) {
    int res = 0;
    for (vector<int> &deck: decks) {
        if (deck.empty()) {
            continue;
        }
        int last_element = deck.back();
        deck.pop_back();

        if (last_element > max_pick) {
            res = max(res, 1 + solve(N, K, decks, last_element));
        } else {
            res = max(res, solve(N, K, decks, max_pick));
        }

        deck.push_back(last_element);
    }
    return res;
}

int gioca(int N, int K, vector<vector<int>> decks) {
    for (vector<int> &deck: decks) {
        reverse(deck.begin(), deck.end());
    }

    return solve(N, K, decks, 0);
}

```

Ho invertito i vettori, solo per poter aggiungere/togliere dalla fine un elemento senza dover shiftare tutto il vettore.

A parte i primi 3 test, ottengo solo:

> Execution killed (could be triggered by violating memory limits)

Immagino perché la chain-call sia troppo lunga…

Se già così fallisce i test per i limiti di memoria, immagino che aggiungere la memoizzazione non sia la strada giusta.

Vi chiedo un consiglio su come rivedere la soluzione.

Del pruning basterebbe?

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [15 Maggio 2024, 11:26am UTC](https://forum.olinfo.it/t/mazzi-di-carte-itday-carte/8857/2 "2024-05-15T11:26:32Z")

</div>

A cosa ti servirebbe memoizzare se tanto gli stati sono K^N?  
Comunque, [con le dovute eccezioni](https://training.olinfo.it/#/task/ois_coordonate/statement), i problemi non sono fatti per essere risolti con pruning/branch&bound, quindi se ti sembra che questa sia l’unica via probabilmente ti mancano delle osservazioni importanti.