SPOJ.com - Problem KINJUTSU

KINJUTSU - POWER LEFT

no tags

Naruto is in the middle of the fight and his present power is p. He uses Tajū Kage Bunshin no Jutsu (Multiple Shadow Clone Technique) to create maximum n number of clones and he decided to distribute maximum p/2 power to the possible number of clones. First clone will always receive power equal to 1 and i th clone will receive power as i th term of an AP starting with 1 and having sum less than equal to p/2. Now he sends all even clones for observation and odd ones for fighting. After the battle is over only the observation clones and the highest power clone is alive. What is Naruto's power after he call back all his clones?

Input

The first line contains the number of test cases t (t <= 1000). The next following t lines will contain two integers p and n (1 <= p, n <= 10^9).

Output

Output must contains t lines consisting of the answer as mentioned in above question.

Example

Input:
1
200 10

Output:
155

Explanation:- Naruto is going to give 100 power to 10 clones. So there will be an AP with first term as 1 common difference 2. On adding required terms we get 55, and hence total power is 155.

Submit solution!

hide comments

< Previous 1 2 Next >

	Jacob Plachta: 2014-11-06 04:15:54 This problem is unacceptably unreadable as is, I can't figure out what exactly it's asking (I had one wild guess, but it wasn't accepted). Are we trying to maximize the number of clones first (at most N), followed by maximizing the sum of their powers (at most P/2)? For example, what happens if N>P/2 - then will only P/2 clones with power 1 be created? What determines Naruto's power at the end? Is it the sum of the powers of the clones who survive plus the power that was never used on any clones (the difference between P and the sum of the clones' powers)? In the sample input, are clones with powers 1,3,5,...,19 created, with clones 3, 7, 11, 15, and 19 surviving, causing the answer to be 100+3+7+11+15+19? It's necessary to address at least those questions in the problem statements, and hopefully offer an explanation of the sample case and possibly provide an additional sample case. EDIT--> the answer to your both ques is YES, in case N>P/2 only P/2 clones will form...it is the sum of the powers of the clones who survive plus the power that was never used on any clones...and including all conditions mentioned in ques.... RE: Alright, that's fine, then. But this problem is not sufficiently clear without all (or most) of these clarifications, so please either leave this comment visible or explain these omitted details in the problem statement. Last edit: 2014-11-06 06:58:22
	[bitthal]: 2014-11-05 18:51:07 my 60th NICE QUESTION :)

Submit solution!

Added by:	`Ak
Date:	2014-10-29
Time limit:	0.100s-1s
Source limit:	5000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All