SQRMINSUM  Minimum Sum
Suppose you have a list of integers, and a move is defined as taking one of the integers from the list and replacing it with its square root, rounded down to the nearest integer.
Given an integer l
and an integer k
, start with the array [1, 2, 3, ..., l]
and find the minimal sum of the array after k
moves.
Example
For l = 5
and k = 2
, the output should be
squareRoots(l, k) = 10
.
We start with [1, 2, 3, 4, 5]
.
After square rooting 5
to get [1, 2, 3, 4, 2]
and then square rooting 3
to get[1, 2, 1, 4, 2]
, we end up with a sum of 10
.
Constraints:
1 ≤ l ≤ 10^{4 }
1 ≤ k ≤ 10^{4}
^{ T=10000}
Input :
The first line contains T the number of test cases followed by 2*T lines containing l and k.
Output:
For every test case, output one line containing an integer, i.e. the minimal possible sum.
Sample Input:
2
5
2
2327
4895
Sample Output:
10
10647
hide comments
Ishan:
20180419 07:22:18
O((k+l)*log(l)) with C++ STL's priority queue is sufficient, just be careful not to use computation heavy floating point calculating like sqrt() etc. 

nadstratosfer:
20171117 08:10:50
Good time limit so you get to see what you're doing right. Turns out you can even pass with pure Python! Coding style makes all the difference. Great problem. 

saurabh:
20170322 14:04:03
can anyone help me what to use instead of priority queue to avoid TLE


vengatesh15:
20170307 09:59:06
easy one no need of priority queue .... 

avisheksanvas:
20160712 08:49:07
It does indeed give the feel of a @vectar31 type problem ;)


jinxer:
20160630 15:27:31
@vectar31 Bro you're an inspiration to me. Can you please give me Your History of submission" (Plaintext Version)"..So that i Could follow it!!!


iharsh234:
20160630 08:19:11
why priority queue in pypy gives TLE?


Shubhransh Srivastav:
20160625 10:14:14
fast i/o+priority queue...just managed to beat the time limit :) 

mokinjay:
20160617 01:33:29
U have given time limit 5second then how a soln of O(klog(l)) give tle..?


Piyush Kumar:
20160614 15:06:49
@Bhuvanesh, i have updated that number of test cases=10000, and k<=10000, and l<=10000. Given your complexity, your number of calculations will be in the order of 10^9 which will time out. You need to do better with the complexity. Also, think about doing some pre computation. 
Added by:  Piyush Kumar 
Date:  20160610 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Standard Pro Co 