All Tracks Algorithms Searching Linear Search Problem

Special Shop
Tag(s):

Algorithms, Easy-Medium, Linear Search, Searching, differentiation

Problem
Editorial
Analytics

Creatnx now wants to decorate his house by flower pots. He plans to buy exactly \(N\) ones. He can only buy them from Triracle's shop. There are only two kind of flower pots available in that shop. The shop is very strange. If you buy \(X\) flower pots of kind 1 then you must pay \(A\times X^2\) and \(B\times Y^2\) if you buy \(Y\) flower pots of kind 2. Please help Creatnx buys exactly \(N\) flower pots that minimizes money he pays.

Input Format

The first line contains a integer \(T\) denoting the number of test cases.

Each of test case is described in a single line containing three space-separated integers \(N, A, B\).

Output Format

For each test case, print a single line containing the answer.

Constraints

  • \(1\le T \le 10^5\)
  • \(1\le N, A, B \le 10^5\)

 

SAMPLE INPUT
2
5 1 2
10 2 4

SAMPLE OUTPUT
17
134
Explanation

Query 1: we have to buy exactly \(5\) pots. There are six possible options:

  • Buy \(0\) pot of first kind, \(5\) pots of second kind. The cost is: \(1\times 0^2 + 2\times 5^2 = 50\).
  • Buy \(1\) pot of first kind, \(4\) pots of second kind. The cost is: \(1\times 1^2 + 2\times 4^2 = 33\).
  • Buy \(2\) pots of first kind, \(3\) pots of second kind. The cost is: \(1\times 2^2 + 2\times 3^2 = 22\).
  • Buy \(3\) pots of first kind, \(2\) pots of second kind. The cost is: \(1\times 3^2 + 2\times 2^2 = 17\).
  • Buy \(4\) pots of first kind, \(1\) pot of second kind. The cost is: \(1\times 4^2 + 2\times 1^2 = 18\).
  • Buy \(5\) pots of first kind, \(0\) pot of second kind. The cost is: \(1\times 5^2 + 2\times 0^2 = 25\).

So, the optimal cost is \(17\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?