Author: | A. Klenin | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
Well-known Internet company "Dalstolb" created an on-line marketplace, where individuals and companies can sell some products. After purchasing and testing the product, buyer can rate the seller with an integer number from 1 to 10. For each seller, website displays number of ratings N and their average A so that prospective buyers can choose better sellers.
If a company is not satisfied with its rating, it might either improve the quality of their goods and services, or create some fake accounts and give high ratings from those accounts to itself. That practice is called astroturfing.
"Dalstolb" is aware of astroturfing and implemented following limits to make it harder: each buyer may give only one rating to a given seller; all ratings strictly greater than twice the current average are flagged for manual inspection.
Your program must calculate the minimum number of fake accounts required to raise the rating to at least B, while not triggering manual inspection.
Note that all calculations by "Dalstolb" server are assumed to be absolutely exact, with no loss of precision at all.
In the first example, ratings and averages are as follows:
Fake account no. | Fake rating | Average rating |
---|---|---|
1 | 4 | 2.40000 |
2 | 4 | 2.66667 |
3 | 5 | 3.00000 |
4 | 6 | 3.37500 |
5 | 6 | 3.66667 |
6 | 7 | 4.00000 |
Input file contains integers NAB.
Output file must contain a single integer — minimum number of fake accounts.
1≤N≤108, 1≤A<B≤9
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|