DMOPC '14 Contest 7 P4 - Sand Triangle

View as PDF

Submit solution

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

Author:
Problem type

Bored out of his mind from being stranded on an island, Tusk has taken to writing down sequences of numbers in the sand. Today, he decided to write down a triangle of numbers, with each row r containing r numbers. When read from top to bottom, left to right, the triangle is made up of consecutive natural numbers starting from 1.

       1
      2 3
     4 5 6
    7 8 9 10
 11 12 13 14 15
16 17 18 19 20 21
      ...

Being curious and having nothing better to do, Tusk wonders what the sum of all the numbers on the row that contains the number N is.

Unfortunately, his beach is too small for him to write down such a massive triangle!

Constraints

Subtask 1 [40%]

For 40\% of the points, it will hold that N \le 10^3.

Subtask 2 [60%]

For the remaining 60\% of the points, it will hold that N \le 10^9.

Input Specification

A single integer, N.

Output Specification

The sum of all the numbers on the row of the triangle containing N.

Sample Input

5

Sample Output

15

Explanation

Considering the example triangle, 5 is contained in row 3, which contains the numbers 4+5+6 = 15.


Comments


  • -8
    jackyliao123  commented on May 6, 2015, 9:43 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 5
      FatalEagle  commented on May 6, 2015, 10:15 p.m.

      Clearly your \mathcal{O}(1) is slower than many of these brute force solutions! I could reduce the time limit, but that would mean that you will TLE before these brute force solutions will.


      • -11
        lolzballs  commented on May 7, 2015, 2:08 a.m. edit 4

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 3
          FatalEagle  commented on May 7, 2015, 2:42 a.m.

          My "brute force" is faster than your submission now. I could change the time limit, just for your submission, if you really want to go that way.


          • -6
            lolzballs  commented on May 7, 2015, 8:27 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


            • 5
              FatalEagle  commented on May 7, 2015, 8:36 p.m.

              What are you talking about? The "brute force" you guys seem to be talking about is \mathcal{O}(\sqrt{N}), which is the intended solution.


        • -6
          jackyliao123  commented on May 7, 2015, 2:29 a.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • 3
            quantum  commented on May 7, 2015, 2:34 a.m.

            For obvious reasons the time limit can't be changed when the problem is attempted by 50+ people.


      • 4
        kobortor  commented on May 6, 2015, 10:16 p.m. edited

        rekt

        fatal tell like it is


  • -3
    LiPatrick  commented on May 5, 2015, 9:51 p.m.

    why


    • 3
      omaewamoushindeiru  commented on May 6, 2015, 10:11 p.m. edit 7

      Please visit here.


    • 2
      FatalEagle  commented on May 5, 2015, 10:01 p.m.
      1. You should have public class instead of just class
      2. You should not prompt for input. Match the format exactly as given in the problem.