# Aiutino per Olympic Pizza

**URL:** <https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836>\
**Category:** Aiuto\
**Created:** [17 Agosto 2014, 3:04pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836 "2014-08-17T15:04:52Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [17 Agosto 2014, 3:04pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/1 "2014-08-17T15:04:52Z")

</div>

Sto cercando di risolvere questo problema, ma faccio solo 70/100  
  
Questo è più o meno l’algoritmo:

```
void Order(int N, int *A) {
if(is_cookable(N, A)) {
cook_it(N, A);
Bake(order_num);
}
else {
add_queue(order_num, N, A);
}
order_num++;
return;
}

void Delivery(int I) {
ing[I]++;
elaborate_queue();
}
```
  
Quindi in pratica faccio la simulazione come richiesto dal problema.  
  
le funzioni is\_cookable e cook\_it vengono eseguite in O(N) dove N è al massimo 8  
add\_queue anche viene eseguito in poco più di O(N), perchè copio il vettore A nella coda che è così strutturata:  
  

```
struct order {
    int ord, N;
    int A[8];
};

deque<order> Q;
```
  
mentre elaborate\_queue varia in base alla dimenzione della deque  
  

```
void elaborate_queue() {
int size = Q.size();
for(int i = 0; i < size; i++) {
if(is_cookable(Q[i].N, Q[i].A)) {
cook_it(Q[i].N, Q[i].A);
Bake(Q[i].ord);
Q.erase(Q.begin()+i);
break;
}
}
return;
}
```
  
Ora, per far si che non sfori il tempo di esecuzione, usando questo algoritmo dovrei trovare un modo di avere una coda il cui primo elemento è sempre un ordine che può essere preparato, in questo modo evito la ricerca nell’intera coda.  
  
Il punto è che come posso farlo??  
  
Il problema visto sotto un altro punto di vista potrebbe somigliare ad un problema di query ed update…ma non so…  
  
Qualche consiglio?

---

<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:** [17 Agosto 2014, 4:26pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/2 "2014-08-17T16:26:07Z")

</div>

Sai qualcosa di bitmasking?

  

Comunque, invece di una deque, io userei una list, dato che ha erase in O(1) e non in O(N)

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [17 Agosto 2014, 4:36pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/3 "2014-08-17T16:36:32Z")

</div>

> Sai qualcosa di bitmasking?
>   
> 
> Comunque, invece di una deque, io userei una list, dato che ha erase in O(1) e non in O(N)
> 
> mark03

si già provato con le&nbsp;list,&nbsp;ma non&nbsp;cambia nulla almeno secondo i tempi dati dal correttor

bitmasking per rappesentare gli 8 ingredienti? Ci avevo pensato ma non mi sembrava Una buona idea

In che modo intendi tu?

---

<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:** [17 Agosto 2014, 5:10pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/4 "2014-08-17T17:10:04Z")

</div>

Usando il bitmasking il check passa da O(N) a O(1). Ma ciò che veramente importante è questo: nota che i tipi di pizze sono solo 256 (2^8) mentrebil numero di pizze può arrivare a 100000. Quindi…

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [17 Agosto 2014, 8:19pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/5 "2014-08-17T20:19:06Z")

</div>

Posso chiedere lumi sul bitmasking?

---

<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:** [17 Agosto 2014, 9:03pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/6 "2014-08-17T21:03:55Z")

</div>

> Posso chiedere lumi sul bitmasking?
> 
> marcoBeretta

Ecco qui :)
[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation)

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [18 Agosto 2014, 7:56am UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/7 "2014-08-18T07:56:37Z")

</div>

> > Posso chiedere lumi sul bitmasking?
> > 
> > marcoBeretta
> 
> Ecco qui :)
> [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation](http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation)  
> 
> wil93

Grazie ora guardo!
  

edit: ho capito come funziona ma non saprei come utilizzarlo per risolvere il problema... un indizio?

edit 2: risolto grazie!

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [18 Agosto 2014, 11:00am UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/8 "2014-08-18T11:00:41Z")

</div>

Ora ho:  
is\_cookable in O(1);  
cook\_it in O(N); //perchè comunque devo tenere per forza un array di interi per tenere conto di QUANTI ingredienti ho.  
add\_queue in O(1);  
  
e risolvo un testcase in più.  
  
gli ultimi 2 li salta ancora.  
  
Ora la struttura della coda è questa:

```
struct order {
int ord;
char I;
};
list<order> Q;
```
tengo con un char gli ingredienti della pizza  
e così controllo se la pizza si puù fare:  
  

