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 BR 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
50 3
15 50 24.35
50 4
15 16.50 50 22.40

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';
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
50 3
15 50 24.35
50 4
15 16.50 50 22.40

Output

x
+
cmd
5.00
5.20
Advertisements

Demonstration


Previous
#1750 Beecrowd Online Judge Solution 1750 Help Cupid Solution in C, C++, Java, Js and Python
Next
#1758 Beecrowd Online Judge Solution 1758 Bonus Grade Points Solution in C, C++, Java, Js and Python