Πρόκληση Φυλακισμένων

Σε μια φυλακή, υπάρχουν ~500~ φυλακισμένοι. Μια μέρα, ο φύλακας τους προσφέρει την ευκαιρία να διεκδικήσουν την ελευθερία τους. Τοποθετεί δυο τσάντες με χρήματα σε ένα δωμάτιο, την τσάντα A και την τσάντα B. Κάθε τσάντα περιέχει από ~1~ έως ~N~ κέρματα, συμπεριλαμβανομένων. Το πλήθος των κερμάτων στην τσάντα Α είναι διαφορετικό από το πλήθος των κερμάτων στην τσάντα B. Ο φύλακας παρουσιάζει στους φυλακισμένους μια πρόκληση. Στόχος των φυλακισμένων είναι να εντοπίσουν την τσάντα με τα λιγότερα κέρματα.

Το δωμάτιο, εκτός από τις τσάντες με τα χρήματα, έχει και έναν ασπροπίνακα. Οποιαδήποτε στιγμή, ένας μόνο αριθμός πρέπει να γράφεται στον ασπροπίνακα. Αρχικά, ο αριθμός στον ασπροπίνακα είναι ~0~.

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

• Να αντικαταστήσει τον αριθμό στον ασπροπίνακα με έναν μη-αρνητικό ακέραιο κι έπειτα να αποχωρήσει από το δωμάτιο. Σημειώστε ότι ο φυλακισμένος μπορεί είτε να αλλάξει είτε να διατηρήσει τον τρέχοντα αριθμό. Η πρόκληση συνεχίζεται μετά από αυτό (εκτός έαν όλοι οι ~500~ φυλακισμένοι έχουν ήδη μπει στο δωμάτιο).
• Να προσδιορίσει μια τσάντα ως αυτή που έχει τα λιγότερα κέρματα. Αυτή η ενέργεια τερματίζει αμέσως την πρόκληση.

Ο φύλακας δεν θα ζητήσει από έναν φυλακισμένο που έχει βγει από το δωμάτιο να ξαναμπεί σε αυτό.

Οι φυλακισμένοι κερδίζουν την πρόκληση εάν ένας από αυτούς προσδιορίσει σωστά την τσάντα με τα λιγότερα κέρματα. Οι φυλακισμένοι χάνουν εάν κάποιος από αυτούς προσδιορίσει λανθασμένα την τσάντα, ή όταν και οι ~500~ έχουν μπει στο δωμάτιο και δεν επιχείρησαν να αναγνωρίσουν την τσάντα με τα λιγότερα κέρματα.

Πριν την έναρξη της πρόκλησης, οι φυλακισμένοι συγκεντρώνονται στην αίθουσα φυλακών για να αποφασίσουν μια κοινή στρατηγική για αυτήν σε τρία βήματα.

• Επιλέγουν έναν μη-αρνητικό ακέραιο ~x~, ο οποίος είναι ο μέγιστος που μπορεί ποτέ να θελήσουν να γράψουν στον ασπροπίνακα.
• Αποφασίζουν, για κάθε αριθμό ~i~ που είναι γραμμένος στον ασπροπίνακα (~0 \le i \le x~), ποια τσάντα πρέπει να ελεγχθεί από έναν φυλακισμένο, ο οποίος διαβάζει τον αριθμό ~i~ στον ασπροπίνακα κατά την είσοδο του στο δωμάτιο.
• Αποφασίζουν ποια ενέργεια πρέπει να εκτελέσει ο φυλακισμένος στο δωμάτιο, αφού μάθει το πλήθος των κερμάτων στην επιλεγμένη τσάντα. Συγκεκριμένα, για κάθε αριθμό ~i~ που είναι γραμμένος στον ασπροπίνακα (~0 \le i \le x~) και για κάθε πλήθος κερμάτων ~j~ που εντοπίστηκε στην ελεγχόμενη τσάντα (~1 \le j \le N~), αποφασίζουν ένα από τα παρακάτω:
  • ποιον αριθμό μεταξύ ~0~ και ~x~ (συμπεριλαμβανομένων) πρέπει να γραφτεί στον ασπροπίνακα ή
  • ποια τσάντα πρέπει να προσδιοριστεί ως αυτή με τα λιγότερα κέρματα.

Όταν κερδίσουν την πρόκληση, ο φύλακας θα απελευθερώσει τους φυλακισμένους αφού υπηρετήσουν ~x~ ακόμη ημέρες.

Σκοπός σας είναι να επινοήσετε μια στρατηγική για τους φυλακισμένους η οποία θα τους εξασφαλίζει την νίκη της πρόκλησης (ανεξάρτητα από το πλήθος των κερμάτων στην τσάντα Α και στην τσάντα Β). Η βαθμολογία της λύσης σας εξαρτάται από την τιμή του ~x~ (δείτε την ενότητα Υποπροβλήματα για περισσότερες λεπτομέρειες).

