EGOI-22 (2022) - Γύρος #2 - 4 (Cheat)

View as PDF

Submit solution

All submissions

Best submissions

Points: 90 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

EGOI

Problem type

Allowed languages

C, C++, Java, Pascal, Python

Chika Wants to Cheat

Η Chika έχει μια τράπουλα με $q$ ~q~ κάρτες αριθμημένες με διάφορους θετικούς ακεραίους. Θέλει να παίξει κάποιες κάρτες με τους φίλους της από το συμβούλιο μαθητών της Ακαδημίας Shuchi'in χρησιμοποιώντας αυτές τις κάρτες, αλλά επίσης θέλει και να κερδίσει, οπότε αποφασίζει να σημαδέψει το πίσω μέρος των καρτών στην τράπουλά της.

Οι κάρτες έχουν όλες τετράγωνο σχήμα με διάσταση $2 \times 2$ ~2 \times 2~, όπου η κάτω αριστερή γωνία τους έχει συντεταγμένες $(0, 0)$ ~(0, 0)~ και η επάνω δεξιά $(2, 2)$ ~(2, 2)~. Η Chika σημαδεύει με ένα συγκεκριμένο μοτίβο την οπίσθια όψη (πλάτη) κάθε κάρτας, έτσι ώστε αργότερα να ξέρει, κοιτώντας το μοτίβο, ποιον αριθμό περιέχει στην εμπρόσθια όψη της. Ζωγραφίζει μοτίβα σύμφωνα με την ακόλουθη διαδικασία: Όσες φορές θέλει (πιθανόν $0$ ~0~ φορές), επιλέγει δυο μοναδικά σημεία $A$ ~A~ και $B$ ~B~ που έχουν ακέραιες συντεταγμένες σε σχέση με την κάτω αριστερή γωνία της κάρτας και σχεδιάζει το ευθύγραμμο τμήμα ανάμεσα στα δυο σημεία.

Η Chika θα σχεδιάσει μόνο έγκυρα ευθύγραμμα τμήματα, δηλαδή, τμήματα μεταξύ των σημείων $A$ ~A~ και $B$ ~B~ για τα οποία δεν υπάρχει κάποιο άλλο σημείο $C$ ~C~ (διαφορετικό από τα $A$ ~A~ και $B$ ~B~) με ακέραιες συντεταγμένες που να περιέχεται στο ίδιο ευθύγραμμο τμήμα. Για παράδειγμα, το τμήμα ανάμεσα στα $(0, 0)$ ~(0, 0)~ και $(2, 2)$ ~(2, 2)~ είναι άκυρο καθώς περιέχει το σημείο $(1, 1)$ ~(1, 1)~, ενώ τα ευθύγραμμα τμήματα μεταξύ των $(0, 0)$ ~(0, 0)~ και $(1, 1)$ ~(1, 1)~ και μεταξύ των $(1, 1)$ ~(1, 1)~ και $(2, 2)$ ~(2, 2)~ είναι και τα δυο έγκυρα και η Chika μπορεί ακόμα και να ζωγραφίσει και τα δύο αυτά τμήματα στο ίδιο μοτίβο. Επίσης, λάβετε υπόψη ότι τα ευθύγραμμα τμήματα δεν έχουν φορά: Ένα ευθύγραμμο τμήμα σχεδιασμένο από το $A$ ~A~ στο $B$ ~B~ είναι ταυτόσημο με το ευθύγραμμο τμήμα ανάποδης φοράς, δηλαδή από το $B$ ~B~ στο $A$ ~A~.

Είναι επίσης σημαντικό η Chika να μπορεί να αναγνωρίζει τις κάρτες της τράπουλας άσχετα με το πως αυτές έχουν περιστραφεί. Μια κάρτα μπορεί να περιστραφεί $0$ ~0~, $90$ ~90~, $180$ ~180~ ή $270$ ~270~ μοίρες αντίστροφα από τους δείκτες του ρολογιού σε σχέση με τον αρχικό της προσανατολισμό. Η δουλειά σας είναι να βοηθήσετε την Chika να σχεδιάσει μοτίβα για τις $q$ ~q~ κάρτες στην τράπουλα της και μετά να τις αναγνωρίσει.

Υλοποίηση

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

Μια συνάρτηση με όνομα BuildPattern που επιστρέφει το μοτίβο που πρέπει να σχεδιαστεί στην πίσω όψη μιας συγκεκριμένης κάρτας. Η συνάρτηση αυτή θα κληθεί $q$ ~q~ φορές κατά το πρώτο στάδιο της αποστολής.
Μια συνάρτηση GetCardNumber που επιστρέφει τον αριθμό μιας (πιθανόν περιστραμμένης) κάρτας που έχει σχεδιασμένο ένα συγκεκριμένο μοτίβο σχεδιασμένο κατά το πρώτο στάδιο. Η συνάρτηση αυτή θα κληθεί $q$ ~q~ φορές κατά το δεύτερο στάδιο της αποστολής.

Η πρώτη συνάρτηση

std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> BuildPattern(int n);

