Fase Territoriale 2002
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 disponibilità 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 più ore ci siano più 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 è 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 è -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 disponibilità potrebbe coprire la mezzanotte; ad esempio la disponibilità 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).Esempi di input/output
input.txt output.txt 3
0 7
8 15
14 207 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-1 1
94 22
/*
www.valcon.it
OII 2002 - Fase territoriale - TURNI DI GUARDIA
*/
#include
#define N_ORE 96
int ore[N_ORE]; // 0, 0, ...
int main()
{
FILE* fin =fopen( "input.txt", "r");
FILE* fout=fopen("output.txt", "w");
int N, // numero guardie disponibili
dalle, // inizio turno
alle; // fine turno
fscanf(fin, "%d", &N);
for(int i=1; i <= N; i++)
{
fscanf(fin, "%d %d", &dalle, &alle);
if(alle < dalle)
alle += N_ORE;
for(j=dalle; j < alle; j++)
ore[j%N_ORE]=1;
}
int risultato=-1;
for(int i=0; i < N_ORE && risultato == -1; i++)
if(ore[i] == 0)
risultato=i;
fprintf(fout, "%d", risultato);
return 0;
}