Λεπτομέρειες Υλοποίησης

Πρέπει να υλοποιήσετε την παρακάτω διαδικασία:

int[][] devise_strategy(int N)

• ~N~: το μέγιστο πλήθος κερμάτων σε κάθε τσάντα.
• Η διαδικασία πρέπει να επιστρέφει έναν πίνακα ~s~ από πίνακες με ~N + 1~ ακεραίους, που αναπαριστούν την στρατηγική σας. Η τιμή του ~x~ είναι το μήκος του πίνακα ~s~ μείον ένα. Για κάθε ~i~ τέτοιο ώστε ~0 \le i \le x~, ο πίνακας ~s[i]~ αναπαριστά τι θα κάνει ο φυλακισμένος αν διαβάσει τον αριθμό ~i~ στον ασπροπίνακα κατά την είσοδο του στο δωμάτιο:
  1. Η τιμή του ~s[i][0]~ είναι ~0~ αν ο φυλακισμένος θα πρέπει να ελέγξει την τσάντα A, ή ~1~ αν ο φυλακισμένος θα πρέπει να ελέγξει την τσάντα B.
  2. Έστω ~j~ το πλήθος των κερμάτων μέσα στην επιλεγμένη τσάντα. Ο φυλακισμένος θα πρέπει να εκτελέσει την παρακάτω ενέργεια:
     • Εάν η τιμή του ~s[i][j]~ είναι ~-1~, ο φυλακισμένος θα πρέπει να προσδιορίσει πως η τσάντα A είναι αυτή με τα λιγότερα κέρματα.
     • Εάν η τιμή του ~s[i][j]~ είναι ~-2~, ο φυλακισμένος θα πρέπει να προσδιορίσει πως η τσάντα Β είναι αυτή με τα λιγότερα κέρματα.
     • Εάν η τιμή του ~s[i][j]~ είναι ένας μη-αρνητικός αριθμός, ο φυλακισμένος θα πρέπει να γράψει αυτόν τον αριθμό στον ασπροπίνακα. Σημειώστε ότι το ~s[i][j]~ θα πρέπει να είναι το πολύ ~x~.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά.

Παράδειγμα

Θεωρείστε την ακόλουθη κλήση:

devise_strategy(3)

Έστω ~v~ δηλώνει τον αριθμό που ο φυλακισμένος διαβάζει από τον ασπροπίνακα κατά την είσοδο του στο δωμάτιο. Μια από τις σωστές στρατηγικές είναι η ακόλουθη:

• Αν ~v = 0~ (συμπεριλαμβανομένου του αρχικού αριθμού), έλεγξε την τσάντα A.
  • Αν περιέχει ~1~ κέρμα, προσδιόρισε την τσάντα A ως αυτή με τα λιγότερα κέρματα.
  • Αν περιέχει ~3~ κέρματα, προσδιόρισε την τσάντα Β ως αυτή με τα λιγότερα κέρματα.
  • Αν περιέχει ~2~ κέρματα, γράψε ~1~ στον ασπροπίνακα (αντικαθιστώντας το ~0~).
• Αν ~v = 1~, έλεγξε την τσάντα B.
  • Αν περιέχει ~1~ κέρμα, προσδιόρισε την τσάντα Β ως αυτή με τα λιγότερα κέρματα.
  • Αν περιέχει ~3~ κέρματα, προσδιόρισε την τσάντα A ως αυτή με τα λιγότερα κέρματα.
  • Αν περιέχει ~2~ κέρματα, γράψε ~0~ στον ασπροπίνακα (αντικαθιστώντας το ~1~). Σημειώστε ότι αυτή η περίπτωση δεν μπορεί να προκύψει, γιατί τότε καταλήγουμε στο συμπέρασμα ότι και οι δύο τσάντες περιέχουν ~2~ κέρματα, το οποίο δεν επιτρέπεται.

Για να δηλωθεί αυτή τη στρατηγική, η διαδικασία θα πρέπει να επιστρέψει [[0, -1, 1, -2], [1, -2, 0, -1]]. Το μήκος του επιστρεφόμενου πίνακα είναι ~2~, επομένως για αυτή την επιστρεφόμενη τιμή, η τιμή του ~x~ είναι ~2 - 1 = 1~.

Περιορισμοί

• ~2 \le N \le 5000~

Υποπροβλήματα

1. (5 βαθμοί) ~N \le 500~, η τιμή του ~x~ δεν πρέπει να είναι μεγαλύτερη από ~500~.
2. (5 βαθμοί) ~N \le 500~, η τιμή του ~x~ δεν πρέπει να είναι μεγαλύτερη από ~70~.
3. (90 βαθμοί) Η τιμή του ~x~ δεν πρέπει να είναι μεγαλύτερη από ~60~.

Εάν σε κάποιο από τα αρχεία ελέγχου, ο πίνακας που επιστρέφεται από την devise_strategy δεν αντιπροσωπεύει μια σωστή στρατηγική, η βαθμολογία της λύσης σας για αυτό το υποπρόβλημα θα είναι ~0~.

Στο υποπρόβλημα 3 μπορείτε να λάβετε μερική βαθμολογία. Έστω ~m~ η μέγιστη τιμή του ~x~ για τους επιστρεφόμενους πίνακες σε όλα τα αρχεία ελέγχου αυτού του υποπροβλήματος. Η βαθμολογία σας για αυτό το υποπρόβλημα υπολογίζεται σύμφωνα με τον παρακάτω πίνακα:

Συνθήκη	Βαθμοί
~40 \le m \le 60~	~20~
~26 \le m \le 39~	~25 + 1.5 \times (40 - m)~
~m = 25~	~50~
~m = 24~	~55~
~m = 23~	~62~
~m = 22~	~70~
~m = 21~	~80~
~m \le 20~	~90~

Υπόδειγμα Βαθμολογητή

O βαθμολογητής διαβάζει την είσοδο με την ακόλουθη μορφή:

• γραμμή ~1~: ~N~
• γραμμή ~2 + k~ (~0 \le k~): ~A[k] \; B[k]~
• τελευταία γραμμή: ~-1~

Κάθε γραμμή εκτός της πρώτης και τις τελευταίας αντιπροσωπεύει ένα σενάριο. Αναφερόμαστε στο σενάριο που περιγράφεται στη γραμμή ~2 + k~ ως σενάριο ~k~. Στο σενάριο ~k~ η τσάντα A περιέχει ~A[k]~ κέρματα και η τσάντα B περιέχει ~B[k]~ κέρματα.

Ο βαθμολογητής αρχικά καλεί την devise_strategy(N). Η τιμή του ~x~ είναι το μήκος του πίνακα που επιστρέφει η κλήση, μείον ένα. Στη συνέχεια, εάν ο βαθμολογητής εντοπίσει ότι ο πίνακας που επιστρέφει η devise_strategy δεν συμμορφώνεται με τους περιορισμούς, όπως αυτοί περιεγράφηκαν στις Λεπτομέρειες Υλοποίησης, τότε τυπώνει ένα από τα παρακάτω μηνύματα σφάλματος και τερματίζει:

• s is an empty array: ~s~ είναι ένας κενός πίνακας (ο οποίος δεν αναπαριστά μια έγκυρη στρατηγική).
• s[i] contains incorrect length: Υπάρχει ένας δείκτης ~i~ (~0 \le i \le x~) τέτοιος ώστε το μήκος του ~s[i]~ δεν είναι ~N + 1~.
• First element of s[i] is non-binary: Υπάρχει ένας δείκτης ~i~ (~0 \le i \le x~) τέτοιος ώστε το ~s[i][0]~ δεν είναι ούτε ~0~ ούτε ~1~.
• s[i][j] contains incorrect value: Υπάρχουν δείκτες ~i, j~ (~0 \le i \le x, 1 \le j \le N~) τέτοιοι ώστε το ~s[i][j]~ δεν είναι μεταξύ ~-2~ και ~x~.

Σε διαφορετική περίπτωση, ο βαθμολογητής παράγει δύο εξόδους.

Πρώτη, ο βαθμολογητής εκτυπώνει την έξοδο της στρατηγικής σας με την ακόλουθη μορφή:

• γραμμή ~1 + k~ (~0 \le k~): η έξοδος της στρατηγικής σας για το σενάριο ~k~. Εάν η εφαρμογή της στρατηγικής οδηγεί στο ότι ένας φυλακισμένος προσδιορίζει την τσάντα Α ως αυτήν με τα λιγότερα κέρματα, τότε η έξοδος είναι ο χαρακτήρας Α. Εάν η εφαρμογή της στρατηγικής οδηγεί στο ότι ένας φυλακισμένος προσδιορίζει την τσάντα Β ως αυτήν με τα λιγότερα κέρματα, τότε η έξοδος είναι ο χαρακτήρας B. Εάν η εφαρμογή της στρατηγικής οδηγεί στο ότι κανένας φυλακισμένος δεν προσδιορίζει μια τσάντα ως αυτήν με τα λιγότερα κέρματα, τότε η έξοδος είναι ο χαρακτήρας X.

Δεύτερη, ο βαθμολογητής γράφει ένα αρχείο log.txt στον τρέχοντα φάκελο με την ακόλουθη μορφή:

• γραμμή ~1 + k~ (~0 \le k~): ~w[k][0] \; w[k][1] \; \ldots~

Η ακολουθία στη γραμμή ~1 + k~ αντιστοιχεί στο σενάριο ~k~ και περιγράφει τους αριθμούς που γράφτηκαν στον ασπροπίνακα. Συγκεκριμένα, το ~w[k][l]~ είναι ο αριθμός που γράφτηκε από τον ~{(l+1)}^{th}~ φυλακισμένο που εισέρχεται στο δωμάτιο.