La vita non è facile nei quattro accampamenti fortificati di Laudanum, Petibonum, Baobarum e Aquarium, che circondano il villaggio dell'Armorica abitato da irriducibili galli. I centurioni hanno grandi difficoltà nel mantenere la disciplina delle proprie legioni, e sono costretti a tenere i propri soldati sotto strettissimo controllo.
La situazione è complicata dal fatto che i turni dei soldati sono estremamente irregolari. Più precisamente: sono dati N intervalli di tempo, ciascuno dei quali corrisponde a un turno (cioè alla presenza continuativa di un soldato per quell'intervallo di tempo); dovete stabilire il minor numero possibile di turni da scegliere in modo tale che ogni altro turno sia coperto almeno in parte da uno dei turni scelti.
Il file di input, di nome input.txt, contiene sulla prima riga un intero N, che è il numero dei turni. Su ciascuna delle successive N righe ci sono due interi non negativi a e b, separati da uno spazio, che corrispondono a un intervallo di tempo [a, b]. Più precisamente, potete assumere che:
Il file di output, di nome output.txt, contiene un solo intero M, che deve soddisfare le seguenti proprietà:
L'esempio che segue è quello mostrato in figura:
File input.txt | File output.txt |
8 0 3 1 6 2 5 4 9 7 8 10 12 11 14 13 15 | 3 |