# Piastrelle. Solo 5 punti

**URL:** <https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794>\
**Category:** Aiuto\
**Created:** [25 Aprile 2014, 9:42pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794 "2014-04-25T21:42:26Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [25 Aprile 2014, 9:42pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/1 "2014-04-25T21:42:26Z")

</div>

Qualcuno riesce a capire perché mi da solo 5 punti nonostante l’algoritmo sembri giusto?

```
#include \<fstream\>  
  
#include \<algorithm\>  
  
#include \<vector\>  
  
using namespace std;

int N;  
vector\<int\> p;

int main(){  
 ifstream in("input.txt");  
 in \>\> N;  
 in.close();  
  
 ofstream out("output.txt");  
 for(int cont=0, i; cont\<=(N/2); cont++){  
 p.resize(N-cont);  
 for(i=0; i\<N-(cont\*2); i++)  
 p[i]=1;  
 for( ; i\<N-cont; i++)  
 p[i]=2;

do{  
 for(int i=0; i\<p.size(); i++)  
 out \<\< ((p[i]==1)?"[O]":"[OOOO]");  
 out \<\< "\n";  
 }while(next\_permutation(p.begin(), p.end()));  
 }  
 out.close();  
 return 0;  
}
```

---

<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:** [25 Aprile 2014, 10:02pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/2 "2014-04-25T22:02:17Z")

</div>

Beh, almeno esponi a parole l’algoritmo 😛

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [25 Aprile 2014, 10:05pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/3 "2014-04-25T22:05:31Z")

</div>

Ma perchè non fate una banale ricorsiva? 😃

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [25 Aprile 2014, 10:07pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/4 "2014-04-25T22:07:39Z")

</div>

Giusto scusami. Praticamente cont contiene il numero progressivo di piastrelle larghe 2. Quindi ad ogni passo del ciclo (il quale durerà fino a quando le piastrelle larghe 2 non saranno la metà di N) riempio il vettore con (N-cont\*2) x 1 e cont x 2, ne analizzo tutte le permutazioni e le stampo. Con input di esempio e altri di prova funziona. Sul correttore invece mi prende il primo subtask e tutti quelli del secondo tranne uno. Poi nessuno di tutti gli altri.

---

<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:** [25 Aprile 2014, 10:11pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/5 "2014-04-25T22:11:58Z")

</div>

quindi per il tuo algoritmo questo:

```
[0000][0][0][0]
```

“viene prima” di:

```
[0][0000][0000]
```

?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [25 Aprile 2014, 10:17pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/7 "2014-04-25T22:17:44Z")

</div>

Secondo il mio algoritmo si… Appena posso faccio la procedura ricorsiva ahahah

---

<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:** [25 Aprile 2014, 10:19pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/8 "2014-04-25T22:19:11Z")

</div>

Non che sia strettamente necessaria eh! Puoi ad esempio aggiungere tutte le piastrellature in un vettore (invece di stamparle direttamente). Lo ordini. Lo stampi tutto 🙂  
  
Nel caso prova a risolverlo in entrambi i modi e vedi quale va più veloce (beh… :P)

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [25 Aprile 2014, 10:21pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/9 "2014-04-25T22:21:22Z")

</div>

Era come volevo farlo all’inizio ma poi pensavo che fosse una perdita di tempo. Non avevo capito bene come ordinare le sequenze

---

<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:** [25 Aprile 2014, 10:27pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/10 "2014-04-25T22:27:53Z")

</div>

Uhm… tecnicamente potresti tenerle come stringhe e ordinare l’array di stringhe (vector\<string\>) l’unico problema è che i separatori ‘[’ e ‘]’ hanno un valore ASCII maggiore di ‘0’. Potresti sostituirli con ‘(’ e ‘)’, ordinare l’array, stamparlo ri-sostituendo le parentesi… 🙂

---

<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:** [25 Aprile 2014, 10:31pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/11 "2014-04-25T22:31:18Z")

</div>

Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [25 Aprile 2014, 10:34pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/12 "2014-04-25T22:34:39Z")

</div>

> Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]
> 
> Degiac

È esattamente quello che ho fatto.
Comunque faccio qualche prova e vi faccio sapere ;)

---

<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:** [25 Aprile 2014, 10:35pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/13 "2014-04-25T22:35:23Z")

</div>

> Oppure puoi usare un vettore di interi (1 e 2) e quando stampi sostituisci 1 con [O] e 2 con [OOOO]
> 
> Degiac

Sì ma dovresti comunqe sapere «come ordinare le sequenze» (ad esempio passando a sort una funzione di compare, oppure definendo un operatore "minore" tra i vector). Con le stringhe chiamerebbe solo sort (non che io consigli di farlo... è bruttissimo :P... molto meglio ordinare i vector in questo caso)

---

<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:** [25 Aprile 2014, 10:40pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/14 "2014-04-25T22:40:18Z")

</div>

Rettifico, a quanto pare vector\<\> definisce già i suoi bei operatori \<, \<=, \>, etc… [http://en.cppreference.com/w/cpp/container/vector/operator\_cmp](http://en.cppreference.com/w/cpp/container/vector/operator_cmp)  
  
Quindi puoi chiamare sort su un vector di vector senza problemi 🙂

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [26 Aprile 2014, 11:46am UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/15 "2014-04-26T11:46:16Z")

</div>

Ordinando il vector di vector da 100/100, grazie 😉

---

<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:** [26 Aprile 2014, 11:54am UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/16 "2014-04-26T11:54:01Z")

</div>

Ottimo. Adesso se vuoi prova ad implementare anche la versione ricorsiva 🙂 quella di cui parlava @mark03

---

<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:** [26 Aprile 2014, 1:17pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/17 "2014-04-26T13:17:23Z")

</div>

> Ordinando il vector di vector da 100/100, grazie ;)
> 
> Lawliet

Tra l’altro ho notato che nella tua ultima sottoposizione per ordinare il vector\<vector\> passi una funzione di compare, questo non è strettamente necessario (come ho scritto in un commento poco sopra) dal momento che la classe vector ha gli operatori di confronto già definiti (\<, \<=, \>, etc…) quindi se hai due vector v1 e v2 e fai la cosa seguente:

```
if (v1 < v2) {
…
}
```

automaticamente verrà fatta la cosa giusta (internamente, verrà chiamata lexicographical\_compare). Quindi puoi fare sort senza passare alcuna funzione di compare 🙂

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [26 Aprile 2014, 3:06pm UTC](https://forum.olinfo.it/t/piastrelle-solo-5-punti/3794/18 "2014-04-26T15:06:23Z")

</div>

> > Ordinando il vector di vector da 100/100, grazie ;)
> > 
> > Lawliet
> 
> Tra l’altro ho notato che nella tua ultima sottoposizione per ordinare il vector\<vector\> passi una funzione di compare, questo non è strettamente necessario (come ho scritto in un commento poco sopra) dal momento che la classe vector ha gli operatori di confronto già definiti (\<, \<=, \>, etc…) quindi se hai due vector v1 e v2 e fai la cosa seguente:
> 
> ```
> if (v1 < v2) {
> …
> }
> ```
> 
> automaticamente verrà fatta la cosa giusta (internamente, verrà chiamata lexicographical\_compare). Quindi puoi fare sort senza passare alcuna funzione di compare 🙂
> 
> wil93

Capito 🙂

Grazie per la disponibilità. Quando avrò un po’ di tempo implementerò la funzione ricorsivamente!