Skip to content

Instantly share code, notes, and snippets.

@KoStard
Created April 13, 2018 18:10
Show Gist options
  • Save KoStard/ab468f97864c5acdeec87b29e953395a to your computer and use it in GitHub Desktop.
Save KoStard/ab468f97864c5acdeec87b29e953395a to your computer and use it in GitHub Desktop.
Task 85 of UniLecs Telegram
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