38ος ΠΔΠ Γ' Φάση
Ψωνίζοντας με τον Τάκη (shopping)
[ Μονάδες]
Ο Τάκης ψωνίζει στο αγαπημένο του μαγαζί ως εξής:
- Ψάχνει να βρει το ακριβότερο προϊόν το οποίο κοστίζει το πολύ όσο τα χρήματα που έχει εκείνη τη στιγμή.
- Αν δεν υπάρχει τέτοιο προϊόν, σταματάει τα ψώνια του.
- Αν υπάρχει τέτοιο προϊόν, το αγοράζει μία φορά, πληρώνοντας τα απαιτούμενα χρήματα, και ξαναρχίζει από την αρχή.
Κάθε προϊόν υπάρχει σε άπειρη ποσότητα, οπότε είναι πιθανό ο Τάκης να αγοράσει τελικά το ίδιο προϊόν πολλές φορές.
Το πρόβλημα αποτελείται από δύο μέρη. Κάθε υποπρόβλημα σχετίζεται με ένα από τα δύο μέρη. Δε χρειάζεται να ολοκληρώσετε το πρώτο μέρος για να προσπαθήσετε το δεύτερο.
1ο Μέρος (70 βαθμοί)
Ο Τάκης γνωρίζει τις τιμές των \(N\) προϊόντων που υπάρχουν στο μαγαζί: \(V_1, \ldots , V_N\). Οι τιμές είναι ακέραιες και διακριτές, δηλαδή διαφορετικές μεταξύ τους.
Ο Τάκης θέλει να ξέρει πόσα χρήματα θα του περισσέψουν μετά τις αγορές του, αλλά δεν είναι ακόμα σίγουρος για το πόσα θα πάρει μαζί του εξαρχής. Έτσι, έχει συγκεντρώσει \(Q\) ερωτήματα \(X_1, X_2, \ldots , X_Q\). Για κάθε ερώτημα, θέλει να μάθει πόσα χρήματα θα του έχουν μείνει όταν σταματήσει τα ψώνια του, αν ξεκινήσει με \(X_i\) ευρώ και ψωνίζει με τον παραπάνω τρόπο.
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς \(N\), \(Q\): το πλήθος προϊόντων στο μαγαζί και το πλήθος των ερωτημάτων του Τάκη. Η δεύτερη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(V_1, V_2, \ldots , V_N\): τις τιμές των προϊόντων. Η τρίτη γραμμή περιέχει \(Q\) ακέραιους αριθμούς \(X_1, X_2, \ldots , X_Q\): τα ερωτήματα του Τάκη.
Δεδομένα εξόδου (stdout)
Πρέπει να αποτελείται από \(Q\) γραμμές, καθεμία από τις οποίες να περιέχει έναν ακέραιο αριθμό: την απάντηση στο αντίστοιχο ερώτημα.
Παράδειγμα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 3 1 8 2 6 13 |
1 |
Εξήγηση παραδείγματος: Ο Τάκης ξεκινά με \(13\) ευρώ. Αρχικά, το ακριβότερο προϊόν που μπορεί να αγοράσει κοστίζει \(8\), το αγοράζει και του μένουν \(5\). Μετά, αγοράζει το προϊόν που κοστίζει \(2\) και του μένουν \(3\). Τέλος, αγοράζει ξανά το προϊόν που κοστίζει \(2\) και του μένει μόνο \(1\) ευρώ. Πλέον, δεν υπάρχει κανένα προϊόν που να μπορεί να αγοράσει. Άρα, τελειώνει τα ψώνια του έχοντας \(1\) ευρώ.
Περιορισμοί
- \(1 \leq N \leq 500.000\).
- \(1 \leq Q \leq 200.000\).
- \(1 \leq V_i \leq 10^{18}\).
- Οι τιμές των προϊόντων είναι διακριτές.
- \(1 \leq X_i \leq 10^{18}\).
Υποπροβλήματα
- (19 βαθμοί) \(N \leq 500\), \(Q \leq 500\), \(X_i \leq 500\), για κάθε \(i\) (\(1 \leq i \leq Q\))
- (21 βαθμοί) \(N = 1\).
- (30 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
2ο Μέρος (30 βαθμοί)
Το αγαπημένο μαγαζί του Τάκη οργανώνει μία κλήρωση. Με κάθε επίσκεψή του στο μαγαζί, ο πελάτης κερδίζει τόσους κλήρους όσους και το πλήθος των διαφορετικών προϊόντων που αγόρασε.
Ο μαγαζάτορας θέλει να μεγιστοποιήσει τις πιθανότητες του αγαπημένου του πελάτη, δηλαδή του Τάκη, να κερδίσει την κλήρωση. Γνωρίζει τον τρόπο που ψωνίζει αλλά δεν είναι σίγουρος με πόσα χρήματα θα έρθει στο μαγαζί του. Στο τετράδιο του έχει σημειώσει \(T\) ποσά \(X_1, X_2, ..., X_T\) με τα οποία μπορεί να έρθει ο Τάκης στο μαγαζί και θέλει για καθένα από αυτά, ανεξάρτητα, να ετοιμάσει μία λίστα προϊόντων που να οδηγεί τον Τάκη στο να κερδίσει το μέγιστο δυνατό πλήθος κλήρων.
Κάθε λίστα πρέπει να περιέχει το πολύ 1.000 προϊόντα και οι τιμές τους να είναι θετικές, ακέραιες, διακριτές και το πολύ ίσες με \(10^{18}\).
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(T\): το πλήθος των ποσών που θέλει να εξετάσει ο μαγαζάτορας. Η δεύτερη γραμμή περιέχει \(T\) ακέραιους αριθμούς \(X_1, X_2, \ldots, X_T\): τα ποσά που θέλει να εξετάσει ο μαγαζάτορας.
Δεδομένα εξόδου (stdout)
Πρέπει να αποτελείται από \(2T\) γραμμές. Σε κάθε ποσό \(X_i\) πρέπει να αντιστοιχούν δύο γραμμές: η πρώτη γραμμή πρέπει να περιέχει έναν ακέραιο αριθμό, το πλήθος \(N\) των προϊόντων, και η δεύτερη γραμμή πρέπει να περιέχει \(N\) ακέραιους αριθμούς, τις τιμές των προϊόντων (σε ευρώ). Οι τιμές πρέπει να ικανοποιούν τους περιορισμούς της εκφώνησης. Αν υπάρχουν πολλές έγκυρες λίστες προϊόντων, που να επιτυγχάνουν το ζητούμενο, μπορείτε να τυπώσετε οποιαδήποτε.
Παράδειγμα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 1 11 |
4 1 16 8 2 |
Εξήγηση παραδείγματος: Αποδεικνύεται ότι αν ο Τάκης ξεκινήσει με \(11\) ευρώ, μπορεί να αγοράσει το πολύ \(3\) διαφορετικά προϊόντα. Αν υπάρχουν τέσσερα διαθέσιμα προϊόντα με τιμές αντίστοιχα \(1\), \(16\), \(8\), και \(2\), ο Τάκης θα αγοράσει ακριβώς \(3\) διαφορετικά προϊόντα: το πρώτο, το τρίτο και το τέταρτο.
Περιορισμοί
- \(1 \leq T \leq 1.000\).
- \(1 \leq X_i \leq 10^{18}\).
Υποπροβλήματα:
- (9 βαθμοί) \(X_i \leq 1.000\), για κάθε \(i\) (\(1 \leq i \leq T\)).
- (21 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.