```
bool is_cookable(char I) {
return ((ing_ava & I) == I);
}
```
  
e la faccio così:  
  

```
void cook_it(char I) {
for(int i = 0; i < 8; i++) {
if((I & 1 << i) != 0) {
ing_num[i]–;
if(ing_num[i] == 0) ing_ava &= ~(1 << i);
}
}
return;
}
```

---

<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:** [18 Agosto 2014, 11:04am UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/9 "2014-08-18T11:04:22Z")

</div>

> Ora ho:  
> is\_cookable in O(1);  
> cook\_it in O(N); //perchè comunque devo tenere per forza un array di interi per tenere conto di QUANTI ingredienti ho.  
> add\_queue in O(1);  
>   
> e risolvo un testcase in più.  
>   
> gli ultimi 2 li salta ancora.  
>   
> Ora la struttura della coda è questa:  
>   
> 
> ```
> struct order {
> int ord;
> char I;
> };
> list<order> Q;
> ```
> tengo con un char gli ingredienti della pizza  
> e così controllo se la pizza si puù fare:  
>   
> 
> ```
> bool is_cookable(char I) {
> return ((ing_ava & I) == I);
> }
> ```
>   
> e la faccio così:  
>   
> 
> ```
> void cook_it(char I) {
> for(int i = 0; i < 8; i++) {
> if((I & 1 << i) != 0) {
> ing_num[i]--;
> if(ing_num[i] == 0) ing_ava &= ~(1 << i);
> }
> }
> return;
> }
> ```
>   
> 
> simone.pri

Come ho già detto, perchè iterare su 100000 potenziali pizze, quando i tipi effettivi di pizze sono solo 256?

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [18 Agosto 2014, 5:06pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/10 "2014-08-18T17:06:39Z")

</div>

E in che modo tengo conto dell’ordine delle pizze?  
  
dovrei avere tipo una struttura del genere:  
priority\_queue\< priority\_queue\<int, vector\<int\>, greater\<int\> \>, vector\< priority\_queue\<int\> \>,&nbsp; priority\_cmp\> Q;  
  
una coda di priopriorità di una coda di priorità  
la coda contiene al più 256 elementi, (i tipi di pizza) e ogni “tipo” contiene una coda con il numero degli ordini delle pizze di quel tipo (ordinate dal più piccolo al più grande)  
  
Ma sono dubbioso di questa struttura O:

---

<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:** [18 Agosto 2014, 5:50pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/11 "2014-08-18T17:50:01Z")

</div>

> E in che modo tengo conto dell'ordine delle pizze?  
>   
> dovrei avere tipo una struttura del genere:  
> priority\_queue\< priority\_queue\<int, vector\<int\>, greater\<int\> \>, vector\< priority\_queue\<int\> \>,&nbsp; priority\_cmp\> Q;  
>   
> una coda di priopriorità di una coda di priorità  
> la coda contiene al più 256 elementi, (i tipi di pizza) e ogni "tipo" contiene una coda con il numero degli ordini delle pizze di quel tipo (ordinate dal più piccolo al più grande)  
>   
> Ma sono dubbioso di questa struttura O:  
> 
> simone.pri

Assolutamente no! Ti basta un array di vector lungo 256 posizioni. Ad ogni pizza corrisponde un posto nell'array e nel vector corrispondente fai il push del numero degli ordini (che sarà, ovviamente, ordinato dato che le pizze vengono date in ordine)

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [18 Agosto 2014, 6:25pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/12 "2014-08-18T18:25:42Z")

</div>

Io ho fatto così:

```
queue<int> V[256];
```
In realtà ,poi, è la prima cosa a cui avevo pensato,  
solo che mi sembrava che l’elaborate impiegasse 256\*256  
invece giustamente basta solo una ricerca di 256  
  
Scusa per la cavolata D: ahaha  
  
E soprattuto grazie per la mano

---

<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:** [18 Agosto 2014, 9:36pm UTC](https://forum.olinfo.it/t/aiutino-per-olympic-pizza/3836/13 "2014-08-18T21:36:47Z")

</div>

> Io ho fatto così:  
> 
> ```
> queue<int> V[256];
> ```
> In realtà ,poi, è la prima cosa a cui avevo pensato,  
> solo che mi sembrava che l'elaborate impiegasse 256\*256  
> invece giustamente basta solo una ricerca di 256  
>   
> Scusa per la cavolata D: ahaha  
>   
> E soprattuto grazie per la mano  
>   
> 
> simone.pri

Di niente :D