×

Salve, una mia amica mi ha fatto vedere alcuni esercizi per le olimpiadi d’informatica di questo dicembre. Non avendo le soluzioni non posso sapere se l’ho risolto o meno. Uno dei quesiti, il primo, è questo, l’unico che ho provato a fare.:

1. Turni di Guardia (turni) (quoziente di difficolta’ 2)

Il Sig. Tesga, dirigente di un’importante azienda del pianeta Planet, vuole che la sede centrale della sua azienda sia sorvegliata da guardie armate durante tutto l’arco della giornata (il motivo non ci è noto…).
Il problema è che un giorno su Planet dura l’equivalente di 4 giorni terrestri (quindi ben 96 ore terrestri!) mentre il bioritmo di un abitante è comparabile a quello di un terrestre, perciò sarebbe impensabile chiedere a un abitante di Planet di lavorare per più di 8 ore al giorno. In particolare assumiamo che le ore su Planet siano numerate a partire dall’ora 0 all’ora 95.
Il Sig. Tesga deve inoltre fare i conti con un numero limitato di richieste di lavoro di abitanti che danno la loro disponibilità a montare di guardia ogni giorno per un dato numero di ore (sempre minore o uguale a 8) da una data ora x a un’altra ora y; ad esempio un abitante potrebbe offrire la sua disponibilita’ a lavorare ogni giorno per sette ore dalle ore 2 alle ore 9.
Il vostro compito è quello di scrivere un programma che aiuti il Sig. Tesga a sapere se le richieste di lavoro che ha a disposizione sono sufficienti ad approntare una serie di turni di guardia che copra un’intera giornata (ovvero se non vi sono ore del giorno durante le quali non vi è nessun abitante disponibile a montare di guardia). Nota bene la soluzione potrebbe prevedere che in una o piu’ ore ci siano piu’ di un abitante al lavoro.
File di input
Il file input.txt contiene sulla prima riga un intero N, il numero di richieste di lavoro che il Sig. Tesga ha a disposizione. Ognuna delle N righe successive contiene 2 interi, x e y separati da uno spazio. Alla riga i (1≤i≤N), x e y indicano rispettivamente l’ora (secondo l’ora di Planet) dalla quale e fino alla quale l’ i-esimo abitante richiedente lavoro è disposto a montare di guardia.
File di output
Il file di output contiene una sola riga terminata da un a-capo. Tale riga e’ costituita da un solo intero. Se, con le richieste che ha a disposizione, il Sig. Tesga riesce a coprire un intera giornata di turni guardia tale intero e’ -1. In caso contrario, tale intero indica la prima ora che non può essere coperta da alcun turno di guardia.
Assunzioni
• Un giorno su Planet dura 96 ore, dall’ora 0 all’ora 95. Ogni periodo di disponibilità offerto dai richiedenti lavoro ha sempre durata minore od uguale ad 8 ore.
• La durata in ore della disponibilità di un richiedente è sempre un numero intero positivo.
• Se un richiedente dà disponibilità dall’ora x all’ora y, l’ora y è la prima a non essere coperta da quel richiedente. Per esempio, la disponibilità dalle 2 alle 10 copre un periodo di 8 ore (dalle 2 fino alle 9 ed escludendo l’ora 10). Notate inoltre che la disponibilita’ potrebbe coprire la mezzanotte; ad esempio la disponibilita’ dalle 94 alle 2 è lecita e indica che il richiedente è disposto a montare di guardia per 4 ore dall’ora 94 fino alle 2 (del giorno successivo).
• Il file di input non contiene altri caratteri oltre a quelli indicati nel testo.
• Il file di output non deve contenere altri caratteri oltre a quelli contenuti nel testo; in particolare non ci devono essere linee di separazione fra le linee di output.
• Il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output.
• I file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un’istruzione tipo

fr = fopen( “input.txt”, “r” );
fw = fopen( “output.txt”, “w” );

• e in Pascal con un’istruzione tipo

assign( fr, ‘input.txt’ ); reset( fr );
assign( fw, ‘output.txt’ ); rewrite( fw );

Esempi di input/output
Esempio 1
File input.txt
3
0 7
8 15
14 20
File output.txt
7

Esempio 2
File input.txt
14
1 7
10 15
14 20
20 28
28 36
36 44
44 52
52 60
60 68
68 76
76 84
84 90
6 10
90 2

File output.txt
-1

Esempio 3

File input.txt
1
94 2

File output.txt

2

Qualcuno saprebbe dirmi il risultato?

- ho anche altri due, ma mi basta questo, grazie mille ^^ -
per chiunque sapesse la risposta può gentilmente mandare una mail a questo indirizzo?:

antony_dalis@hotmail.it

Io alle selezioni scolastiche ho fatto uno scarsetto 29 su 40. Alle territoriali (di provincia credo, comunque nella provincia di Vicenza) ho fatto 2 esercizi su 3… A te come è andata?