DMOPC '14 Contest 7 P4 - Sand Triangle - Olympiads Online Judge

DMOPC '14 Contest 7 P4 - Sand Triangle

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 0.3s

Memory limit: 64M

Author:

Xyene

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$ ~r~ containing $r$ ~r~ numbers. When read from top to bottom, left to right, the triangle is made up of consecutive natural numbers starting from $1$ ~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$ ~N~ 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^3$ ~N \le 10^3~.

Subtask 2 [60%]

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

Input Specification

A single integer, $N$ ~N~.

Output Specification

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

Sample Input

Sample Output

Explanation

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

Comments

-8

jackyliao123 commented on May 6, 2015, 9:43 p.m. ← edited →

So the judge allows people to brute force when there is an $\mathcal{O}(1)$ ~\mathcal{O}(1)~ solution.

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)$ ~\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 →

But my $\mathcal{O}(1)$ ~\mathcal{O}(1)~ solution beats everyone.

Therefore, you should turn down the time limit.

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.

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

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})$ ~\mathcal{O}(\sqrt{N})~, which is the intended solution.

-6

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

Yeah, I agree. Time limit should be lowered

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.

11

bobhob314 commented on May 7, 2015, 12:24 a.m. ← edit 3 →

12

omaewamoushindeiru commented on May 7, 2015, 3:52 a.m.

I WAS LEARNING THIS 'MARKDOWN' SYNTAX

2
FatalEagle commented on May 5, 2015, 10:01 p.m.
You should have public class instead of just class

You should not prompt for input. Match the format exactly as given in the problem.