GAMARENA - GAMING ARENA

no tags 

 

GAMIN ARENA


 

Elgin and Hajee are planning to conduct gamindrome next day. As they have to connect all the computers, they need lan cables, hubs and wireless routers. They went to Richi street to purchase them. Unexpectedly hub was not available in any shop.

Any lan cable can connect two computers. Any wireless router can connect atmost ‘k’ number of computers. Any computer can be connected to atmost one lan cable and atmost one wireless network. If a computer is connected to both lan and wireless, the connections get automatically bridged.

 

They have n computers and their aim is to connect all the computers with minimum cost. So they have to buy minimum number of lan cables and wireless routers.

The cost of of buying one lan cable is L and the cost of buying one wireless router is W. 

Given n, k, L and W find the minimum cost needed to connect all the computers.

 

Input Specification:

The first line contains an integer t, the number of test cases. Each test case consists 4 integers n, k, L and W as defined above.

 

Output Specification:

For each test case find the minimum cost to connect all the computers.

Input Constraints:

1<=t<=1000

1<=n<=1000

2<=k<=1000

1<=L<=1000

1<=W<=1000

 

Sample Input: 

 9

1 4 8 6

10 2 5 8

5 4 9 9

2 5 2 6

7 3 3 6

3 3 3 5

6 4 7 2

10 4 2 7

5 3 10 8

Sample Output:

0

57

18

2

18

5

11

20

26

3 2

359 5 5 5
146 2 5 3

hide comments
nadstratosfer: 2019-12-26 15:36:44

Took 2h to find the error in my logic. God bless pen & paper!

Edit: .. and another hour to bring the complexity down to what it should be. It was fun, but nevertheless thanks for TL that allows the less elegant solution to pass. cegprakash = best psetter!

Last edit: 2019-12-26 18:19:15
cegprakash: 2014-04-17 10:03:04

Abhishek Mishra : Write a test case generator and match your output against a brute force solution.

Abhishek Mishra: 2013-02-11 18:04:23

may u plz the provide the test case where my code fail plzz admin i have crrct code for it but i want to figure out the part where my this algo fails.


Added by:cegprakash
Date:2012-05-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU