Σημείωση : Ενδεικτικός κώδικας τον οποίο μπορείτε να τροποποιήσετε υπάρχει εδώ : http://pastebin.com/x0inkunb
… Οι αρχαίοι Έλληνες διακατέχονταν από αγωνιστικό πνεύμα, το οποίο έπαιξε καθοριστικό ρόλο σε πολλές πτυχές του πολιτισμού τους… οι ραψωδοί συναγωνίζονταν στην απαγγελία κατά τη γιορτή των Παναθηναίων… (πηγή http://www.ime.gr/chronos/04/gr/culture/421rel_rituals_competit.html )
Μετά από λίγο καιρό οι αγώνες μνήμης δεν είχαν κανένα νόημα, καθώς οι ραψωδοί γνώριζαν απ έξω την Ιλιάδα και την Οδύσσεια, ισοβαθμώντας έτσι στην πρώτη θέση.
Επινόηθηκε λοιπόν ένα καινούριο άθλημα μνήμης. Δίνεται στους ραψωδούς ένας πίνακας με Ν αριθμούς και κάθε λεπτό ο κριτής μπορεί να αλλάξει έναν από αυτούς. Ο ραψωδός πρέπει να θυμάται όλες τις αλλαγές που έχουν γίνει, διότι ο κριτής μπορεί να του υποβάλλει ερωτήσεις του τύπου : «Ποιο ήταν το άθροισμα των αριθμών από τη θέση 5 ως τη θέση 25, το 30στο λεπτό του παιχνιδιού;».
Δυστυχώς υπήρχαν διαγωνιζόμενοι που αποκτούσανε πρόσβαση στα θέματα, κι έτσι απομνημόνευαν από την προηγούμενη μέρα τις απαντήσεις. Μετά από ομολογουμένως λίγη σκέψη αποφασίστηκε το εξής. Στα χαρτιά τους οι κριτές θα γράφουνε μόνο τον αρχικό πίνακα και ένα ερώτημα. Για να βρούνε την i-οστή ανανέωση και το (i+1)-οστό ερώτημα χρησιμοποιούν τους εξής τύπους (ανανεώσεις και ερωτήματα συμβαίνουν πάντα εναλλάξ) :
Θέση ανανέωσης = ((10.301 * X ) mod N) + 1
Νέα τιμή = ((10.889 * Χ ) mod 20.000 ) + 1
Αρχή διαστήματος ερωτήματος = ((33.617 * X ) mod N) + 1
Τέλος διαστήματος ερωτήματος = Αρχή διαστήματος + ((58.049 * X ) mod (N-Αρχή_Διαστήματος+1))
Χρόνος στον οποίο αναφέρεται το ερώτημα = (81.517 * X ) mod (i+1)
όπου Χ η απάντηση στο i-οστό ερώτημα.
Έτσι αν κάποιος διαγωνιζόμενος αποκτήσει πρόσβαση στο χαρτί με τα θέματα, θα δει μόνο τον αρχικό πίνακα και το πρώτο ερώτημα, κι αφού δε γνωρίζει τον τρόπο με τον οποίο δημιουργούνται οι ανανεώσεις/ερωτήματα, δε μπορεί να γνωρίζει τι ακολουθεί.
Η τεχνική αυτή (security through obscurity), η υποτιθέμενη ασφάλεια δηλαδή που αποκτάς επειδή οι αντίπαλοί σου δεν ξέρουν πώς λειτουργείς, είναι εντελώς λάθος. Απόδειξη : Σήμερα που γνωρίζουμε τον τρόπο με τον οποίο δημιουργούνταν τα ζεύγη ανανεώσεων/ερωτημάτων είμαστε σε θέση να ζωντανέψουμε την ιστορία επαναλαμβάνοντας την διαδικασία που ακολουθούσαν οι κριτές.
Στην πρώτη γραμμή δίνονται δύο θετικοί ακέραιοι Ν και Μ, το πλήθος των στοιχείων του πίνακα και το πλήθος των ζευγαριών ανανέωση-ερώτημα που ακολουθούν μετά το πρώτο ερώτημα.
Στη δεύτερη γραμμή δίνονται Ν θετικοί ακέραιοι Ai, τα στοιχεία του πίνακα.
Στην τρίτη γραμμή δίνονται δύο θετικοί ακέραιοι X και Y που περιγράφουν το πρώτο ερώτημα, η αρχή και το τέλος του διαστήματος για το οποίο μας ενδιαφέρει η απάντηση. Εννοείται ο χρόνος μηδέν, αφού δεν έχει συμβεί καμμία ανανέωση προηγουμένως.
Μ+1 γραμμές, η i-οστή από αυτές τις γραμμές αντιπροσωπεύει την απάντηση στο i-οστό ερώτημα.
1 <= Ν, Μ <= 100.000
1 <= Ai <= 20.000
1 <= X, Υ <= Ν
5 2 3 9 19 4 1 2 4
32 1 8454
Το πρώτο ερώτημα είναι το 2-4, προφανώς στον χρόνο 0.
Επομένως η απάντηση είναι 9+19+4 = 32.
Εφαρμόζοντας τους τύπους, με Χ=32, παίρνουμε ότι πρέπει να ανανεώσουμε την θέση 3 βάζοντας τον αριθμό 8449, κι ότι το επόμενο ερώτημα είναι το 5-5, σε χρόνο 0.
Συνεπώς ο πίνακας στον χρόνο 1 είναι
3 9 8449 4 1,
κι η απάντηση στο ερώτημα είναι 1.
Προσέξτε ότι το ερώτημα αναφέρεται στον χρόνο 0, όπου ο πίνακας ήταν :
3 9 19 4 1.
Παρομοίως, με Χ = 1 προκύπτει ανανέωση της θέσης 2 με 10890, και ερώτημα 3-5 στον χρόνο 1.
Ο πίνακας στον χρόνο 2 γίνεται :
3 10890 8449 4 1,
και η απάντηση είναι 8449+4+1 = 8454