La commissione istituita per l’esame di maturità della classe di Luca ha ricevuto dal MIUR l’elenco dei codici SIDI di tutti gli N alunni da esaminare, con il suggerimento che l’ordine delle interrogazioni all’esame orale segua, in ordine crescente, il codice SIDI.
Ciò significa che uno studente i dovrebbe essere interrogato prima di uno studente j se il codice SIDI del primo è inferiore a quello del secondo (ovvero Ci < Cj).
Seguire le indicazioni del Ministero comporterebbe però una certa confusione tra gli studenti, abituati a essere interrogati in ordine per numero crescente di registro (numero 1, numero 2, . . . , numero N).
Assecondando le richieste degli studenti, la commissione stabilisce di adottare la modalità consueta (in ordine per numero crescente di registro), ma vuole prima stabilire qual è l’impatto di questa scelta.
In particolare si vuole stabilire per quante coppie di studenti (i, j) cambierebbe l’ordine di interrogazione, ovvero per quante coppie (i, j) i verrebbe interrogato prima di j con uno dei due metodi ma dopo j con l’altro.
Dati di input
Il file input.txt è composto da 2 righe.
- La prima riga contiene l’intero N, il numero di studenti.
- La seconda riga contiene N interi positivi separati da spazio: i codici SIDI degli alunni dal numero 1 al numero N.
Dati di output
Il file output.txt contiene un singolo intero: il numero di coppie di studenti che cambiano l’ordine relativo di interrogazione tra il primo e il secondo metodo.
Attenzione: la risposta al problema supera, in alcuni casi, 232.
Se si lavora, ad esempio, in C/C++ è quindi richiesto l’uso del tipo long long al posto di int.
Assunzioni
- 2 ≤ N ≤ 200 000
- 1 ≤ Ci ≤ 10000000 per ogni i=0. . .N−1.
- Il codice SIDI è univoco: Ci ≠ Cj per ogni (i, j) con i ≠ j.
Esempi di input/output
input.txt | output.txt |
4 14 63 22 31 |
2 |
5 84 31 57 25 66 |
6 |
Spiegazione
Nel primo esempio considera le seguenti coppie di studenti il cui ordine cambia tra i due metodi:
- Codici SIDI 63 e 22 (63 > 22), sono rispettivamente i numeri 2 e 3 nel registro (2 < 3).
- Codici SIDI 63 e 31 (63 > 31), sono rispettivamente i numeri 2 e 4 nel registro (2 < 4).
Tutte le altre coppie mantengono la stessa posizione relativa: gli studenti della coppia verranno interrogati nello stesso ordine indipendentemente dal metodo utilizzato.
Ottiene il 50% su array non troppo grandi
/* www.valcon.it ABC - Interrogazioni ordinate */ #include#include #define NMAX 200000 using namespace std; long ELENCO[NMAX+1]; int main() { ifstream fin ( "input.txt"); ofstream fout("output.txt"); long N; fin >> N; for(long i=1; i <= N; i++) fin >> ELENCO[i]; long long int cambi=0; for(long i=1; i < N; i++) for(long j=i+1; j <= N; j++) if(ELENCO[i] > ELENCO[j]) cambi++; fout << cambi; return 0; }