Numero di Array Unici
Dato
n array, ciascuno di lunghezza l (ovvero l interi), si richiede di calcolare quanti di questi array sono unici. Due array si considerano unici se differiscono almeno in un elemento.Tuttavia, confrontare gli array uno a uno potrebbe richiedere troppo tempo. Un approccio alternativo consiste nell’applicare una funzione di hash (a scelta) a ogni array e poi confrontare i valori hash.
Dopo aver calcolato l’hash di un array, è possibile prendere un grande array di dimensione
m e inizializzarlo a zero. Ogni volta che si ricava un hash, si “segna” (imposta a 1) la posizione corrispondente in questo grande array. Al termine, per scoprire quanti array diversi si sono incontrati, sarà sufficiente contare i valori pari a 1 in quest’ultimo array.È importante notare che la funzione di hash deve essere utilizzata in modulo
m, così che gli indici rientrino nell’intervallo [0; m).Dati in Ingresso
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ 1000) e l (1 ≤ l ≤ 1000).Le successive
n righe contengono l interi separati da uno spazio (0 ≤ ≤ ).Risultato
Il programma deve stampare il numero di array unici.
Esempi
Input | Output |
4 3
1 2 3
3 2 1
2 5 3
3 2 1 | 3 |
2 3
1 2 3 4
1 2 3 4 | 1 |
Suggerimento
Se la funzione di hash non è abbastanza efficace e si verificano ancora collisioni, prova a confrontare i risultati ottenuti con 2 funzioni di hash diverse: in questo modo l’algoritmo risulta due volte più robusto alle collisioni.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB