Tag Archives: vector

Due sequenze

Correttore online – Intermedi

Siano date due sequenze così definite

  • a1=2, a2=3, a3=4, a4=7, e (per n > 4) an=bn-1+bn-3
  • bn è una sequenza crescente di numeri non presenti in an.

Così, i numeri della successione an sono 2, 3, 4, 7, 13, 15, … e i numeri della successione bn sono 1, 5, 6, 8, 9, 10, …
Dato un intero n, scrivete un programma per calcolare an e bn.

Dati di input

Il file di input contiene il numero intero n (0 < n < 10001).

Dati di output

La prima riga del file di output deve contenere an, la seconda bn.

Esempi di input/output

input.txt output.txt
4
7
8
10
25
16

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.


A spasso per Brisbane

Fase Territoriale 2013

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.

2013_brisbanePer esempio, possiamo fare riferimento alla figura, 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

input.txt output.txt
6 2 2 4 2
1
5
0 1
2 5
0 3
1 3
2 4
4 5
1 2
3 4
1
1
2
2
30 5 18 14 11
8
12
15
22
28
0 5
0 24
1 8
1 25
2 3
2 23
5 11
8 14
11 16
13 17
14 19
16 20
18 22
19 21
20 22
21 22
23 24
23 25
1 4
2 28
2 29
4 7
4 8
7 29
12 26
14 15
15 19
15 21
17 21
18 21
26 27
27 28
3 7
3 25
6 9
6 13
7 15
9 10
10 17
12 16
12 18
13 15
17 18
2
5
4
5

Nota

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