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 >

	naruto09: 2015-12-18 17:22:29 common difference should always be an integer. ?? final answer always an integer..?? @naruto09--> no it can have precision loss Last edit: 2015-12-18 17:28:54
	sy_117: 2015-08-26 23:44:41 Nice ques. only take care of diff. cases.
	Jaswanth: 2015-08-16 13:52:17 easy one to get 1 point don't forget atmost n clones
	xMAn: 2015-08-03 11:01:04 getting SIGFPE error :/
	Aman Agarwal: 2015-06-08 10:46:23 Voila! got 1 point..just needed to take care of some silly cases
	sdda: 2015-04-14 10:51:43 for those who are getting SIGFPE runtime error.......guys also include the case when n=0 with n=1.....
	Amit Ajaat: 2014-12-22 11:57:18 Akay sir,u please explain ,can we have any real number including (floats)as the common difference of AP or just integers,also u post some more testcases!!!Not everyone watches naruto RE- u can work with any data type either float or int, and to solve this there is no need to be a naruto fan :P Last edit: 2014-12-31 14:01:23
	Mordekaiser: 2014-11-06 09:02:09 How to read the problem? The AP is the ability power? Mordekaiser can always use ability power... If the AP is the Arithmetic Progression, is the increment the integers? Or can it be the reals? Is this real life? What does "maximum n clones" mean? Can we use the negative value of the difference of an AP? Last edit: 2014-11-06 09:08:41
	`Ak: 2014-11-06 06:58:04 @Jacob Plachta I feel the question is well explained as it is mentioned that the possible number of clones that can be formed and at last that we have to find the Naruto's power that specifies that the total amount of power left with Naruto.. What do you find unclear in it?? RE: The statement leaves out many details entirely, such as how the arithmetic progression is determined (namely, that the number of terms is first maximized (up to N), breaking ties by maximizing the sum of the terms (up to P/2)), and what determines Naruto's final power. Without that, there are multiple possible interpretations which can only be narrowed down by trying cases, which isn't fine. Last edit: 2014-11-06 08:56:48
	UJtriumphsâ„¢: 2014-11-05 21:10:52 Some more test cases :) 18 10 O/P->14 200 9 O/P->172 Last edit: 2014-11-06 07:01:21

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