παίρνει μια μοναδική παράμετρο, τον ακέραιο $n$ ~n~, ο οποίος απεικονίζεται στην εμπρόσθια όψη της. Πρέπει να επιστρέψετε ένα std::vector που να περιέχει τα ευθύγραμμα τμήματα που η Chika θα σχεδιάσει για το μοτίβο στην οπίσθια όψη της κάρτας ώστε να την αναγνωρίζει αργότερα. Ένα ευθύγραμμο τμήμα αναπαρίσταται από ένα std::pair σημείων και ένα σημείο αναπαρίσταται από ένα std::pair $(x, y)$ ~(x, y)~ ακέραιων συντεταγμένων ορισμένων σε σχέση με την κάτω αριστερή γωνία της κάρτας, όπου $0 \le x, y \le 2$ ~0 \le x, y \le 2~. Όλα τα ευθύγραμμα τμήματα που η Chika θα σχεδιάσει πρέπει να είναι έγκυρα και να μην είναι ταυτόσημα με άλλα ευθύγραμμα τμήματα του μοτίβου. Είναι εγγυημένο ότι όλες οι $q$ ~q~ κλησεις στη BuildPattern λαμβάνουν διαφορετικές τιμές για την παράμετρο $n$ ~n~.

Αφού λάβει όλα τα μοτίβα για τις $q$ ~q~ κάρτες, ο βαθμολογητής (grader) μπορεί να κάνει οποιοδήποτε από τις παρακάτω ενέργειες, όσες φορές θέλει, σε κάθε ένα από τα μοτίβα:

Να περιστρέψει ολόκληρο το μοτίβο κατά $0$ ~0~, $90$ ~90~, $180$ ~180~ ή $270$ ~270~ μοίρες αντίστροφα από τη φορά των δεικτών του ρολογιού.
Να αλλάξει τη σειρά των ευθύγραμμων τμημάτων στην αναπαράσταση std::vector του μοτίβου.
Να αλλάξει τη σειρά των σημείων ενός ευθύγραμμου τμήματος στο μοτίβο. (Δηλαδή το ευθύγραμμο τμήμα από το $A$ ~A~ στο $B$ ~B~, να γίνει το ταυτόσημό του, από το $B$ ~B~ στο $A$ ~A~).

Η δεύτερη συνάρτηση,

int GetCardNumber(std::vector<std::pair<std::pair<int, int>, std::pair<int, int>>> p);

λαμβάνει μια μοναδική παράμετρο $p$ ~p~, τύπου std::vector από ευθύγραμμα τμήματα που περιγράφουν το μοτίβο που σχεδίασε η Chika στην οπίσθια όψη της κάρτας, βασισμένη στην απάντηση σας από προηγούμενη κλήση της συνάρτησης BuildPattern. Η συνάρτηση πρέπει να επιστρέψει τον αριθμό $n$ ~n~ της εμπρόσθιας όψης της κάρτας. Προσέξτε ότι το μοτίβο $p$ ~p~ δεν είναι απαραίτητα στην ίδια διάταξη που το επέστρεψε η BuildPattern;, αλλά μπορεί να έχουν εφαρμοστεί σε αυτό οι τρείς ενέργειες που περιγράφτηκαν προηγουμένως. Είναι επίσης πιθανό η σειρά των καρτών να είναι διαφορετική από τη σειρά που δόθηκαν στο πρώτο στάδιο.

Περιορισμοί

$1 \le q \le 10\,000$ ~1 \le q \le 10\,000~
$1 \le n \le 67\,000\,000$ ~1 \le n \le 67\,000\,000~ για όλες τις κλήσεις στη συνάρτηση BuildPattern
Λάβετε υπόψη ότι υπάρχουν αλγόριθμοι να δημιουργήσουν μοτίβα τέτοια ώστε κάποιος να αναγνωρίζει $67\,000\,000$ ~67\,000\,000~ διαφορετικές κάρτες

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
$1$ ~1~	$2$ ~2~	$n \le 2$ ~n \le 2~
$2$ ~2~	$9$ ~9~	$n \le 25$ ~n \le 25~
$3$ ~3~	$15$ ~15~	$n \le 1\,000$ ~n \le 1\,000~ και ο βαθμολογητής δεν θα περιστρέψει τα μοτίβα ανάμεσα στο στάδιο $1$ ~1~ και $2$ ~2~. (Ο βαθμολογητής μπορεί να εκτελέσει τις υπόλοιπες δύο ενέργειες).
$4$ ~4~	$3$ ~3~	$n \le 16\,000\,000$ ~n \le 16\,000\,000~ και ο βαθμολογητής δεν θα περιστρέψει τα μοτίβα ανάμεσα στο στάδιο $1$ ~1~ και $2$ ~2~. (Ο βαθμολογητής μπορεί να εκτελέσει τις υπόλοιπες δύο ενέργειες).
$5$ ~5~	$24$ ~24~	$n \le 16\,000\,000$ ~n \le 16\,000\,000~
$6$ ~6~	$18$ ~18~	$n \le 40\,000\,000$ ~n \le 40\,000\,000~
$7$ ~7~	$29$ ~29~	Κανένας επιπλέον περιορισμός.

