Interrogazioni ordinate

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: CiCj per ogni (i, j) con ij.

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

Notice: This work is licensed under a BY-NC-SA. Permalink: Interrogazioni ordinate

Comments are closed.