Created
April 13, 2018 18:10
-
-
Save KoStard/ab468f97864c5acdeec87b29e953395a to your computer and use it in GitHub Desktop.
Task 85 of UniLecs Telegram
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function task85(k){ | |
console.log((-1+Math.sqrt(1+8*k))/2) | |
z = Math.ceil((-1+Math.sqrt(1+8*k))/2); | |
if (k%2==0){ | |
while (z%4!=3 && z%4!=0){ | |
z++; | |
} | |
}else{ | |
while (z%4!=1 && z%4!=2){ | |
z++; | |
} | |
} | |
return z; | |
} | |
console.log(task85(3)); | |
/* So the explanation. | |
Every time if we invert number d, then the sum will decrease with 2*d. | |
So, if we get even k, then the sum initially will be even, | |
because it will decrease every time with even number, so it will stay even and vice versa. | |
OK... But how to get that sum? Because this is arithmetic progression, we can calculate the sum | |
using this formula. | |
sum = z*(z+1)/2 | |
If we want to know the minimal sum bigger than k, then we have to calculate the z for sum = k. | |
We may get float, because it is not the real sum, it just shows the threshold for the sum (so the final z will be bigger than this z). | |
In the k=3 example, we get z = 2; | |
the final z (fz) will be bigger or equal to z, because if we already found the exact sum which is equal to the k, then the problem is solved. | |
If not, then here we get a new task. | |
To get even sum, the z will be: | |
n*4+3 | |
n*4 | |
and to get odd sum, the z will be: | |
n*4+1 | |
n*4+2 | |
(where n is natural number) | |
To understand this part, just imagine a row of number from 1 to n. | |
1 2 3 4 5 6 7 8 9 | |
Every time we add a odd number, it's "oddity" can be neutralized by another waiting odd number by adding to it, | |
or can start waiting for a pair. | |
1 - is waiting for a pair | |
1 2 - nothing happens [the sum stays odd] | |
1 2 3 - because 1+3=4, they neutralize each other | |
1 2 3 4 - nothing happens [the sum stays even] | |
* * | |
So as we can see, when we get 4*n or 4*n-1 (4*n+3) numbers (z), then we get even sum, | |
otherwise (4*n+1 & 4*n+2) we get odd sum. | |
So the problem is practically done, because we just have to find the minimal fz value, that is bigger than z | |
and meets the criteria (even/odd 4*n+m). | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment