| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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 >= 2\sqrt{ab} >= 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)$$$.