34ος ΠΔΠ B' Φάση Γυμνασίου
Ο ξενοδόχος τρελλάθηκε (crazyhotel)
Το ξενοδοχείο του νησιού δεν πηγαίνει πολύ καλά από πλευράς πελατείας. Λίγο η πανδημία, λίγο η γενικότερη κακή οικονομική κατάσταση, ο ιδιοκτήτης του αποφάσισε ότι πρέπει να αλλάξει κάτι για να φέρει περισσότερους πελάτες. Κάποιος φίλος του πρότεινε να μην έχει σταθερές τιμές, αλλά να αυξομειώνει την τιμή του δωματίου μέρα με τη μέρα, ανάλογα με τη ζήτηση. Με τη βοήθεια λοιπόν του λογιστηρίου που κρατάει αρχείο της ζήτησης για τα προηγούμενα χρόνια, της μετεωρολογικής υπηρεσίας και του φίλου του που εκτιμά τη μελλοντική εξέλιξη της ζήτησης, ο ιδιοκτήτης κατέληξε στις τιμές που θα προσφέρει τα δωμάτιά του κάθε μέρα. Μάλιστα, κάποιες μέρες αποφάσισε να προσφέρει τα δωμάτια δωρεάν για να προσελκύσει ακόμα περισσότερους πελάτες.
Ο Θανασάκης θέλει φέτος να κάνει διακοπές και πάντα ήθελε να επισκεφτεί το νησί. Όταν πληροφορήθηκε για τις τιμές των δωματίων του ξενοδοχείου, το πήρε απόφαση. Όμως, ούτε τα δικά του οικονομικά είναι πολύ καλά τώρα τελευταία. Μπορεί να ξοδέψει συνολικά το πολύ \(S\) ευρώ και, για λόγους αρχής, καμία μέρα δεν είναι διατεθειμένος να πληρώσει περισσότερα από \(T\) ευρώ.
Με αυτούς τους περιορισμούς, βοηθήστε το Θανασάκη να μετρήσει όλα τα δυνατά χρονικά διαστήματα που μπορεί να μείνει στο ξενοδοχείο.
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις τιμές των δωματίων του ξενοδοχείου για ένα διάστημα \(N\) ημερών καθώς και τα όρια \(S\) και \(T\) που έχει βάλει ο Θανασάκης, και θα εκτυπώνει το πλήθος των διαφορετικών δυνατών χρονικών διαστημάτων που ικανοποιούν τους παραπάνω περιορισμούς.
Αρχεία εισόδου:
Τα αρχεία εισόδου με όνομα crazyhotel.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχουν τρεις ακέραιοι αριθμοί χωρισμένοι ανά δύο με ένα κενό διάστημα: το πλήθος \(N\) των ημερών για τις οποίες το ξενοδοχείο είναι διαθέσιμο, το συνολικό ποσό \(S\) που μπορεί να διαθέσει ο Θανασάκης, και το μέγιστο ποσό \(T\) που είναι διατεθειμένος να πληρώσει την ημέρα. Στη δεύτερη γραμμή υπάρχουν \(N\) ακέραιοι αριθμοί, χωρισμένοι ανά δύο με ένα κενό διάστημα: οι τιμές \(A_1, A_2, ... A_N\) των δωματίων του ξενοδοχείου κάθε μέρα.
Αρχεία εξόδου:
Τα αρχεία εξόδου με όνομα crazyhotel.out είναι αρχεία κειμένου με την εξής δομή. Περιέχουν ακριβώς μία γραμμή η οποία περιέχει έναν ακέραιο αριθμό: το πλήθος των διαφορετικών χρονικών διαστημάτων που μπορεί ο Θανασάκης να μείνει στο ξενοδοχείο.
Περιορισμοί:
- \(1 \leq N \leq 1.000.000\),
- \(0 \leq A_i \leq 1.000\),
- \(0 \leq S \leq 1.000.000.000\),
- \(0 \leq T \leq 1.000\).
Η σωστή απάντηση δε θα υπερβαίνει το \(2.000.000.000\)
Παραδείγματα αρχείων εισόδου-εξόδου:
1o
| crazyhotel.in | crazyhotel.out |
|---|---|
| 6 10 7 4 3 6 0 8 2 |
9 |
2o
| crazyhotel.in | crazyhotel.out |
|---|---|
| 9 17 7 7 5 6 8 3 6 7 8 4 |
12 |
Εξήγηση του 1ου παραδείγματος:
Το πλήθος των ημερών είναι \(N = 6\). Υπάρχουν εννιά διαφορετικά χρονικά διαστήματα με συνολικό κόστος που να μην υπερβαίνει το \(S = 10\) και μέγιστη τιμή ημέρας που να μην υπερβαίνει το \(T = 7\). Πέντε από αυτά τα χρονικά διαστήματα διαρκούν μόνο μία μέρα: \(4, 3, 6, 0\) και \(2\). Προσέξτε ότι η μέρα που η τιμή είναι \(8 > T\) έχει αποκλειστεί. Υπάρχουν ακόμα τρία διαστήματα που διαρκούν δύο μέρες: \(4+3, 3+6\), \(6+0\), καθώς και ένα διάστημα που διαρκεί τρεις μέρες: \(3+6+0\).
Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.