| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Given an integer $$$N$$$. Find two integers such that their product is strictly greater than $$$N$$$ and sum is minimum. How to solve this in O(1)?
P.S.- I posted this before, as I though contest ended at 9 pm. Sorry about that. JEEADVANCED can you confirm if the contest has ended.
2*sqrt(N)+1 are you really a specialist or is it magic?
Derivation/Logic of the above formula?
Yes I am a specialist and I too get stuck at simple problems. There's nothing harm in that buddy :)
Ya buddy did not mean to insinuate From Wiki
By the AM-GM inequality, we know that $$$a + b \gt = 2\sqrt{ab} \gt = 2 \sqrt{N}$$$. I assume that $$$a + b \in Z$$$. If so, when $$$N$$$ is a perfect square, we can achieve $$$2\sqrt{N}$$$ with $$$a = b = \sqrt{N}$$$. If $$$N$$$ is not a perfect square, we can achieve $$$2\sqrt{N} + 1$$$ with $$$a = b$$$ as the ceiling of $$$\sqrt{N}$$$ (and if it is possible, also consider (a, b — 1)).
Like you said, For $$$N$$$ = 5, your answer is $$$(3, 4)$$$ whereas the optimal answer is $$$(2, 3)$$$
My answer for $$$N = 5$$$ is $$$(2,3)$$$. o_O
Bruh. I knew you'd change that to floor of $$$sqrt(N)$$$. Now try for $$$N$$$ = 6, your answer is $$$(2, 3)$$$ whereas the right answer is $$$(3, 3)$$$ or $$$(4, 2)$$$ lol.
Oh I didn't read strictly greater. Then replace N with N + 1
That still yields $$$(2, 3)$$$ for $$$N = 6$$$ by your definition.
It does not. The ceiling of sqrt(7) is 3. So it produces whichever is better: (3,4) or (3,3).
Why are u so indecisive and changed your comment to justify your point? -_-
I did change my answer; however, before it used to say (3,4) for 6, not (2,3). I
You're still indecisive.
Go ahead and change your comment to $$$(3, 3)$$$, $$$(3, 2)$$$, according to your definition.
ok whatever you know what I mean
All i know you're stub and still wrong lol.
Have fun editing your comment ;)
PS: Don't downvote my comment out of shame lol.
Yeah I was wrong (I never said I was right, and I'm grateful you pointed it out). The fix is pretty easy, though, just let $$$a$$$ be the floor of the square root of $$$n + 1$$$ and chose the best of $$$(a,a+1)$$$, $$$(a,a)$$$, and $$$(a + 1, a + 1)$$$.