Μανιτάρια (mushrooms)

Ο Ανδρέας είναι ειδικός στα μανιτάρια. Έχει συλλέξει ~n~ μανιτάρια, αριθμημένα από ~0~ μέχρι και ~n - 1~. Κάθε μανιτάρι ανήκει σε ένα από δύο διαφορετικά είδη, που ονομάζονται ~A~ και ~B~.

Ο Ανδρέας γνωρίζει ότι το μανιτάρι ~0~ ανήκει στο είδος A, δυστυχώς όμως τα δύο είδη μοιάζουν και δε γνωρίζει σε ποιο είδος ανήκουν τα υπόλοιπα μανιτάρια, από το ~1~ μέχρι και το ~n - 1~.

Ευτυχώς, ο Ανδρέας έχει μία μηχανή που μπορεί να τον βοηθήσει. Για να τη χρησιμοποιήσει, μπορεί να τοποθετήσει δύο ή περισσότερα μανιτάρια το ένα δίπλα στο άλλο μέσα στη μηχανή (σε οποιαδήποτε σειρά) και να θέσει τη μηχανή σε λειτουργία. Τότε, η μηχανή υπολογίζει το πλήθος των γειτονικών ζευγών μανιταριών που ανήκουν σε διαφορετικά είδη. Για παράδειγμα, αν βάλει μέσα στη μηχανή τα μανιτάρια που ανήκουν στα είδη ~[A, B. B, A]~ με αυτή τη σειρά), το αποτέλεσμα θα είναι ~2~.

Όμως, η χρήση αυτής της μηχανής είναι πολύ ακριβή και ο Ανδρέας μπορεί να τη χρησιμοποιήσει μόνο περιορισμένο αριθμό φορών. Επιπλέον, το συνολικό πλήθος των μανιταριών που μπορεί να τοποθετήσει στη μηχανή όλες τις φορές που θα τη χρησιμοποιήσει δεν μπορεί να υπερβαίνει το ~100\,000~. Βοηθήστε τον Ανδρέα να χρησιμοποιήσει τη μηχανή για να μετρήσει πόσα μανιτάρια από το είδος ~A~ έχει συλλέξει.

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

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

int count_mushrooms(int n)

• ~n~: το πλήθος των μανιταριών που έχει συλλέξει ο Ανδρέας.
• Η συνάρτηση αυτή καλείται ακριβώς μία φορά και πρέπει να επιστρέφει το πλήθος των μανιταριών που ανήκουν στο είδος \(Α\).

Η παραπάνω συνάρτηση μπορεί να καλεί την παρακάτω συνάρτηση:

int use_machine(int[] x)

• ~x~: ένας πίνακας μήκους μεταξύ ~2~ και ~n~ (συμπεριλαμβανομένων), που περιέχει τους αριθμούς των μανιταριών που τοποθετούνται στη μηχανή, κατά σειρά.
• Τα στοιχεία του ~x~ πρέπει να είναι διακριτοί ακέραιοι αριθμοί μεταξύ ~0~ και ~n - 1~ (συμπεριλαμβανομένων).
• Έστω ~d~ το μήκος του πίνακα ~x~. Τότε, η συνάρτηση επιστρέφει το πλήθος των διαφορετικών δεικτών ~j~, τέτοιων ώστε ~0 \le j \le d - 2~ και τα μανιτάρια ~x[j]~ και ~x[j + 1]~ ανήκουν σε διαφορετικά είδη.
• Η συνάρτηση αυτή μπορεί να κληθεί το πολύ ~20\,000~ φορές.
• Το άθροισμα των μηκών των πινάκων ~x~ που δίνονται ως παράμετροι στη συνάρτηση use_machine σε όλες τις κλήσεις της δεν μπορεί να υπερβαίνει το ~100\,000~.

Παραδείγματα

Παράδειγμα 1

Έστω ένα σενάριο στο οποίο υπάρχουν ~3~ μανιτάρια από τα είδη ~[A, B, B]~, με αυτή τη σειρά. Η συνάρτηση count_mushrooms καλείται ως εξής:

count_mushrooms(3)

