Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1755
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1755
The Change
By Victor Marcilio Peixoto, UNIVASF 
Brazil
Timelimit: 2
Jõaozinho's father asked him to shop for a certain ingredient and gave him the following instructions:
1 - You may choose any brand as long as you buy as many units as possible.
2 - Don't come back empty-handed (buy at least one product).
3 - Don't bring me products from different brands.
4 - If you respect the first 3 constraints the change is yours.
Joãozinho is not that good in math and asked you to help him choose the brand that would maximize the change, respecting the constraints. You don't like lazy people and promissed Joãozinho that you would build him a program to solve part of his problem: finding the best change (without mentioning which brand would lead to such change).
Input
The first line of input contains an integer T (1 ≤ T ≤ 2000), the number of test cases.
Each test case has 2 lines. The first line has the integeres D (10 ≤ D ≤ 500) and N ( 2 ≤ N ≤ 300), indicating the amount of money Joãozinho took to the market and the number of different brands available (you may assume that the store has enough stock to supply any demand), respectively.
The second line contains N floating-point numbers pi, representing the cost of one unit manufactured by brand bi. You may assume that the any price will have at most 2 digits after the decimal point.
Output
For each test case print a single line containing a floating-point number with 2 digits after the decimal point: The largest change that Joãozinho can earn.
| Input Sample | Output Sample |
|
2 |
5.00 5.20 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int cases;
int n;
double d, price;
cin >> cases;
while (cases--)
{
cin >> d >> n;
double maior = -1.0;
for (int i = 0 ; i < n ; ++i)
{
cin >> price;
int qtde = 0;
while (price * qtde < = d) ++qtde;
--qtde;
double x = d - qtde * price;
if (x > maior && qtde >= 1)
maior = x;
}
cout << setprecision(2) << fixed << maior << '\n';
}
}
Input
50 3
15 50 24.35
50 4
15 16.50 50 22.40
Output
5.20