Techgig

Candy Shop

June 25, 2022 by aAshish

Hanna wants to buy N chocolates for her niece on her birthday. She visits a nearby candy shop and finds that there are only two types of candies in the shop, U and V. The pricing is calculated in a special manner though:


  1. If you buy K number of U candies, then you have to pay C1 * K^2 where C1 is a constant value.

  2. If you buy L number of V candies, then you have to pay C2 * L^2 where C2 is a constant value.

Hanna is not good with calculations and needs your help to find the minimum money she has to pay for N chocolates. Can you help her?


Example:

Number of chocolates Hanna wants to buy, N = 4

C1 = 2

C2 = 3


There are multiple possible combinations to buy 4 chocolates. The one with the least amount of money spent is our combination.


|Number of U Candies (K) | Number of V candies (L) | Price to Pay for N candies 
| 0                                            | 4                                            |     2 * 0^2 + 3 * 4^2 = 48 
| 1                                             | 3                                            |     2 2 * 1^2 + 3 * 3^2 = 29
| 2                                            | 2                                            |     2 * 2^2 + 3 * 2^2 = 20
| 3                                            | 1                                             |     2 * 3^2 + 3 * 1^2 = 21
| 4                                            | 0                                            |     2 * 4^2 + 3 * 0^2 = 32


Minimum amount of money Hanna has to pay is 20.


Input Format

  • The first line consists of the number of test cases, T.
  • The only line of each test case consists of three space-separated integers, N (number of chocolates to buy), C1 and C2 respectively.
Constraints

1<= T <=10

1<= N, C1, C2 <=100000


Output Format
For each test case, print the minimum amount Hanna has to pay for N chocolates.
PYTHON
t = int(input())
while t > 0:
    n, c1, c2 = input().split(" ")
    n, c1, c2 = int(n), int(c1), int(c2)
    ans = (c1 * 0 ** 2) + (c2 * n ** 2)
    for x in range(n + 1):
        temp = (c1 * x ** 2) + (c2 * (n - x) ** 2)
        if temp <= ans:
            ans = temp
        else:
            print(ans)
            break
    t -= 1
JAVA
import java.util.Scanner;

public class CandidateCode {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while (t > 0) {
      int[] arr = {sc.nextInt(), sc.nextInt(), sc.nextInt()};

      double ans = (arr[1] * Math.pow(0, 2)) + (arr[2] * Math.pow(arr[0], 2));

      for (int i = 0; i <= arr[0]; i++) {
        double temp = (arr[1] * Math.pow(i, 2)) + (arr[2] * Math.pow((arr[0] - i), 2));
        if (temp <= ans) ans = temp;
        else {
          System.out.println((long) ans);
          break;
        }
      }
      --t;
    }
  }
}