matteo.pata
10-09-2010, 18:07
Ciao ragazzi rieccomi qua ad esporvi le mie problematiche:
ho un progetto da fare: mi servirebbe una mano per scegliere la giusta struttura dati da utilizzare e per mettere giù qualche pezzo di codice:
il testo è:
New New New York è la città più popolata nell'anno 3500 D.C. (costruita sulle ceneri di New New
York). A NNNY si costruiscono grattacieli quasi ogni giorno. I grattacieli non sono fatti per durare in
eterno. Già al momento della costruzione è nota la data della demolizione, talvolta vicinissima a quella
di costruzione.
Ogni grattacielo al momento della costruzione viene battezzato con un nome (univoco). Qualche volta,
si decide di ristrutturare un grattacielo già esistente e si proroga la data della sua demolizione.
New New New York si a accia sul mare: la sua spiaggia si estende da Nord a Sud. Se la si osserva dal
mare, di notte, sopra alla spiaggia appare un tipico skyline (la linea di con ne fra cielo e grattacieli).
Infatti, ogni metro di spiaggia (ad una certa latitudine) è sovrastato da un certo numero di grattacieli a
longitudini diverse (talvolta uno o nessuno). Chiaramente, è sempre il più alto di questi a svettare sugli
altri, e la sua altezza de nisce l'altezza dello skyline su quel metro di spiaggia. In assenza di palazzi, lo
skyline è alto zero.
Il problema consiste nel registrare, un certo numero di volte durante la serie di costruzioni e abbattimenti,
quante altre volte lo skyline si è presentato esattamente nella stessa forma in passato (per ni turistici e
storici).
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 no al punto 5).
Ciascuna riga successiva descrive un evento quotidiano, oppure una query. Ogni giorno avviene soltanto un evento. Un evento può corrispondere alla costruzione di un nuovo palazzo, oppure alla ristrutturazione di un palazzo già esistente (con conseguente procrastinamento della sua demolizione), oppure ancora al semplice passaggio di una giornata (evento vuoto). Costruzioni e ristrutturazioni avvengono sempre nel primo mattino. La sera, quando è necessario, uno (o anche più) palazzi (arrivati alla ne della loro vita) possono essere abbattuti. Se nella riga successiva all'evento compare una query, allora il programma deve rispondere ad una domanda relativa alla notte successiva all'ultimo evento trascorso.
E' Le righe che descrivono una query consistono nel solo carattere \punto interrogativo". Nel leggere questa riga, il programma dovrà stampare a schermo il numero di notti precedenti nelle quasi lo skyline si è presentato identico a quello della notte corrente . Ad esempio, se durante la notte relativa alla richiesta siamo in presenza di uno skyline inedito, si dovrà stampare il numero 0. Se lo skyline è identico a quello della notte di una settimana prima (ma diverso da quello di tutte le altre notti) si dovrà stampare il numero 1.
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 del grattacielo, seguito dalla durata prevista, cioè dal numero di giorni che il grattacielo deve durare prima di essere abbattuto. Le tre misure rappresentano, rispettivamente: da quale metro di spiaggia comincia e a quale metro fi nisce
il grattacielo, e la sua altezza, in centimetri. Si tratta di tre numeri naturali. Ad esempio, se compaiono i numeri 4 6 1000, signi ca che il grattacielo si estende nell'intervallo che comincia a 4 metri esatti, nisce al sesto metro (sarà dunque lungo due metri), ed è alto 1000 centimetri (10 metri). La durata è espressa in giorni, ed e' un numero naturale strettamente maggiore di 0 che rappresenta il numero di giornate che devono trascorrere prima dell'abbattimento (salvo rimandi). Il grattacielo viene abbattuto la sera della sua ultima giornata, prima della notte successiva. Quindi, ad esempio, se la durata valesse 1, il grattacielo verrebbe abbattuto ancor prima della notte successiva.
Gli eventi di tipo ristrutturazione cominciano con la stringa \renew" (senza le virgolette), seguita dal nome del palazzo in questione, seguito dal numero di giorni di durata ulteriore da attribuire al grattacielo.
Gli eventi vuoti consistono nella lettera \v" (senza le virgolette).
La serie di righe è terminata da una riga composta da un solo punto esclamativo, che segnala la ne del
problema.
L'input viene fornito al programma sotto forma di fi le di testo, il cui nome viene speci cato dal primo
argomento passato al programma. Se non ne viene speci cato alcuno, l'input deve venir letto direttamente dallo stdin.
Dopo la lettura di un evento, il programma deve stampare un numero Alla ne della giornata a cui l'evento fa riferimento.
Facciamo ad esempio il seguente caso di le di input.
15
new aaa 7 10 2500 3
new bbb 5 10 1500 100
?
new ccc 7 9 2500 100
new ddd 9 10 2500 100
?
!
2
Il primo giorno viene costruito aaa, e il secondo bbb.
Al momento della la prima query, la seconda notte, saranno presenti entrambi i grattacieli aaa e bbb. Dal metro 7 al metro 10 (dunque per tre metri) avremo uno skyline alto esattamente 25 metri (l'altezza del palazzo aaa). Dal metro 5 al 7, alto 15 (per il palazzo bbb, che in e etti prosegue anche no al metro 10,
ma dal metro 7 al 10 la sua silhouette viene coperta da quella di aaa). Visto che questa con gurazione non ha avuto precedenti, alla query si risponderà con uno 0.
La mattina del terzo giorno viene costruito ccc. Alla sera dello stesso giorno, aaa viene abbattuto. Il quarto giorno viene costruito ddd. Al momento della seconda query, cioe la quarta notte, lo skyline è lo stesso della seconda notte (pur essendo in piedi un numero diverso di palazzi). Dunque alla query si
risponderà con un 1.
So noti che e' alla seconda query si sarebbe dovuto rispondere nello stesso modo anche se la prima query non fosse stata e ettuata. Infatti, conta il numero di notti, indipendentemente dal numero di queries.
Grazie in anticipo a tutti quelli che mi daranno una mano....
ho un progetto da fare: mi servirebbe una mano per scegliere la giusta struttura dati da utilizzare e per mettere giù qualche pezzo di codice:
il testo è:
New New New York è la città più popolata nell'anno 3500 D.C. (costruita sulle ceneri di New New
York). A NNNY si costruiscono grattacieli quasi ogni giorno. I grattacieli non sono fatti per durare in
eterno. Già al momento della costruzione è nota la data della demolizione, talvolta vicinissima a quella
di costruzione.
Ogni grattacielo al momento della costruzione viene battezzato con un nome (univoco). Qualche volta,
si decide di ristrutturare un grattacielo già esistente e si proroga la data della sua demolizione.
New New New York si a accia sul mare: la sua spiaggia si estende da Nord a Sud. Se la si osserva dal
mare, di notte, sopra alla spiaggia appare un tipico skyline (la linea di con ne fra cielo e grattacieli).
Infatti, ogni metro di spiaggia (ad una certa latitudine) è sovrastato da un certo numero di grattacieli a
longitudini diverse (talvolta uno o nessuno). Chiaramente, è sempre il più alto di questi a svettare sugli
altri, e la sua altezza de nisce l'altezza dello skyline su quel metro di spiaggia. In assenza di palazzi, lo
skyline è alto zero.
Il problema consiste nel registrare, un certo numero di volte durante la serie di costruzioni e abbattimenti,
quante altre volte lo skyline si è presentato esattamente nella stessa forma in passato (per ni turistici e
storici).
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 no al punto 5).
Ciascuna riga successiva descrive un evento quotidiano, oppure una query. Ogni giorno avviene soltanto un evento. Un evento può corrispondere alla costruzione di un nuovo palazzo, oppure alla ristrutturazione di un palazzo già esistente (con conseguente procrastinamento della sua demolizione), oppure ancora al semplice passaggio di una giornata (evento vuoto). Costruzioni e ristrutturazioni avvengono sempre nel primo mattino. La sera, quando è necessario, uno (o anche più) palazzi (arrivati alla ne della loro vita) possono essere abbattuti. Se nella riga successiva all'evento compare una query, allora il programma deve rispondere ad una domanda relativa alla notte successiva all'ultimo evento trascorso.
E' Le righe che descrivono una query consistono nel solo carattere \punto interrogativo". Nel leggere questa riga, il programma dovrà stampare a schermo il numero di notti precedenti nelle quasi lo skyline si è presentato identico a quello della notte corrente . Ad esempio, se durante la notte relativa alla richiesta siamo in presenza di uno skyline inedito, si dovrà stampare il numero 0. Se lo skyline è identico a quello della notte di una settimana prima (ma diverso da quello di tutte le altre notti) si dovrà stampare il numero 1.
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 del grattacielo, seguito dalla durata prevista, cioè dal numero di giorni che il grattacielo deve durare prima di essere abbattuto. Le tre misure rappresentano, rispettivamente: da quale metro di spiaggia comincia e a quale metro fi nisce
il grattacielo, e la sua altezza, in centimetri. Si tratta di tre numeri naturali. Ad esempio, se compaiono i numeri 4 6 1000, signi ca che il grattacielo si estende nell'intervallo che comincia a 4 metri esatti, nisce al sesto metro (sarà dunque lungo due metri), ed è alto 1000 centimetri (10 metri). La durata è espressa in giorni, ed e' un numero naturale strettamente maggiore di 0 che rappresenta il numero di giornate che devono trascorrere prima dell'abbattimento (salvo rimandi). Il grattacielo viene abbattuto la sera della sua ultima giornata, prima della notte successiva. Quindi, ad esempio, se la durata valesse 1, il grattacielo verrebbe abbattuto ancor prima della notte successiva.
Gli eventi di tipo ristrutturazione cominciano con la stringa \renew" (senza le virgolette), seguita dal nome del palazzo in questione, seguito dal numero di giorni di durata ulteriore da attribuire al grattacielo.
Gli eventi vuoti consistono nella lettera \v" (senza le virgolette).
La serie di righe è terminata da una riga composta da un solo punto esclamativo, che segnala la ne del
problema.
L'input viene fornito al programma sotto forma di fi le di testo, il cui nome viene speci cato dal primo
argomento passato al programma. Se non ne viene speci cato alcuno, l'input deve venir letto direttamente dallo stdin.
Dopo la lettura di un evento, il programma deve stampare un numero Alla ne della giornata a cui l'evento fa riferimento.
Facciamo ad esempio il seguente caso di le di input.
15
new aaa 7 10 2500 3
new bbb 5 10 1500 100
?
new ccc 7 9 2500 100
new ddd 9 10 2500 100
?
!
2
Il primo giorno viene costruito aaa, e il secondo bbb.
Al momento della la prima query, la seconda notte, saranno presenti entrambi i grattacieli aaa e bbb. Dal metro 7 al metro 10 (dunque per tre metri) avremo uno skyline alto esattamente 25 metri (l'altezza del palazzo aaa). Dal metro 5 al 7, alto 15 (per il palazzo bbb, che in e etti prosegue anche no al metro 10,
ma dal metro 7 al 10 la sua silhouette viene coperta da quella di aaa). Visto che questa con gurazione non ha avuto precedenti, alla query si risponderà con uno 0.
La mattina del terzo giorno viene costruito ccc. Alla sera dello stesso giorno, aaa viene abbattuto. Il quarto giorno viene costruito ddd. Al momento della seconda query, cioe la quarta notte, lo skyline è lo stesso della seconda notte (pur essendo in piedi un numero diverso di palazzi). Dunque alla query si
risponderà con un 1.
So noti che e' alla seconda query si sarebbe dovuto rispondere nello stesso modo anche se la prima query non fosse stata e ettuata. Infatti, conta il numero di notti, indipendentemente dal numero di queries.
Grazie in anticipo a tutti quelli che mi daranno una mano....