AlgoNTUA Day 1: Συνοστισμός στο γραφείο

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

Συνοστισμός στο γραφείο

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

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα το οποίο, αφού διαβάσει το πλήθος των φοιτητών και τη συχνότητα επίσκεψης τους στο γραφείο του κυρίου Ζάχου, θα βρίσκει τον ελάχιστο αριθμό ημερών μετά από τις οποίες θα συναντηθούν τουλάχιστον N - 1 φοιτητές. Αν εκείνη τη μέρα λείπει ένας φοιτητής, το πρόγραμμά σας πρέπει επίσης να βρίσκει ποιος θα είναι αυτός.

Είσοδος:

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

Έξοδος:

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

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

STDIN (agora.in)

10
1 2 3 4 5 6 7 8 9 10

STDOUT (agora.out)

360 7

Σε αυτό το παράδειγμα, μετά από 360 μέρες θα ξανασυναντηθούν όλοι οι φοιτητές, εκτός από τον 7^\text{ο}.


2o

STDIN

9
10 14 15 30 21 5 40 4 8

STDOUT

840 0

Σε αυτό το παράδειγμα, μετά από 840 μέρες θα ξανασυναντηθούν όλοι οι φοιτητές. Καμία προηγούμενη μέρα δε θα συναντηθούν τουλάχιστον 8 φοιτητές.


3o

STDIN

5
25065 3575 12305 88590 1758

STDOUT

25845383485350 4

Σε αυτό το παράδειγμα, στο οποίο φαίνεται ότι οι φοιτητές είναι υπεραιωνόβιοι και επίσης δεν πάνε συνχά στον κύριο Ζάχο, θα συναντηθούν τέσσερις εξ αυτών (εκτός του 4^\text{ου}) μετά από 25.845.383.485.350 μέρες (περισσότερες από εικοσιπέντε τρισεκατομμύρια!)

Παρατηρήσεις:
  • Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
  • Μέγιστος χρόνος εκτέλεσης: 1 sec.
  • Μέγιστη διαθέσιμη μνήμη: 64 MB.

Comments

There are no comments at the moment.