# Ninja and his dessert.

Posted: 8 Apr, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### For making dessert, there are some basic rules

``````1. There should be exactly one base flavor.
2. Toppings can be one or more or none.
3. There are at most two toppings of each type.
``````

#### Example

``````Let N = 2 , M = 2 , K = 10, FLAVOR = [1,7] , TOPPING = [3, 4] , K = 10

Here we can make a dessert with the base flavor of price 7 and adding 1 topping of price 3. Which will cost 7 + 3 = 10, which is exactly equal to k, so the closest possible price would be 10.
``````
##### Input Format
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer ‘N’ representing the number of base FALVOURS.

The second line of each test case contains ‘N’ integer representing the cost base FLAVOURS.

The third line of each test case contains an integer ‘M’ representing the number of TOPPINGS.

The second line of each test case contains ‘M’ integer representing the cost TOPPINGS.

The fifth and last line of each test case contains an integer ‘K’ representing the target price for dessert.
``````
##### Output Format
``````For each test case, print a single line containing a single integer denoting the closest possible price of the dessert to the target price.

The output of each test case will be printed in a separate line.
``````

#### Note:

``````You don’t need to print anything or take input. It already has been taken care of. Just implement the function.
``````
##### Constraints
``````1 <= T <= 5
1 <= N, M <= 10
1 <= FLAVOUR[i] , TOPPINGS[i] <= 10 ^ 4
1 <= K <= 10 ^ 4

Time limit: 1 sec.
`````` Approach 1

There are 3 ways to make a dessert

1. Add one topping to flavor[i]
2. Add two toppings to flavor[i]
3. Don’t add any toppings to flavor[i]

Implement this with recursion since we have 3 choices at each instant.

We will now take a particular base flavor and start adding toppings to it in the above ways.

## Algorithm:

• Function to choose the closest price to target.
• int  closest(int a, int b, int target)
• If a is 0, then return b or vice versa.
• If the absolute value of (a - target) is equal to the absolute value of (b - target), then return smaller of a and b.
• If the absolute value of (a - target) is greater than the absolute value of (b - target), then return b, else return a.
• Function to find the closed value for a specific base flavor.
• int dfs(int[] &topping, int index, int sum,int target)
• If index >= topping size then return sum.
• Initialize a variable ‘a’ to store the first way for a specific base. So a= dfs(topping,i + 1,sum + topping[i]).
• Initialize a variable ‘b’ to store the second way for a specific base. So b = dfs(topping, i + 1, sum+ topping[i] * 2)
• Initialize a variable ‘c’ to store the third way for a specific base. So c = dfs(topping, i + 1, sum);
• Finally, return sum, where sum= closest(a, closest(b,c))
• Function to find the closest price possible
• int  closestCost(int[]flavor, int[]topping, int target)
• Initialize a variable ans=0 to store answer.
• Iterate i from 0 to base size - 1.
1. Update ans as  ans= closest(dfs(topping, 0,  base[i]),ans)
• Return ans.