DMOPC '14 Contest 8 P4 - Sand Triangle

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.42s
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 rr containing rr numbers. When read from top to bottom, left to right, the triangle is made up of consecutive natural numbers starting from 11.

       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 NN is.

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

Constraints

Subtask 1 [40%]

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

Subtask 2 [60%]

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

Input Specification

A single integer, NN.

Output Specification

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

Sample Input

5

Sample Output

15

Explanation

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


Comments


  • 2
    billsboard  commented on Feb. 16, 2021, 9:39 p.m.

    0.42s, such a specific TL


  • -7
    jackyliao123  commented on May 6, 2015, 5:43 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 6
      FatalEagle  commented on May 6, 2015, 6: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.


      • -10
        lolzballs  commented on May 6, 2015, 10:08 p.m. edit 3

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 3
          FatalEagle  commented on May 6, 2015, 10:42 p.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.


          • -5
            lolzballs  commented on May 7, 2015, 4:27 p.m.

            This comment is hidden due to too much negative feedback. Click here to view it.


            • 6
              FatalEagle  commented on May 7, 2015, 4: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.


        • -5
          jackyliao123  commented on May 6, 2015, 10:29 p.m.

          This comment is hidden due to too much negative feedback. Click here to view it.


          • 4
            quantum  commented on May 6, 2015, 10:34 p.m.

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


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

        rekt

        fatal tell like it is


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

    why


    • 4
      BMP  commented on May 6, 2015, 6:11 p.m. edit 7

      Please visit here.


      • 10
        bobhob314  commented on May 6, 2015, 8:24 p.m. edited


        • 12
          BMP  commented on May 6, 2015, 11:52 p.m.

          I WAS LEARNING THIS 'MARKDOWN' SYNTAX


    • 2
      FatalEagle  commented on May 5, 2015, 6: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.