35ος ΠΔΠ Α' Φάση
Ηλεκτρονικές κάρτες αγορών (coupon)
Λόγω της μεγάλης αύξησης των τιμών, πολλά κράτη εκδίδουν προπληρωμένες ηλεκτρονικές κάρτες για τους πολίτες τους με τις οποίες μπορούν να κάνουν διάφορες αγορές (π.χ. τρόφιμα, καύσιμα κλπ). Με βάση τα οικονομικά δεδομένα καθορίζεται το συνολικό ποσό που μπορεί να διατεθεί. Η διάθεση γίνεται σε οικογένειες με βάση εισοδηματικά κριτήρια, με τον εξής τρόπο:
Οι οικογένειες χωρίζονται σε \(N\) οικονομικές ομάδες με βάση το συνολικό ετήσιο εισόδημά τους. Οι οικογένειες που βρίσκονται στην πρώτη ομάδα έχουν μικρότερο εισόδημα από αυτές που βρίσκονταιστη δεύτερη ομάδα, κ.ο.κ. Σε όλες τις οικογένειες της ίδιας οικονομικής ομάδας θα δοθεί μία προπληρωμένη ηλεκτρονική κάρτα της ίδια αξίας και το Υπουργείο Οικονομικών έχει αποφασίσει ότι αν η αξία των καρτών της 1ης ομάδας είναι ίση με \(X_1\) ευρώ, τότε η αξία των καρτών της 2ης ομάδας θα πρέπει να είναι ίση με \(X_2 = A \cdot X_1\) ευρώ (όπου \(0 < A < 1\) δοθείς αριθμός), η αξία των καρτών της 3ης ομάδας θα πρέπει να είναι ίση με \(X_3 = A \cdot X_2\) ευρώ, κ.ο.κ. Όλες οι αξίες των καρτών σε ευρώ θα πρέπει να είναι ακέραιοι αριθμοί — τα λεπτά του ευρώ που τυχόν προκύπτουν από τις παραπάνω πράξεις θα αποκόπτονται. Επίσης, αν η αξία των καρτών μίας οικονομικής ομάδας προκύπτει να είναι μικρότερη των 10 ευρώ, τότε σε αυτή την οικονομική ομάδα δε θα διατεθεί κανένα βοήθημα.
Για παράδειγμα, έστω ότι \(A = 0.5\) και οι κάρτες της 1ης ομάδας έχουν αξία \(X_1 = 100\) ευρώ. Τότε, οι κάρτες όλων των οικονομικών ομάδων θα πρέπει να έχουν τις παρακάτω αξίες:
- Ομάδα 1 \(X_1 = 100\) ευρώ
- Ομάδα 2 \(X_2 = 50\) ευρώ
- Ομάδα 3 \(X_3 = 25\) ευρώ
- Ομάδα 4 \(X_4 = 12\) ευρώ (αποκόπτονται τα \(50\) λεπτά)
- Ομάδα 5 \(X_5 = 0\) (θα ήταν \(6 < 10\) ευρώ)
- Ομάδα 6 \(X_6 = 0\) (θα ήταν \(3 < 10\) ευρώ)
Το Υπουργείο Οικονομικών έχει ορίσει το μέγιστο συνολικό ποσό \(B\) που μπορεί να διατεθεί ως βοήθημα με αυτόν τον τρόπο. Γνωρίζει επίσης ότι στην 1η οικονομική ομάδα ανήκουν \(C_1\) οικογένειες, στη 2η οικονομική ομάδα ανήκουν \(C_2\) οικογένειες, κ.ο.κ. Ζητά τη βοήθειά σας για να προσδιορίσει τις αξίες των καρτών με τέτοιο τρόπο ώστε η 1η οικονομική ομάδα να πάρει κάρτες όσο το δυνατόν μεγαλύτερης αξίας, χωρίς όμως να ξεπερασθεί το μέγιστο συνολικό ποσό.
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει το πλήθος των ομάδων, τον αριθμό των οικογενειών ανά οικονομική ομάδα, τη σταθερά \(A\) και το μέγιστο συνολικό ποσό που μπορεί να διατεθεί. Το πρόγραμμά σας πρέπει να τυπώνει το συνολικό ποσό που θα διατεθεί και τις αξίες των καρτών κάθε οικονομικής ομάδας.
Αρχεία Εισόδου:
Τα αρχεία εισόδου με όνομα coupon.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχουν τρεις αριθμοί χωρισμένοι ανά δύο με ένα κενό διάστημα: το πλήθος των οικονομικών ομάδων \(N\), η σταθερά \(A\), και μέγιστο συνολικό ποσό \(B\). Οι αριθμοί \(N\) και \(B\) είναι ακέραιοι, ενώ η σταθερά \(A\) δίνεται με τρία το πολύ δεκαδικά ψηφία. Σε κάθε μία από τις επόμενες \(N\) γραμμές υπάρχει ένας ακέραιος αριθμός \(C_i\) (όπου \(1 \leq i \leq N\)): ο αριθμός των οικογενειών που ανήκουν στην \(i\)-οστή οικονομική ομάδα.
Αρχεία Εξόδου:
Τα αρχεία εξόδου με όνομα coupon.out είναι αρχεία κειμένου με την εξής δομή. Η γραμμή πρέπει να περιέχει ακριβώς έναν ακέραιο αριθμό: το συνολικό ποσό που θα διατεθεί σε όλες τις οικογένειες. Κάθε μία από τις επόμενες \(N\) γραμμές πρέπει να περιέχει έναν ακέραιο αριθμό \(X_i\) (όπου \(1 \leq i \leq N\)): την αξία της ηλεκτρονικής κάρτας που θα διατεθεί σε κάθε οικογένεια της \(i\)-οστής οικονομικής ομάδας ή \(0\) αν στην \(i\)-οστή οικονομική ομάδα δε θα διατεθεί βοήθημα.
Περιορισμοί:
- \(1 \leq N \leq 1.000\),
- \(0 \leq A \leq 1\),
- \(1 \leq B \leq 1.000.000.000\),
- \(1 \leq C_i \leq 1.000.000\).
Παραδείγματα Αρχείων Εισόδου - Εξόδου:
1o
| coupon.in | coupon.out |
|---|---|
| 6 0.5 1000000 10000 3000 1000 400 100 10 |
991000 84 42 21 10 0 0 |
Στο πρώτο παράδειγμα, σε κάθε οικογένεια της 1ης οικονομικής ομάδας διατίθεται μία ηλεκτρονική κάρτα των \(84\) ευρώ. Υπάρχουν \(10000\) οικογένειες σε αυτή την ομάδα που παίρνουν συνολικά \(10000 \cdot 84 = 840000\) ευρώ. Στη 2η οικονομική ομάδα θα διατεθούν συνολικά \(3000 \cdot 42 = 126000\) ευρώ, στην 3η οικονομική ομάδα θα διατεθούν συνολικά \(1000 \cdot 21 = 21000\) ευρώ, ενώ στην 4η οικονομική ομάδα θα διατεθούν συνολικά \(400 \cdot 10 = 4000\) ευρώ. Στην 5η και την 6η οικονομική ομάδα δε θα διατεθεί κανένα βοήθημα. Το συνολικό ποσό που θα διατεθεί σε όλες τις οικογένειες είναι:
\[840000 + 126000 + 21000 + 4000 = 991000\]2o
| coupon.in | coupon.out |
|---|---|
| 10 0.8 100000000 10000 25000 120000 40000 15000 6000 1520 800 420 170 |
99921970 736 588 470 376 300 240 192 153 122 97 |
Στο δεύτερο παράδειγμα, ξεκινώντας με \(736\) ευρώ για την 1η οικονομική ομάδα, το συνολικό ποσό επαρκεί για να διατεθεί βοήθημα σε όλες τις οικονομικές ομάδες.
Παρατηρήσεις:
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.