Laboratorio di Algoritmi e Strutture Dati
Marco Tarini
“New New York”
Consegna Progetto: entro Dom 25 Aprile 2010 - ore 24.00
Il problema
A New New York, la citt`a pi`u popolata nell’anno 3000 D.C., si costruiscono grattacieli di continuo e ad una velocit`a impressionante. Purtroppo, non rimangono mai in piedi a lungo perch´e secoli di pessime politiche estere hanno creato un clima internazionale talmente invivibile che attacchi terroristici si susseguono di continuo, e non di rado i palazzi vengono rasi al suolo.
Ogni grattacielo al momento della costruzione viene battezzato con un nome (univoco).
New New York si affaccia sul mare, con la sua spiaggia si estende da Nord a Sud. Se la si osserva dal mare, di notte, sopra alla spiaggia appare una tipica skyline (la linea di confine fra cielo e grattacieli).
Infatti, ogni metro di spiaggia (ad una certa latitudine) `e sovrastato da un certo numero di grattacieli a longitudini diverse (talvolta uno o nessuno). Chiaramente, `e sempre il pi`u alto di questi a svettare sugli altri, e la sua altezza definisce l’altezza dello skyline su quel metro di spiaggia. In assenza di palazzi, lo skyline `e alto zero.
Il problema consiste del misurare l’altezza media dello skyline di New New York durante la continua costruzione e distruzione di palazzi.
Dati in input
L’input consiste in una serie di righe. Nella prima riga compare un numero, che corrisponde alla lunghezza totale della spiaggia, in metri (per esempio, se vale 5, la spiaggia comincia nel punto 0 e si estende fino al punto 5). Ciascuna riga successiva descrive un evento (costruzione o, tragicamente, abbattimento di un grattacielo), o una richiesta.
• Le richieste sono semplicemente delle righe costituite da un unico punto interrogativo. Nel leg- gere una richiesta, il programma deve stampare nello standard output l’altezza media dello skyline, espressa in metri, precisa al millimetro.
• Gli eventi di tipo abbattimento cominciano dalla stringa “kaboom” (senza le virgolette), seguita dal nome del palazzo abbattuto.
• Gli eventi di tipo costruzione cominciano con la stringa “new” (senza le virgolette), seguita dal nome del palazzo costruito, seguito da una tripletta di misure (separate da spazi) che rappresentano, rispettivamente: da quale metro di spiaggia comincia e a quale metro finisce il grattacielo, e la sua altezza, tutto in metri. Le prime due misure sono numeri naturali, la terzo `e un razionale (con virgola). Ad esempio, se compaiono i numeri 4 6 10.4, significa che il grattacielo si estende nell’intervallo che comincia a 4 metri esatti, finisce al 6sto metro (sar`a dunque lungo due metri), ed
`
e alto 10.4 metri.
La serie di righe `e terminata da una riga composta da un solo punto esclamativo, che segnala la fine del problema.
1
L’input viene fornito al programma sotto forma di file di testo, il cui nome viene specificato dal primo argomento passato al programma. Se non ne viene specificato alcuno, l’input deve venir letto direttamente dallo stdin.
Altri vincoli
E’ richiesto che programma funzioni in modalit`a “on-line”: cio`e l’input pu`o essere letto una sola volta, e, nel leggere una richiesta, la risposta deve essere stampata sul video senza che sia necessario leggere nessuna delle righe successive. Insomma il programma deve funzionare anche se ipoteticamente l’input fosse fornito solo una riga alla volta, e se le risposte fossero necessarie prima di fornire la riga successiva.
La correttezza `e un requisito necessario. Un progetto sar`a considerato pi`u o meno valido rispetto all’ef- ficienza (tempo di calcolo) nel risolvere le istanze del problema di dimensioni via via crescenti (non solo le istanze fornite, ovviamente, ma anche altre del tipo di quelle fornite).
Esempi
Mettiamo che la spiaggia sia lunga 10 metri (da 0 a 10). Se abbiamo solo il grattacielo pippo e pluto, costruiti con
new pippo 7 10 25.0 new pluto 5 10 15.0
allora la skyline sara’ ad altezza 0 fino al quinto metro (per cinque metri), 10.0 per i metri dal quinto al settimo (dunque per due metri), e 25.0 dal settimo al decimo (dunque per tre metri). L’altezza media sar`a (2 · 15 + 3 · 25)/10, cio`e 10.5 metri.
Dal sito del corso `e possibile scaricare esempi di input (file di testo) di difficolt`a crescente.
Dimensioni tipiche dei problemi
Gli abbattimenti sono frequenti. Si sa che i grattacieli che vengono distrutti sono, grossomodo, una percentuale fissa dei grattacieli che vengono costruiti (es. il 20-50%).
I nomi non sono mai pi`u lunghi di qualche centinaio di caratteri.
I grattacieli possono essere molto numerosi. Tuttavia, istanze anche grandi del problema (in numero di grattacieli) hanno di solito spiagge relativamente poco estese.
Gli esempi forniti sono rappresentativi delle dimensioni possibili che ci si pu`o attendere.
Suggerimenti
1. Per leggere l’input e scrivere l’output si possono usare le funzioni standard ANSI C fscanf() e printf(). Il primo parametro della fscanf() sia una variabile posta a stdin oppure ad un FILE*
aperto in lettura (a seconda del numero di argomenti).
2. Soluzioni che impiegano un tempo quadratico (o peggio) nel numero di eventi NON saranno abbastanza efficienti da risolvere le istanze grandi del problema.
3. SEMPRE: pensare bene sulla carta prima di cominciare a scrivere codice!
2
Presentazione del progetto
Il progetto va implementato in C (si faccia riferimento allo standard ANSI). Vi `e piena libert`a sulla scelta dell’ambiente di sviluppo, ma il codice deve poter essere compilato con gcc e funzionare correttamente se eseguito da linea di comando.
L’elaborato deve essere inviato per posta elettronica all’indirizzo marco.tarini@isti.cnr.it entro e non oltre la data indicata. L’avvenuta ricezione del progetto sar`a confermata da un mio messaggio. Per favore, il soggetto della mail includa la stringa “algo2009c”.
I progetti che non hanno ricevuto un mio messaggio di conferma non saranno considerati validi.
Occorre presentare, oltre al il codice sorgente, una sintetica relazione (formato pdf o ps) che illustri le strutture dati utilizzate e analizza il costo delle diverse operazioni richieste dalla specifica.
Tutti i file spediti dal sorgente devono chiamarsi col proprio nome e cognome, per es ‘francorossi’. Solo l’estensione cambia: ‘.c’ per il file sorgente, se unico, ‘.zip’ se il progetto comprende pi`u di un file sorgente (e allora tale zip conterr`a solo alcuni file ‘.h’ ‘.c’), ‘.pdf’ o ‘.ps’ per la relazione.
Non inviare file eseguibili, neanche in cartelle compattate.
Il progetto deve essere discusso nella sessione di consegna. Si ricorda di presentarsi alla prova orale con una copia stampata della relazione e del codice.
La versione aggiornata del progetto `e pubblicata sul sito del corso (cercare la mia pagina con google – “Marco Tarini”, seguire “teaching” in fondo, seguire “lab di algoritmi 2009/2010”). Si consiglia di consultare periodicamente il sito per eventuali correzioni e/o precisazioni relative al testo del progetto.
La realizzazione del progetto `e una prova d’esame da svolgersi individualmente. Progetti che saranno ritenuti semplici varianti uno dell’altro non verranno corretti, a prescindere di quale sia stato l’originale e quale la copia derivata.
Per ogni ulteriore chiarimento, e-mail: marco.tarini@isti.cnr.it
3
