# Ois\_pesci 10/100

**URL:** <https://forum.olinfo.it/t/ois-pesci-10-100/4734>\
**Category:** Aiuto\
**Created:** [26 Luglio 2017, 9:31pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734 "2017-07-26T21:31:38Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [26 Luglio 2017, 9:31pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/1 "2017-07-26T21:31:38Z")

</div>

Salve a tutti,  
Ho provato a risolvere l’algoritmo dell’esercizio " pesci mangioni " ma ottengo solo 3 output corretti e il 10/100 del punteggio.  
Qui trovate il codice : [https://pastebin.com/LcHhDaKS](https://pastebin.com/LcHhDaKS).  
Grazie 🙂

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [26 Luglio 2017, 10:45pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/2 "2017-07-26T22:45:26Z")

</div>

Se non ho capito male tu quando trovi 2 pesci adiacenti che nuotano in direzione opposta elimini il più piccolo, ma se quello più a sinistra dei due si muove verso sinistra e quello più a destra va verso destra, vanno in direzioni diverse eppure non si mangiano 🙂

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [26 Luglio 2017, 11:29pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/3 "2017-07-26T23:29:38Z")

</div>

Quando usi la funzione `erase` elimini un elemento e quindi la dimensione del `vector` si riduce, però tu vai a chiamare elementi che non dovrebbero esistere.  
Un modo per risolvere sarebbe sostituire nel for `i<N` con `i<j` e ogni volta che elimini un elemento decrementare `i`.  
Tuttavia la funzione `erase` ha complessità \mathcal O(N) e quindi la soluzione finale diventa \mathcal O(N^2) che -teoricamente- dovrebbe andare fuori tempo.  
Prova a pensare un modo per cancellare un elemento in \mathcal O(1).

Se lo cancellellassi dal fondo o dalla cima?

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [27 Luglio 2017, 12:19pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/4 "2017-07-27T12:19:57Z")

</div>

Ho cambiato l’if della direzione in questo modo:  
`if(direzione[i] != direzione[i-1] && (direzione[i] != 0 && direzione[i-1] != 1)) { ... }`  
E la condizione di uscita del ciclo da `i<N` a `i<j` pero’ ottengo qualche output corretto in piu’ nel 2 subtask, ma ottengo sempre il 10/100.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [27 Luglio 2017, 12:40pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/5 "2017-07-27T12:40:01Z")

</div>

Come ho già detto prima, anche se l’algoritmo fosse giusto andrebbe fuori tempo, quindi prova a cambiare strategia.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [27 Luglio 2017, 8:22pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/6 "2017-07-27T20:22:00Z")

</div>

Sei sicuro che basti una passata? Prova a simulare, anche se comunque effettivamente il tuo approccio è troppo lento

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [27 Luglio 2017, 9:31pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/7 "2017-07-27T21:31:13Z")

</div>

Voi come l’avete fatto ?

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [27 Luglio 2017, 9:53pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/8 "2017-07-27T21:53:28Z")

</div>

L’ideale sarebbe quello di usare una pila scorrendo i pesci verso destra, se i pesci vanno verso destra li aggiungi, altrimenti elimini dalla cima finché i pesci non si sono mangiati a vicenda seguendo le regole. La risposta del problema è la dimensione della pila. Le funzioni `pop` e `push` sono entrambe costanti, quindi la soluzione finale diventa \mathcal O(N).

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [27 Luglio 2017, 10:05pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/9 "2017-07-27T22:05:39Z")

</div>

Io ci avevo ragionato qualche giorno fa, ma non ho avuto voglia di implementarlo , ma l’avevo ragionato così:

Nel caso in cui il pesce più a sinistra va a sinistra lo tolgo e aggiungo a quelli che rimarranno, stessa cosa per quello verso destra.  
Se i 2 più verso sinistra vanno verso destra ed è più piccolo dei due il più verso sinistra allora quel pesce avrà la stessa sorete del secondo e quindi è come se il secondo valese 2 pesci  
Se invece il più a sinistra va verso destra e il secondo più a sinistra va verso sinistra elimino il più piccolo se invece sia il più a sinistra che il secondo più a sinistra vanno verso destra e il più a sinistra è più grande allora sposto il ragionamento sul secondo

Spero di non aver fatto confusione

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Luglio 2017, 12:22pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/10 "2017-07-28T12:22:29Z")

</div>

L’idea mi sembra ottima…  
Il codice andrebbe fatto così ? ([https://pastebin.com/urAcnGyD](https://pastebin.com/urAcnGyD))

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [28 Luglio 2017, 12:56pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/11 "2017-07-28T12:56:44Z")

</div>

Ti manca la parte in cui i pesci si mangiano a vicenda.  
Se il pesce va verso destra lo aggiungo alla pila e fin qua è chiaro, se va verso sinistra devo controllare quanti pesci riesce a mangiare prima di essere mangiato a sua volta o di aver mangiato tutti i pesci della pila.  
Quando capisci il concetto l’implementazione risulta semplice.

> L’array direzione, indicizzato da 0 a N − 1, indica se l’i−esimo pesce nuota da sinistra verso destra (direzione[i]= 0) o da destra verso sinistra (direzione[i]= 1).

Fai attenzione a destra e sinistra.

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Luglio 2017, 3:13pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/12 "2017-07-28T15:13:30Z")

</div>

Non avendo mai usato una pila in c++, non riesco a fare la parte del codice in cui va verso sinistra…

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [28 Luglio 2017, 3:49pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/13 "2017-07-28T15:49:55Z")

</div>

La pila è piuttosto semplice da usare.  
Ha due operazioni in \mathcal O(1) aggiungere un elemento alla cima (`push`) e rimuovere un elemento dalla cima (`pop`), inoltre si può accerere solo all’elemento in cima (`top`). Queste tre funzioni sono sufficienti per risolvere il problema.  
Ecco un esempio:

```auto
stack<int> s;
s.push(3);
s.push(2);
s.push(5);
cout << s.top(); // 5
s.pop();
cout << s.top(); // 2

```

Se preferisci puoi usare al posto della pila un vector basta sostituire le funzioni: `push` -\> `push_back`, `pop` -\> `pop_back` e `top` -\> `back` e il funzionamento è identico.

Detto questo, quando trovi un pesce P\_i che va a sinistra devi eliminare il pesce in cima fino a quando quest’ultimo è più grande di P\_i oppure la pila è vuota (ricordati che se la pila è vuota devi aggiungere il pesce P\_i alla pila poiché non viene mangiato da nessuno), è piuttosto semplice.

---

<div class="post-metadata">

**Author:** ![Think.Different](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/ea5d25/32.png) [@Think.Different](https://forum.olinfo.it/u/Think.Different)\
**Post date:** [28 Luglio 2017, 7:13pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/14 "2017-07-28T19:13:01Z")

</div>

Grazie delle spiegazioni… sei stato molto gentile…  
Per caso intendi questo " [https://pastebin.com/pLLPwvNs](https://pastebin.com/pLLPwvNs) " ?

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [28 Luglio 2017, 8:42pm UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/15 "2017-07-28T20:42:25Z")

</div>

Sei sulla giusta strada! 😉  
Basta qualche piccola correzione:

- All’interno del for manca l’else

- `s.top() > dimensione[i]` dovrebbe essere minore e non maggiore

- Non consideri il caso in cui all’interno della pila vi siano pesci che vanno verso sinistra, poiché un pesce che arriva da sinistra, se è più grande se lo mangerebbe.

I primi due punti sono semplici da correggere, per l’ultimo è un po’ più complicato, ci sono essenzialmente 3 modi per risolverlo:

- Eviti di aggiungere i pesci che vanno verso sinistra e utilizza un’altra variabile (per esempio `j`) per tenerti conto di questi pesci e la soluzione diventerebbe `s.size() + j`

- Utilizzi uno stack di pair

- Ti crei la tua struttura dati

L’ultima scelta è la più complessa, ma risulta davvero utile negli esercizi più difficili, diventa una cosa di questo tipo:

```auto
struct pesce{
	int peso; //dimesione
	int verso; //direzione
};

```

Se usi invece la prima soluzione devi stare attento ad una cosa: quando chiami `s.top()` e la pila è vuota ti dà errore, un modo per correggere è inserire un numero molto grande all’inizio (come può essere `INT_MAX` della libreria `<climits>`) e invece di utilizzare `s.empty()` utilizzi `s.size() == 1` e poi alla fine decrementi il totale di 1. E’ più complicato di quel che pensavo quindi se non hai voglia di provare da solo e per non tirare troppo avanti l’argomento ecco qua:

```auto
stack<int> s;
int j = -1;
s.push(INT_MAX);
for(int i=0; i<N; i++)
{
	if (direzione[i] == 1)
	{
		while (s.top() < dimensione[i])
			s.pop();
		if (s.size() == 1)
			j++;
	}
    else
        s.push(dimensione[i]);
}
return s.size() + j;

```

Se non riesci a copiare vai [qua](https://pastebin.com/YqxAjq9e).  
Se invece desideravi trovare una soluzione con la struttura dati te la lascio [qua](https://pastebin.com/GRdmYhZY).  
Spero di essere stato utile e chiaro, questo problema era un po’ particolare, spero che almeno hai capito il concetto che c’era dietro la soluzione e se hai qualche domanda chiedi pure 🙂

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [29 Luglio 2017, 10:51am UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/16 "2017-07-29T10:51:33Z")

</div>

Volevo provare la tua soluzione ma molti dei subtask risultano sbagliati, con “Execution killed with signal 11 (could be triggered by violating memory limits)”, non riesco a capire dove è l’errore visto che quando esegui l’istruzione pop verifichi prima che lo stack non sia vuoto

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [29 Luglio 2017, 10:53am UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/17 "2017-07-29T10:53:02Z")

</div>

Ho provato le soluzioni e funzionavano 😄  
EDIT: no hai ragione tu, devo aver confuso un po’ di cose, il problema è qua:  
`while (s.top().peso < dimensione[i] && !s.empty() && s.top().verso == 0)`  
quando accedi a `top` se è vuoto ti dà errore, il problema è che tu controlli se è vuoto dopo avere chiamato `top`, così dovrebbe funzionare:  
`while (!s.empty() && s.top().peso < dimensione[i] &&s.top().verso == 0)`

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [29 Luglio 2017, 11:05am UTC](https://forum.olinfo.it/t/ois-pesci-10-100/4734/18 "2017-07-29T11:05:51Z")

</div>

> [@bortoz](#):
>
> quando accedi a top se è vuoto ti dà errore, il problema è che tu controlli se è vuoto dopo avere chiamato top,

Non avevo fatto caso all’ordine 😉