RTE '16 S1 - Battery Pyramids

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types

If you want to find the most innovative students at RHHS, there’s only one place to look: TEJ4M1. Here, the students are always finding new ways to challenge reality and solve unknown problems. On an average day in TEJ4M1, the students had an extra-special idea. They decided to stack all of the AA batteries in the classroom into triangles of different base sizes, as shown below.

However, they encountered a little problem. Out of the N batteries available in the classroom, the rest of the class (the unproductive part) needed K batteries in order to use their power-hungry drone remotes. Due to this ridiculous restriction, the highly motivated students decided they only had one option: to maximize the awesomeness they could get with the limited supply to batteries they had. This involved creating battery triangles of ascending base length, following the set of natural numbers (1, 2, 3, 4, 5,... ), and using as many of the available batteries as possible.

In order to help them, you, as the Gordon of the class, need to find the number of batteries required to create the maximum number of pyramids.

Input Specification

The first line will contain T (1 \leq T \leq 10\,000), the number of test cases.

The next T lines will contain two space separated integers, N and K (0 \leq K < N \leq 10^9).

For test cases worth 20 of 100 points, 0 \leq N \leq 10^3.

For test cases worth an additional 30 points, 0 \leq N \leq 10^6.

Output Specification

Output a single integer, representing the number of batteries required to create the maximum number of pyramids with the given number of available batteries.

Sample Input 1

1
40 10

Sample Output 1

20

Explanation for Sample 1

Of the 40 available batteries, the rest of the class needs 10. That leaves 40 - 10 = 30 batteries for the triangles. The first four available triangles result in triangles with 1, 3, 6, and 10 batteries. 1 + 3 + 6 + 10 = 20. Adding the next sized triangle, which contains 15 batteries, will bring the total battery requirement up to 20 + 15 = 35, which is more than the available 30. Thus, 20 batteries is the maximum the students could use.

Sample Input 2

1
10000 1000

Sample Output 2

8436

Explanation for Sample 2

Use the first 36 triangles. 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55 + 66 + 78 + 91 + 105 + 120 + 136 + 153 + 171 + 190 + 210 + 231 + 253 + 276 + 300 + 325 + 351 + 378 + 406 + 435 + 465 + 496 + 528 + 561 + 595 + 630 + 666 = 8436


Comments


  • 0
    Phoenix1369  commented on June 16, 2017, 7:27 p.m.

    Partial scoring for this problem has been enabled and all submissions have been re-scored. Apologies for any inconvenience caused.