Διαδραστικό παράδειγμα

Κλήση συνάρτησης	Επιστρεφόμενη τιμή	Επεξήγηση
Πρώτο στάδιο	-	-
BuildPattern(3)	{{{0, 0}, {2, 1}}, {{1, 1}, {2, 0}}}	Έχουμε να σχεδιάσουμε ένα μοτίβο για τον αριθμό $3$ ~3~ στην κάρτα διάστασης $2 \times 2$ ~2 \times 2~. Αποφασίζουμε να σχεδιάσουμε 2 ευθύγραμμα τμήματα: - μεταξύ $(0, 0)$ ~(0, 0)~ και $(2, 1)$ ~(2, 1)~, - μεταξύ $(1, 1)$ ~(1, 1)~ και $(2, 0)$ ~(2, 0)~.
BuildPattern(1)	{{{0, 1}, {0, 0}}}	Έχουμε να σχεδιάσουμε ένα μοτίβο για τον αριθμό $1$ ~1~ στην κάρτα διάστασης $2 \times 2$ ~2 \times 2~: - μεταξύ $(0, 1)$ ~(0, 1)~ και $(0, 0)$ ~(0, 0)~.
Τέλος πρώτου σταδίου	-	-
Αρχή δεύτερου σταδίου	-	-
GetCardNumber({{{0, 0}, {0, 1}}})	$1$ ~1~	Λαμβάνουμε ένα μοτίβο αποτελούμενο από $1$ ~1~ ευθύγραμμο τμήμα: - μεταξύ $(0, 0)$ ~(0, 0)~ και $(0, 1)$ ~(0, 1)~ Αυτό είναι το ίδιο μοτίβο με το να σχεδιάζαμε το ευθύγραμμο τμήμα: - μεταξύ $(0, 1)$ ~(0, 1)~ και $(0, 0)$ ~(0, 0)~ το οποίο είναι ταυτόσημο με το μοτίβο με τον ίδιο προσανατολισμό (περιστραμμένο κατά $0$ ~0~ μοίρες) που δημιουργήσαμε και επιστρέψαμε κατά τη δεύτερη κλήση στη συνάρτηση BuildPattern. Επομένως, επιστρέφουμε $1$ ~1~.
GetCardNumber({{{1, 1}, {2, 2}}, {{1, 2}, {2, 0}}})	$3$ ~3~	Λαμβάνουμε ένα μοτίβο αποτελούμενο από $2$ ~2~ ευθύγραμμα τμήματα: - μεταξύ $(1, 1)$ ~(1, 1)~ και $(2, 2)$ ~(2, 2)~, - μεταξύ $(1, 2)$ ~(1, 2)~ και $(2, 0)$ ~(2, 0)~ Αυτό είναι το μοτίβο που δημιουργήσαμε και επιστρέψαμε στην πρώτη κλήση στη συνάρτηση BuildPattern, περιστραμμένο κατά $90$ ~90~ μοίρες αντίστροφα από τους δείκτες του ρολογιού. Επομένως, επιστρέφουμε $3$ ~3~.
Τέλος δεύτερου σταδίου	-	-

Οι επόμενες τρεις φωτογραφίες αναπαριστούν με τη σειρά:

Το μοτίβο που επιστραφηκε από την πρώτη κλήση στη BuildPattern:

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

Το μοτίβο που επιστράφηκε από τη BuildPattern κατά τη δεύτερη κλήση της, το οποίο είναι ίδιο με το μοτίβο που λήφθηκε σαν παράμετρος στην πρώτη κλήση της GetCardNumber.

Παράδειγμα Βαθμολογητή

Το παράδειγμα βαθμολογητή που παρέχεται, grader.cpp, στο επισυναπτόμενο Cheat.zip, διαβάζει έναν ακέραιο $q$ ~q~ από την τυπική είσοδο και θα εκτελέσει τα επόμενα βήματα $q$ ~q~ φορές:

Διαβάσε ακέραιο αριθμό $n$ ~n~ από την τυπική είσοδο.
Κάλεσε τη BuildPattern(n) και αποθήκευσε την επιστρεφόμενη τιμή στην μεταβλητή $p$ ~p~.
Κάλεσε τη GetCardNumber(p) και τύπωσε την επιστρεφόμενη τιμή στην τυπική έξοδο.

Μπορείτε να τροποποιήσετε τον βαθμολογητή τοπικά (στον υπολογιστή σας) αν το επιθυμείτε.

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

g++ -std=gnu++11 -O2 -o solution grader.cpp solution.cpp

όπου solution.cpp είναι το αρχείο με το πρόγραμμα σας που θα υποβάλετε στο CMS. Για να τρέξετε το πρόγραμμα σας με το παράδειγμα βαθμολογητή που παρέχεται σαν επισύναψη, γράψτε την παρακάτω εντολή στη γραμμή εντολών του τερματικού:

./solution < input.txt

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

Comments

There are no comments at the moment.