Selezioni Territoriali 2013

[Difficoltà D=2]

A spasso per Brisbane (brisbane)

Descrizione del problema

Nel 2013, le IOI si svolgeranno a Brisbane (in Australia). La rappresentativa italiana ha già iniziato a studiare la città, per capire cosa ci sia di interessante da vedere, e come ci si possa spostare nella giornata libera successiva alla seconda gara delle Olimpiadi. L’offerta di trasporto pubblico a Brisbane è abbastanza variegata: ci sono due linee di bus, di cui una gratuita che gira intorno alla città, e due linee di traghetti che fermano in diversi punti del fiume Brisbane, che taglia la città in due; per quello che riguarda i prezzi, esiste un abbonamento giornaliero a tutti i trasporti pubblici, bus e traghetti insieme, oppure è possibile prendere un più economico abbonamento giornaliero ai soli traghetti, o un ancor più economico abbonamento ai soli bus.

La squadra italiana vorrà visitare il maggior numero di attrazioni possibile e per questo motivo Monica, la responsabile dell’organizzazione, ha deciso di cercare un buon compromesso tra il prezzo dei biglietti e le attrazioni che sarà possibile raggiungere partendo dall’hotel. Data una lista di attrazioni e la mappa dei collegamenti delle diverse linee del trasporto pubblico, il vostro compito è quello di aiutare Monica a capire quante attrazioni sono raggiungibili per ogni possibile scelta dei biglietti per i trasporti pubblici.

Per esempio, possiamo fare riferimento alla figura qui sopra, dove ad ogni fermata è associato un cerchio (o un quadrato nel caso di luogo di attrazione) e i collegamenti sono:

1. tratteggiati – collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi);
2. rossi – bus a pagamento;
3. gialli – traghetto.

Il punto di partenza della rappresentativa italiana è la fermata numero 0; le attrazioni da vedere sono quelle rappresentate con un quadrato, numerate rispettivamente 8, 12, 15, 22 e 28. Come si può vedere, spostandosi con i mezzi gratuiti si raggiungono solo due attrazioni (la numero 8 e la numero 14); comprando il biglietto del bus si raggiungono tutte le attrazioni; comprando il biglietto del traghetto si raggiungono, oltre alla 8 e la 14, anche la 12 e la 15 per un totale di quattro attrazioni. Il biglietto combinato, in questo caso, raggiunge tutte le attrazioni.

Dati di input

Il file input.txt è composto da 1+A+Mg+Mb+Mt righe. La prima riga contiene cinque interi positivi separati da uno spazio, che rappresentano il numero N delle fermate, il numero A di attrazioni, il numero Mg dei collegamenti gratuiti, il numero Mb dei collegamenti via bus e il numero Mt dei collegamenti via traghetto. Ogni fermata è rappresentata da un intero compreso tra 0 e N-1. Le successive A righe contengono ognuna una fermata (un intero compreso tra 0 e N-1) corrispondente ad una delle attrazioni che la rappresentativa italiana può visitare. Ognuna delle successive Mg+Mb+Mt righe contiene un collegamento del trasporto pubblico, rappresentato da due interi positivi: le fermate collegate. Le prime Mg righe contengono i collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi), poi le successive Mb contengono i collegamenti del bus a pagamento e infine le ultime Mt righe contengono i collegamenti dei traghetti. Il punto di partenza della rappresentativa italiana è la sempre la fermata numero 0.

Dati di output

Il file output.txt è composto da 4 righe contenenti ognuna un intero non negativo, rispettivamente, il numero di attrazioni raggiungibili:

1. senza comprare biglietti (solo con mezzi gratis);
2. comprando solo il biglietto giornaliero dei bus;
3. comprando solo il biglietto giornaliero dei traghetti;
4. comprando entrambe le tipologie di biglietti.

Assunzioni

• 2 ≤ N ≤ 1000

• N ≤ Mg+Mb+Mt ≤ 10000

Esempi di input/output

Nota/e

• Il secondo caso di esempio corrisponde alla situazione presentata in figura.

• Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio.