Μαγικά Φύλλα

Ο Pak Dengklek θα εκτελέσει ένα μαγικό κόλπο. Ο βοηθός του Pak Dengklek, Pak Ganesh, έχει ~N~ αριθμημένα φύλλα από 1 έως \(Β\). Ένας θεατής προσκαλείται στη σκηνή για να επιλέξει ~K~ ξεχωριστά φύλλα από αυτά και να τα δώσει στον Πακ Γκανές. Ο Pak Ganesh βλέπει τα φύλλα, πετάει ένα από τα ~K~ φύλλα, και μετά αφήνει τα υπόλοιπα ~K - 1~ φύλλα με κάποια σειρά στο τραπέζι. Στη συνέχεια, ο Pak Dengklek κοιτάζει τα ~K - 1~ φύλλα στο τραπέζι και πρέπει να μπορεί να προσδιορίσει το φύλλο που πέταξε ο Pak Ganesh.

Προφανώς, ο Pak Dengklek και ο Pak Ganesh δεν πρέπει να έχουν επικοινωνία αμέσως μετά την έναρξη του κόλπου, αλλά μπορούν να προκαθορίσουν τη στρατηγική τους πριν ξεκινήσει το κόλπο. Πρέπει να τους βοηθήσετε σχεδιάζοντας τη στρατηγική τους. Αυτή τη φορά, ο Pak Dengklek και ο Pak Ganesh θα εκτελέσουν αυτό το κόλπο ~Q~ φορές με την ίδια τιμή των ~N~ και ~K~.

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

Θα πρέπει να υλοποιήσετε τις ακόλουθες διαδικασίες:

void init_assistant(int N, int K)

• ~N~ : ο αριθμός των φύλλων στο κόλπο.
• ~K~ : ο αριθμός των φύλλων που επιλέγει ο θεατής.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά, πριν από οποιαδήποτε κλήση της select_cards.

int[] select_cards(int[] cards)

• cards : ένας πίνακας μήκους ~K~, που αποτελείται από τους αριθμούς των φύλλων που επιλέγει ο θεατής σε αύξουσα σειρά.
• Αυτή η διαδικασία θα πρέπει να επιστρέψει τα ~K - 1~ φύλλα που άφησε ο Pak Ganesh στο τραπέζι μαζί με τη σειρά που διατάχθηκαν. Όλα τα στοιχεία πρέπει να είναι μοναδικά και να υπάρχουν στον πίνακα cards.
• Αυτή η διαδικασία καλείται ακριβώς ~Q~ φορές.

void init_magician(int N, int K)

• ~N~ : ο αριθμός των φύλλων στο κόλπο.
• ~K~ : ο αριθμός των φύλλων που επιλέγει ο θεατής.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά, πριν από οποιαδήποτε κλήση της find_discarded_card.

int find_discarded_card(int[] cards)

• cards : ένας πίνακας μήκους ~K - 1~ που αποτελείται από τους αριθμούς των φύλλων που έχουν μείνει στο τραπέζι σε αυτή τη σειρά.
• Αυτή η διαδικασία θα πρέπει να επιστρέψει τον αριθμό του φύλλου που πέταξε ο Pak Ganesh.
• Αυτή η διαδικασία καλείται ακριβώς ~Q~ φορές.

Κάθε δοκιμαστική περίπτωση περιλαμβάνει ένα μόνο σενάριο των ~N~ και ~K~ . Ένα πρόγραμμα που καλεί τις παραπάνω διαδικασίες τρέχει ακριβώς δύο φορές, ως εξής.

Κατά την πρώτη εκτέλεση του προγράμματος:

• Η init_assistant καλείται ακριβώς μία φορά πριν από κάθε κλήση της choose_cards;
• Η choose_cards καλείται ακριβώς ~Q~ φορές. Σε κάθε κλήση τα φύλλα που επιστρέφονται, αποθηκεύονται στο σύστημα βαθμολόγησης.

Κατά τη δεύτερη εκτέλεση του προγράμματος:

• Η init_magician καλείται ακριβώς μία φορά πριν από οποιαδήποτε κλήση της find_discarded_card.
• Η find_discarded_card καλείται ακριβώς ~Q~ φορές. Σε κάθε κλήση, μία \(αυθαίρετη\) εκτέλεση του κόλπου επιλέγεται και τα φύλλα που επιστρέφονται από τη choose_cards χρησιμοποιούνται ως είσοδοι στη find_discarded_card.

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

Παράδειγμα

Εξετάστε την ακόλουθη κλήση:

init_assistant(5, 3)

Υπάρχουν 5 κάρτες που θα χρησιμοποιηθούν σε όλα τα κόλπα, σε καθένα από αυτά θα προσκληθεί ένας θεατής να επιλέξει 3 διαφορετικά φύλλα.

Αφού γίνει η προετοιμασία από τον Pak Ganesh, εξετάστε την ακόλουθη κλήση:

select_cards([1, 2, 3])

Αυτό σημαίνει ότι ο θεατής επέλεξε κάρτες με αριθμούς 1, 2 και 3. Ας υποθέσουμε ότι ο Pak Ganesh είχε πετάξει το φύλλο με νούμερο 1 και το αριστερό φύλλο με νούμερο 3 βρίσκεται πριν από το φύλλο με νούμερο 2 στο τραπέζι, τότε η choose_cards θα πρέπει να επιστρέψει [3, 2].

Εξετάστε μία άλλη πιθανή κλήση:

select_cards([1, 3, 4])

Αυτό σημαίνει ότι ο θεατής επέλεξε κάρτες με αριθμούς 1, 3 και 4. Ας υποθέσουμε ότι ο Pak Ganesh πέταξε το φύλλο με νούμερο 3 και το αριστερό φύλλο με νούμερο 1 βρίσκεται πριν από το φύλλο με νούμερο 4 στο τραπέζι, τότε η choose_cards θα πρέπει να επιστρέψει [1, 4].

Ας υποθέσουμε ότι ο Pak Ganesh έχει αφήσει τα χαρτιά στο τραπέζι για όλες τις εκτελέσεις του κόλπου και εξετάστε την ακόλουθη κλήση:

init_magician(5, 3)

Οι ίδιες πληροφορίες των \(Ν\) και \(Κ\) που κατέχει ο Pak Ganesh δίνονται στον Pak Dengklek.

Αφού γίνει η προετοιμασία από τον Pak Dengklek, εξετάστε την ακόλουθη κλήση:

find_discarded_card([1, 4])

Αυτό σημαίνει ότι ο Pak Dengklek βλέπει τα φύλλα με αριθμούς 1 και 4, με αυτή τη σειρά, στο τραπέζι. Αυτά τα φύλλα είναι ίδια με την επιστρεφόμενη τιμή της choose_cards([1, 3, 4]). Καθώς ο Pak Ganesh πέταξε το φύλλο με νούμερο 3 σε αυτή την εκτέλεση, τότε η find_discarded_card θα πρέπει να επιστρέψει 3.

Εξετάστε μία άλλη κλήση:

find_discarded_card([3, 2])

Αυτό σημαίνει ότι ο Pak Dengklek βλέπει τα φύλλα με αριθμούς 3 και 2, με αυτή τη σειρά, στο τραπέζι. Αυτά τα φύλλα είναι ίδια με την επιστρεφόμενη τιμή της choose_cards([1, 2, 3]). Καθώς ο Pak Ganesh πέταξε το φύλλο με νούμερο 1 σε αυτή την εκτέλεση, τότε η find_discarded_card θα πρέπει να επιστρέψει 1.

Περιορισμοί

• ~2 \le K \le 8~
• ~K \le N \le 10\, 000~
• ~1 \le Q \le 50\, 000~

Για κάθε κλήση της choose_cards:

• ~1 \le \textrm{cards}[i] \le N~ (για κάθε ~i~ έτσι ώστε ~0 \le i \le K-1~)
• Όλα τα στοιχεία των φύλλων είναι διακριτά.

Για κάθε κλήση της find_discarded_card:

• Όλες οι είσοδοι που δίνονται είναι ίδιες με όλες τις ~Q~ τιμές που επιστρέφει η choose_cards με τυχαία σειρά.

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

1. (5 βαθμοί) ~N \le 3, K=2~
2. (11 βαθμοί) ~N \le 5, K=3~
3. (24 βαθμοί) ~N \le 12, K=6~
4. (60 βαθμοί) ~K=8~

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

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

• γραμμή ~1~: ~N~ ~K~ ~Q~
• γραμμή ~2 + i~ ~(0 \le i \le Q - 1 )~: τα φύλλα ~K~ που επιλέγει ο θεατής για την εκτέλεση i του κόλπου σε αύξουσα σειρά.

Για κάθε εκτέλεση με την ίδια σειρά με την είσοδο, το δείγμα βαθμολογητή εκτυπώνει Accepted: selected_cards = <chosen_cards>; discarded_card = <discarded_card> εάν το κόλπο εκτελείται σωστά, όπου <chosen_cards> είναι τα φύλλα που επιστράφηκαν από τη choose_cards και <discarded_card> είναι το φύλλο που επιστράφηκε από τη find_discarded_card.

Για κάθε παιχνίδι, ο βαθμολογητής του δείγματος εκτυπώνει Wrong Answer: <MSG> εάν το κόλπο αποτύχει να εκτελεστεί σωστά, όπου το <MSG> είναι ένα από τα ακόλουθα:

• invalid number of chose cards: ο αριθμός των φύλλων που επιστράφηκαν από chosen_cards είναι λανθασμένος.
• invalid chosen card number: κάποιος από τους αριθμούς φύλλων που επιστράφηκε από chosen_cards είναι μη έγκυρος.
• duplicated chosen cards: υπάρχουν δύο φύλλα που επιστράφηκαν από chosen_cards με το τον ίδιο αριθμό.
• wrong discarded card: το φύλλο που επιστράφηκε από την find_discarded_card δεν είναι σωστό.