Task
Vasya has one package of mobile phone operator Ratsviyk and $S_0$ tugriks on its account. (Tugrik is the currency in Vasya’s country. $0.01$ of tugrik is a cent). Also he has $n$ packages of Eciujd which is the satellite of Ratsviyk. There are $S_i$ tugriks on the account of the $i$-th package of Eciujd. There was a new tariff plan on Ratsviyk and Vasya want to go into it. For this purpose it is necessary to have at least $S$ tugriks on the account. Vasya hasn’t any money, that is why he don’t want to buy new bill replenishment, to fill up the Ratsviyk account to the necessary sum. But the escape exists.
On Ratsviyk there is such possibility as to transfer money between each others. The transfer is the sending of some money from one account to another. It is possible to send only an integer amounts of tugriks, not smaller than $5$. The cost of the transfer is $10$ cents which is draw from the account from which money was sended. Transfer can be made only if after it on the account remains at least $5$ tugriks. Since Eciujd is the satellite of Ratsviyk, then subscribers of Eciujd also can participate in this transfers.
Giving $S_0, S, n, S_i (1 \leq i \leq n)$ find whether it is possible to go into new tariff plan without buying new bill replenishment and if so find the minimum number of transfers needed for this.
Input
In the first line of input there is an integer $n (0 \leq n \leq 1000), S_0$ and $S$. In the second line are written down through a blank numbers $S_1, S_2,$…$,S_n$. All numbers $S, S_i (0 \leq i \leq n)$ — real numbers from the interval $[0.01, 10000.00]$ with exactly with two digits after a decimal point.
Output
Output the minimum number of transfers needed to go into new tariff plan or $-1$ if it is impossible without buying a new bill replenishment.
Tests
| Input | Output |
| [latex]2\, 10.00\, 16.00[/latex] | [latex]2[/latex] |
| [latex]10.10\, 6.10[/latex] | |
| [latex]3\, 100.00\, 50.00[/latex] | [latex]0[/latex] |
| [latex]2.00\, 19.05\ 30.20[/latex] | |
| [latex]3\ 10.00\ 14.00[/latex] | [latex]-1[/latex] |
| [latex]2.00\ 10.05\ 10.00[/latex] | |
| [latex]2\ 142.10\ 143.00[/latex] | [latex]2[/latex] |
| [latex]6.05\ 7.00[/latex] |
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; double s0, s; double A[n], B[n]; cin >> s0 >> s; if(s0>=s) cout << 0; else { for(int i=0; i<n; i++) { cin >> A[i]; B[i]=A[i]; } sort(B, B+n); int ans=0; for(int i=n-1; i>=1; i--) { if(B[i]>=10.1) { if((int)(B[i]-5.1)+s0>=s){ ans++; cout << ans; return 0; } else { ans++; B[i-1]+=(int)(B[i]-5.1); } } else { break; } } if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s)) cout << ans+1; else { sort(A, A+n); if(s0>=10.1) { A[n-1]+=(int)(s0-5.1); s0-=(int)(s0-5.1); s0-=0.1; ans=1; for(int i=n-1; i>=1; i--) { if(A[i]>=10.1) { if((int)(A[i]-5.1)+s0>=s){ ans++; cout << ans; return 0; } else { ans++; A[i-1]+=(int)(A[i]-5.1); } } else { break; } } if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s)) cout << ans+1; else cout << -1; } else cout << -1; } } return 0; } |
Solution
To begin with, if we have enough money in our account, then we do not need to do anything. Otherwise, we have three options: when we can collect the required amount without manipulating the main account, when we can collect the necessary amount by manipulating the main account and when we can not collect the required amount at all.
For the first option, we will transfer the largest possible amount to smaller ones from large side accounts and check whether we can switch to a new tariff by transferring the current account amount to the main account. In cases of a positive answer, the problem is solved.
If in the end you did not manage to get the right amount, go to the second option. We simply transfer the maximum possible amount from the main account to the largest collateral account. Then we do everything the same as in the first version. In cases of a positive answer, the problem is solved.
Otherwise, you can not get the right amount.
References
The task at E-Olymp
My solution at ideone