30ος ΠΔΠ B' Φάση Λυκείου
Η αγορά (agora)

Στην αγορά της πόλης φτάνουν οι κάτοικοι των κοντινών χωριών για να κάνουν προμήθειες. Υπάρχουν \(N\) χωριά γύρω από την πόλη. Οι κάτοικοι του πρώτου χωριού πηγαίνουν στην πόλη κάθε \(x_1\) μέρες για ανεφοδιασμό, αυτοί του δεύτερου χωριού κάθε \(x_2\) μέρες, κ.ο.κ. Σήμερα έτυχε να συναντηθούν στην αγορά της πόλης οι κάτοικοι όλων των χωριών — αυτό συμβαίνει αρκετά σπάνια. Βρείτε μετά από πόσες μέρες θα συναντηθούν πάλι στην αγορά της πόλης οι κάτοικοι τουλάχιστον \(N-1\) χωριών.

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο, αφού διαβάσει το πλήθος των χωριών και τη συχνότητα επίσκεψης των κατοίκων τους στην αγορά της πόλης, θα βρίσκει τον ελάχιστο αριθμό ημερών μετά από τις οποίες θα συναντηθούν οι κάτοικοι τουλάχιστον \(N−1\) χωριών. Αν εκείνη τη μέρα λείπουν οι κάτοικοι ενός χωριού, το πρόγραμμά σας πρέπει επίσης να βρίσκει ποιο θα είναι αυτό το χωριό.

Αρχεία εισόδου

Τα αρχεία εισόδου με όνομα agora.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό \(N\). Τον αριθμό των χωριών (\(1 \leq N \leq 1.000.000\)). Η δεύτερη γραμμή περιέχει \(N\) θετικούς ακέραιους αριθμούς \(x_i\), χωρισμένους μεταξύ τους με ένα κενό διάστημα. Κάθε αριθμός \(x_i\) (\(1 \leq x_i \leq 1.000.000\)) εκφράζει κάθε πόσες μέρες έρχονται στην αγορά της πόλης οι κάτοικοι του \(i\)-οστού χωριού. Θεωρήστε δεδομένο ότι οι κάτοικοι όλων των χωριών θα συναντηθούν και πάλι στην αγορά της πόλης το πολύ σε \(10^{18}\) μέρες (τιμή πολύ μεγάλη για να αναπαρασταθεί με αριθμό των \(32\) bit).

Αρχεία εξόδου

Τα αρχεία εξόδου με όνομα agora.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει ακριβώς δύο ακέραιους αριθμούς. Ο πρώτος είναι ο ζητούμενος αριθμός ημερών, μετά από τις οποίες οι κάτοικοι τουλάχιστον \(N-1\) χωριών θα ξανασυναντηθούν στην αγορά της πόλης. Ο δεύτερος αριθμός είναι μηδέν (\(0\)) αν εκείνη τη μέρα θα συναντηθούν πάλι οι κάτοικοι όλων των χωριών. Διαφορετικά, θα είναι ο αύξων αριθμός του χωριού που οι κάτοικοί του θα λείπουν. (Η αρίθμηση των χωριών είναι από \(1\) έως και \(N\).)

Παραδείγματα Αρχείων Εισόδου - Εξόδου

1^o

agora.in	agora.out
10 1 2 3 4 5 6 7 8 9 10	360 7

Εξήγηση: Σε αυτό το παράδειγμα, μετά από \(360\) μέρες θα ξανασυναντηθούν οι κάτοικοι όλων των χωριών, εκτός από του 7^ου.

2^o

agora.in	agora.out
9 10 14 15 30 21 5 40 4 8	840 0

Εξήγηση: Σε αυτό το παράδειγμα, μετά από \(840\) μέρες θα ξανασυναντηθούν οι κάτοικοι όλων των χωριών. Καμία προηγούμενη μέρα δε θα συναντηθούν οι κάτοικοι τουλάχιστον \(8\) χωριών.

3^o

agora.in	agora.out
5 25065 3575 12305 88590 1758	25845383485350 4

Εξήγηση: Σε αυτό το παράδειγμα, στο οποίο φαίνεται ότι οι κάτοικοι των χωριών είναι υπεραιωνόβιοι και επίσης δεν τρώνε πολύ, θα συναντηθούν οι κάτοικοι τεσσάρων από αυτά (εκτός του 4^ου) μετά από \(25\), \(845\), \(383\), \(485\), \(350\) μέρες (περισσότερες από εικοσιπέντε τρισεκατομμύρια!)

Παρατηρήσεις