Η συνάρτηση αυτή μπορεί να καλέσει την use_machine([0, 1, 2]), η οποία (σε αυτό το σενάριο) επιστρέφει 1. Στη συνέχεια, μπορεί να καλέσει την use_machine([2, 1]), που επιστρέφει 0.

Στο σημείο αυτό, έχουμε αρκετές πληροφορίες ώστε να συμπεράνουμε πως υπάρχει μόνο ~1~ μανιτάρι από το είδος ~A~. Επομένως, η συνάρτηση count_mushrooms πρέπει να επιστρέψει 1.

Παράδειγμα 2

Έστω ένα άλλο σενάριο στο οποίο υπάρχουν ~4~ μανιτάρια από τα είδη ~[A, B, A, A]~, με αυτή τη σειρά. Η συνάρτηση count_mushrooms καλείται ως εξής:

count_mushrooms(4)

Η συνάρτηση αυτή μπορεί να καλέσει την use_machine([0, 2, 1, 3]), που επιστρέφει 2. Στη συνέχεια, μπορεί να καλέσει την use_machine([1, 2]), που επιστρέφει 1.

Στο σημείο αυτό, έχουμε αρκετές πληροφορίες ώστε να συμπεράνουμε πως υπάρχουν μανιτάρια ~3~ από το είδος \(Α\). Επομένως, η συνάρτηση count_mushrooms πρέπει να επιστρέψει 3.

Περιορισμοί

• ~2 \le n \le 20\,000~

Βαθμολόγηση

Αν σε οποιαδήποτε από τις περιπτώσεις ελέγχου κάποια κλήση της συνάρτησης use_machine δεν υπακούει στους κανόνες που αναφέρονται παραπάνω, ή αν η τιμή επιστροφής της count_mushrooms είναι εσφαλμένη, η λύση σας θα βαθμολογηθεί με ~0~. Διαφορετικά, έστω ~Q~ το μέγιστο πλήθος κλήσεων στη συνάρτηση use_machine μεταξύ όλων των περιπτώσεων ελέγχου. Τότε, η βαθμολογία σας θα υπολογιστεί σύμφωνα με τον ακόλουθο πίνακα:

Συνθήκη	Βαθμολογία
~20\,000 < Q~	~0~
~10\,010 < Q \le 20\,000~	~10~
~904 < Q \le 10\,010~	~25~
~226 < Q \le 904~	~(226 / Q) \cdot 100~
~Q \le 226~	~100~

Σε κάποιες περιπτώσεις ελέγχου, η συμπεριφορά του βαθμολογητή θα είναι προσαρμοστική (adaptive). Αυτό σημαίνει ότι σε αυτές τις περιπτώσεις ελέγχου, ο βαθμολογητής δε θα έχει εξ αρχής μία συγκεκριμένη σειρά ειδών μανιταριών. Αντίθετα, οι απαντήσεις που θα δίνει μπορεί να εξαρτώνται από τις προηγούμενες κλήσεις της use_machine. Όμως, είναι βέβαιο ότι ο βαθμολογητής απαντά με τέτοιο τρόπο ώστε μετά από κάθε απάντηση να υπάρχει τουλάχιστον μία ακολουθία ειδών μανιταριών που να είναι συνεπής με όλες τις απαντήσεις που έχει δώσει μέχρι εκείνη τη στιγμή.

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

Ο υποδειγματικός βαθμολογητής διαβάζει έναν πίνακα ~s~, αποτελούμενο από ακέραιους αριθμούς που παριστάνουν τα είδη των μανιταριών. Για κάθε ~0 \le i \le n - 1~, ~s[i] = 0~ σημαίνει ότι το μανιτάρι ~i~ ανήκει στο είδος ~A~, ενώ ~s[i] = 1~ σημαίνει ότι το μανιτάρι ~i~ ανήκει στο είδος ~B~. Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~
• γραμμή ~2~: ~s[0]~ ~s[1] ... s[n - 1]~

• Η έξοδος του υποδειγματικού βαθμολογητή είναι ως εξής:

• γραμμή ~1~: η τιμή επιστροφής της συνάρτησης count_mushrooms.

• γραμμή ~2~: το πλήθος κλήσεων στη συνάρτηση use_machine.

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