Per esercizio e tifare per i nostri atleti, vi propongo di cimentarvi nella soluzione del primo task di riscaldamento pubblicato sul sito delle Olimpiadi Internazionali di Informatica 2012 che cominceranno il prossimo 23 settembre 2012.
Sul sito si può scaricare anche una macchina virtuale contenente una installazione Ubunto simile aquella che si troveranno davanti gli atlei nella competizione che gira su Virtual Box.
Una veloce traduzione delle istruzioni in Inglese del task la potete trovare qui in basso. Per svolgere l'esercizio è consigliabile utilizzare la directory compressa predisposta dal comitato olimpico scaricabili qui. In questa directory troverete anche il main da utilizzare per testare la vostra soluzione. Se volete, potete scaricarvi questo programmino che scritto per produrre i dati di test. Nello zippo c'è anche il progetto .dev per Dev-Cpp.
Chi vuole cimentarsi con questo esercizio? Inviate la vostra soluzione nei commenti. Anch'io mi cimenterò nella soluzione in un prossimo post.

Tralascio la traduzione dei commenti ironici sulle difficoltà di approvvigionamento e gli stereotipi sull'organizzazione all'Italiana simpaticamente descritte nell'esordio della traccia, lo scopo del task è scrivere un programma che riceva la notifica di nuovi ordini di pizza e di consegne di ingredienti e che dica al pizzaiolo di preparare la pizza non appena ha tutti gli ingredienti necessari per farlo.

Ci sono esattamente 8 ingredienti per guarnire la pizza che sono identificati da numeri interi da 0 a 7. Anche gli ordini sono numerati consecutivamente partendo da 0 (il primo ordine di pizza).

Occorre implementare le seguenti routine

Init() - la routine è chiamata una sola volta all'inizio dell'esecuzione del programma, prima di qualunque altra istruzione;

Order(N,A) - La routine viene chiamata all'arrivo di un ordine con N ingredienti di guarnizione specificati nel vettore A da A[0] a A[N-1] che assume valori da 0 a 7 senza che ci possano essere due elementi di A uguali tra loro;

Delivery(I) - La routine viene eseguita non appena viene consegnato l'ingrediente I, che assume valori da 0 a 7;

Il programma, quando ci sono tutti gli ingredienti per soddisfare l' ordine k-esimo, deve chiamare la seguente routine fornita fornita dal sistema:

Bake(K) - con k >= 0.

Alcuni ordini potrebbero non essere mai soddisfatti a causa della mancanza di qualche ingrediente.

Esempio

Tue routine Routine di sistema

Init()

Delivery(1)

Delivery(1)

Delivery(1)

Delivery(2)

Delivery(2)

Order(3,[1,2,3])

Delivery(4)

Delivery(4)

Order(3,[1,2,4]) Bake(1)

Delivery(3) Bake(3)

Order(4,[1,2,3,4])

Delivery(2)

La valutazione del Task è fatta in base ai seguenti sottotask:

Sottotask 1 [25 punti]

Le routine Order and Delivery saranno chiamate al più 100 volte

Sottotask 2 [25 punti]

Le routine Order and Delivery saranno chiamate al più 5000 volte

Sottotask 3 [20 punti]

Le routine Order and Delivery saranno chiamate al più 100000 volte. Inoltre le Delivery avverrano tutte prima di ogni ordine;

Sottotask 4 [30 punti]

Le routine Order and Delivery saranno chiamate al più 100000 volte

Dettagli implementativi

Occorre produrre un solo file pizzac che implemneti le routine descritte sopra usando le signature seguenti:

void Init();

Void Order(int N, int *A);

void Delivery(int I);

La signature della routine Bake è la seguente:

void Bake( int K);

Ovviamnete in pizza.c ci possono tante altre altre funzioni di servizio quanto voi ritenete necessario per la soluzione del problema. Non si può leggere o scrivere su file o su stdin o stdout.

Limiti di Run Time

Limite di tempo 1 secondo

Limite di memoria 256 MiB