Soluzione con liste concatenate semplici del task Pizza delle Olimpiadi Internazionali di Informatica 2012

Qui troverete una soluzione del Task di riscaldamento Pizza delle Olimpiadi Internazionali dell'Informatica 2012 in corso a Sirmione (BS) in questi giorni.La soluzione è basata sull'uso delle liste semplici concatenate. Torneremo presto su questo argomento in un prossimo post. Per il momento vi lascio alla lettura dei commenti inseriti nel codice.

L'applicativo ha dimostrato delle bune performance terminando l'analisi di 100000 ordini e consegne in tempi inferiori ai 150 millisecondi su una macchina intel core i7 a 2.8 GHz con Windows 7. Nella figura in alto a sinistra si può vedere il risultato della misura dei tempi di esecuzione con il comando unix time su CigWin.

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

Olimpiadi Internazionali dell'Informatica 2012

La 24° edizione delle Olimpiadi Internazionali in Informatica (IOI) si svolgerà a Montichiari/Sirmione (BS), dal 23 al 30 settembre 2012. La squadra che rappresenterà l'Italia è stata selezionata il 13 giugno 2012, al termine di un lungo percorso, le Olimpiadi Italiane dell'Informatica, cominciato nelle 399 sparse sul territorio nazionale scuole iscritte alle selezioni, e continuato nelle selezioni territoriali per arrivare alle selezioni finali dello scorso 13 giugno. Le IOI sono nate nel 1989 con l'obiettivo primario di stimolare l'interesse nell'informatica e nella tecnologia dell'informazione.Le IOI sono organizzate ogni anno da una delle nazioni partecipanti; ogni paese invia una propria delegazione composta da non più di quattro studenti di età inferiore ai 20 anni e da due adulti accompagnatori. Le gare si concentrano in due giornate nell'arco di una settimana durante la quale sono previsti eventi culturali e ricreativi organizzati dal paese ospitante.Gli atleti competono individualmente cercando di risolvere i problemi di natura algoritmica assegnati con l'utilizzo di un personal computer. I linguaggi di programmazione usati sono il C e il Pascal. Gli esercizi di "riscaldamento" preparati dal comitato Olimpico e l'ambiente di lavoro sono disponibili qui. Un sentito in bocca al lupo per la squadra italiana!

Procuriamoci gli Strumenti per la progettazione del software - parte 1

Alcuni potrebbero osservare che per il progetto di un programma è sufficiente usare carta e matita. Questo è verissimo fino a che la dimensione e/o la complessità del software non diventano tali da rendere un vero incubo la gestione del progetto e delle sue revisioni. Ancora una volta, googlando "software design free" avrete una cascata di proposte di software di ausilio alla progettazione.

Ma, che cosa significa progettare un software? La progettazione del software è un argomento piuttosto vasto che si inserisce nel più vasto argomento del "ciclo di vita del software" che sarà oggetto di una serie di post nel prossimo futuro. Per il momento accontentiamoci di dare una definizione ricorsiva : "progettare un software vuol dire progettare i componenti del software da realizzare per soddisfare i requisiti espressi dall'utente finale del software e/o dal committente". Già, ma chi progetta i componenti? Siamo sempre noi. Scomponendo il problema da risolvere in sottoproblemi forse riusciremo ad individuare dei sottoproblemi, o componenti, già noti e quindi fermarci con la scomposizione e con il progetto. Oppure, per alcuni sottoproblemi, o componenti, dovremo procedere ad una ulteriore scomposizione fino ad arrivare a problemi facilmente risolvibili. Insomma, come dicevano i Romani, "divide et impera". Ritornando alla definizione di progettazione software che abbiamo dato, è necessario sottolineare la parte riguardante "... soddisfare i requisiti espressi dall'utente finale del software o dal committente". Infatti, non si può progettare un software senza aver prima raccolto i requisiti che deve soddisfare. Anche per questa fase del ciclo di vita del software sono stati definiti dei modelli teorici e degli strumenti software di ausilio alla raccolta e l'analisi dei requisiti.

