Olimpiadi di Informatica - Selezione Regionale 2007 problema Giri sulla Scopa Nimbus3000 (NIMBUS) - livello difficoltà 2 soluzione in C++ proposta da Paola Masin

/* Selezione regionale 2007 - Giri sulla Scopa Nimbus3000 (NIMBUS) Difficoltà D = 2 Descrizione del problema Al celebre maghetto Harry Potter è stata regalata una scopa volante modello Nimbus3000 e tutti i suoi compagni del Grifondoro gli chiedono di poterla provare. Il buon Harry ha promesso che nei giorni a venire soddisferà le richieste di tutti, ma ogni ragazzo è impaziente e vuole provare la scopa il giorno stesso. Ognuno propone ad Harry un intervallo di tempo della giornata durante il quale, essendo libero da lezioni di magia, può fare un giro sulla scopa, e per convincerlo gli offre una fantastica caramella Tuttigusti+1. Tenendo presente che una sola persona alla volta può salire sulla Nimbus3000 in ogni istante di tempo, Harry decide di soddisfare, tra tutte le richieste dei ragazzi, quelle che gli procureranno la massima quantità di caramelle (che poi spartirà coi suoi amici Ron e Hermione). Aiutalo a trovare la migliore soluzione possibile. Dati di input Il file input.txt contiene nella prima riga un intero positivo N, che indica il numero di richieste, che sono numerate da 1 a N. Ognuna delle successive N righe contiene una coppia di interi. Ciascuna di tali righe contiene una coppia di interi positivi A e B, separati da uno spazio, a rappresentare la richiesta di poter utilizzare la scopa dall'istante iniziale A fino all'istante finale B, in cambio di una caramella (dove A < B). A tal fine, il tempo è diviso in istanti discreti numerati a partire da 1 in poi. Dati di output Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il massimo numero di caramelle che Harry può ottenere. Assunzioni •1 < N < 1000. •Gli interi nelle N coppie sono distinti l'uno dall'altro (non esistono due interi uguali, anche in coppie diverse). Esempi di input/output +----------+----------+ |input.txt |output.txt| +----------+----------+ | 1 5 | 2 | | 3 7 | | | 9 11 | | | 10 12 | | | 6 13 | | +----------+----------+ Note •Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio rilevante. --------------------------------------------------------------------------*/ /* Ninbus - Selezione Regionale 2007 - NIMBUS - programma di Paola Masin La soluzione si basa sul fatto che i valori sono tutti diversi e quindi si può memorizzare il secondo estremo in un vettore dove l'indice è il primo estremo e poi si possono eliminare gli elementi che contengono come sottoinsieme un altro elemento. Allora basta contare, perchè è sempre il primo valore che si incontra quello che vale */ #include <fstream> #include <iostream> using namespace std; int main(){ ifstream fLegggi("input.txt"); int N; fLegggi>>N; int i,j, primo, secondo, risultato=0, minX, maxX; // min e max per ridurre int destro[1001]; // non uso la posizione 0 il range di scansione for (i=1;i<=1000;i++) // inizializzo la matrice a 0, destro[i]=0; // significa che non c'è intervallo che finisce lì } fLegggi>>primo; fLegggi>>secondo; destro[primo]=secondo; minX=maxX=primo; for (i=2;i<=N;i++) { //carico i dati fLegggi>>primo; fLegggi>>secondo; destro[primo]=secondo; if (minX>primo) minX=primo; if (maxX<primo) maxX=primo; } fLegggi.close(); // cancello gli inutili for (i=minX;i<=maxX;i++) { j=i+1; while (destro[i]!=0 && j<=maxX) { if (destro[j]!=0 && destro[j]<destro[i] ) destro[i]=0; j++; } } for (i=minX;destro[i]==0;i++); //cerco il primo valido risultato=1; while (destro[i]<maxX){ risultato++; i=destro[i]+1; while (destro[i]==0) i++; } ofstream fScrivi("output.txt"); fScrivi<< risultato; fScrivi.close(); return 0; }

Testo del problema