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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • -6
    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.


      • -9
        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.


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

            Obviously, that means that the test cases aren't "extreme" enough.


            • 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.


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

          Yeah, I agree. Time limit should be lowered


          • 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.


      • 4
        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.


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


        • 10
          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.