Ritornando al progetto del software, per gli studenti delle scuole medie superiori lo strumento di progettazione più usato è il diagramma di flusso, la ricerca Google "free software flowchart diagram" restituirà una lista di programmi gratuiti per la creazione e gestione di diagrammi di flusso. Per quanto riguarda questo sito e le lezioni online, si userà YEd.

Nella parte 2 di questo post vedremo insieme quali strumenti free di ausilio alla progettazione si possono trovare nella rete per gli studenti universitari e i programmatori professionisti.

Il linguaggio di programmazione C

Il C è un linguaggio di programmazione imperativo "antico" ma ancora molto ma molto attuale.
Antico perché è stato inventato alla fine degli anni '60 del secolo scorso da Dennis Ritchie ed è stato usato per la scrittura del sistema operativo Unix. Il signor Ritche è venuto a mancare il 12 ottobre 2011, a pochi giorni dalla scomparsa di Steve Jobs, ma non se ne è parlato molto sui media internazionali. Eppure, quasi tutti gli oggetti di uso comune, dal più sofisticato smartphone al più insignificante prodotto industriale, sono stati progettati grazie agli sviluppi tecnologici che il C ha consentito o contentgono componenti software scritte o prodotte grazie al C.
Il C è moderno perché è ancora in uso e il patrimonio applicativo basato sul C o sulla sua versione a oggetti C++ ammonta sicuramente a diversi miliardi di linee di codice. La modernità di questo linguaggio è anche constatabile osservando i vari dialetti che si sono sviluppati nei tempi recenti, come ad esempio il C# per .NET, oppure se si osserva la numerosità degli ambienti di sviluppo C/C++ per microcontrollori, ad esempio per la famiglia di microcontrollori AVR della Atmel è disponibile l'IDE WinAVR .

Procuriamoci un ambiente di sviluppo C/C++

Per ambiente di sviluppo si intende l'insieme degli strumenti software necessari per scrivere, compilare, collegare e eseguire un programma scritto nel linguaggio di programmazione scelto.

Per ottenere un ambiente di sviluppo C/C++ dobbiamo innanzitutto decidere su quale Sistema Operativo (SO) vogliamo lavorare: Windows, Mac OS X, Unix, Linux, .... Per quanto riguarda Mac OS X, Unix e Linux, occorre osservare che essendo questi POSIX o parzialmente POSIX , essi contengono la cosiddetta catena di sviluppo gcc che consente di avere a disposizione gratuitamente un ambiente di sviluppo potente e completo. D'altra parte, per quanto riguarda Windows occorre procurarsi tutti gli strumenti dell'ambiente di sviluppo. Ce ne sono diversi in giro sulla rete e una ricerca con Google del tipo "compilatori C++ free windows" dovrebbe darvi abbastanza link da studiare.

Quando si parla di ambienti di sviluppo, taluni pensano subito ad un ambiente integrato che consente di scrivere, verificare la sintassi, compilare collegare, eseguire e testare un programma scritto con un certo linguaggio di programmazione. Pensano quindi ad un Integrated Development Environment (IDE). Effettivamente sono molto comodi da usare e talvolta, per certe piattaforme, indispensabili per poter far riferimento a complesse Application Programming Interface (librerie di programmazione per interfacciarsi al SO o API) quali, ad esempio, quelle di Windows . Ci sono molti IDE gratuiti disponibili su Internet. Ancora una volta, googlando "IDE C++ free" otterrete una bella lista di IDE gratuiti per i vari SO.

Per le lezioni su Skype cercheremo di adattarci alle scelte di SO e di IDE dei discenti, ma su questo sito, per brevità e chiarezza, utilizzeremo la GNU toolchain su UNIX o UNIX-like e DEV-CPP (scaricabile qui) su WIndows. Vi lasciamo con una indicazione di lettura per i programmatori UNIX like o per quelli che vorrebbero diventarlo. Qui, troverete un articolo su Unix visto come un IDE :). Ci permettiamo di ricordarvi che è tutto molto attuale e che l'acquisizione delle nozioni presentate nell'articolo può sicuramente fare la differenza nel mondo del lavoro di oggi.