LabASD - Numero di telefono ripetuto

Siete stati assunti come consulenti dalla IATM S.p.A. (Importante Azienda di Telefonia Mobile) che è alle prese con il problema seguente. L’azienda ha un file contenente \(n\) numeri di telefono, \(200000 < n \leq \mathtt{MAXN}\). Tutti i numeri hanno sei cifre, la prima delle quali può essere 3 oppure 5; i numeri di telefono hanno quindi la forma 3xxxxx oppure 5xxxxx, dove le x sono cifre numeriche arbitrarie. Il contenuto del file non è necessariamente ordinato.

Da quanto detto sopra si può dedurre che ci sia sicuramente almeno un numero di telefono che compare più di una volta, perché il file contiene più elementi di quanti siano i possibili numeri distinti. Il vostro compito è di implementare un algoritmo efficiente che stampi a video il più piccolo numero di telefono che compare più di una volta nel file di input.

Il file di input ha \(n\) righe, ciascuna delle quali contenente un numero di telefono (si consideri questo esempio). Il programma riceve il nome del file di input come unico parametro sulla riga di comando, e deve stampare a video il minimo numero ripetuto presente nel file.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic telefono.c -o telefono

Per eseguire in ambiente Linux/MacOSX:

    ./telefono nome_file

Per eseguire in ambiente Windows:

    .\telefono nome_file

dove nome_file è il nome del file di input contenente l’elenco dei numeri di telefono.

Per approfondire

Un aspetto complicato di questo esercizio è la generazione dei file di input (che non è richiesta, ma che ho dovuto fare io per preparare gli input). Dato un intero \(n > 200000\) e un numero di telefono \(t\), come fareste per generare un file di input composto da \(n\) numeri di telefono come sopra, non necessariamente in ordine, in cui il minimo valore ripetuto sia esattamente \(t\)?

File

• telefono.c
• telefono.in (output atteso)
• telefono1.in
• telefono2.in
• telefono3.in
• telefono4.in