4538. Bob and balls
Recently Bob
learned that balls can be played in a very entertaining game. In this game you
want to stack the balls in the form of various geometric shapes. Just now Bob
is engaged in laying the balls in the form of an equilateral triangle. But
here's the thing: sometimes Bob do not have enough balls, and he wants to know,
what is the greatest side of the triangle for which it is enough balls? Help
Bob to count the value of n –
the length of equilateral triangle for given number of balls k.
Below given the
example of placing the balls in the form of an equilateral triangle:
Input. One positive integer k (0 ≤ k
≤ 2 *108), the existing number of balls.
Output. Print the
value of n – the answer to the
problem.
|
Sample
input |
Sample
output |
|
5 |
2 |
SOLUTION
combinatorics
Algorithm analysis
If n is the length of the side of triangle,
then for its complete packing it is required 1 + 2 +… + n = n * (n
+ 1) / 2 balls.
There are k balls
available. Solve the equation n * (n
+ 1) / 2 = k and round the non-negative root down to
the nearest integer.
Solve the
quadratic equation: n2 + n – 2k
= 0, d = 1 + 8k, n = 
.
The answer is the value 
.
Algorithm realization
Read the value of k. Compute and print the answer.
scanf("%d",&k);
n = int((-1 + sqrt(1.0 + 8*k)) / 2.0);
printf("%d\n",n);
Ðåàëèçàöèÿ àëãîðèòìà – áèíàðíûé
ïîèñê
#include <stdio.h>
long long n, k, l, r, mid, res;
long long f(long long n)
{
return n * (n + 1) /
2;
}
int my_upper_bound(int start, int end, int x)
{
while (start <
end)
{
int mid = (start +
end) / 2;
if (f(mid) > x)
end = mid;
else
start = mid + 1;
}
return start;
}
int main()
{
scanf("%lld", &k);
// find min n: f(n) >= k
if (k == 0) res =
0;
else if (k == 1) res =
1;
else res =
my_upper_bound(0, k, k) - 1;
printf("%d\n", res);
}
Ðåàëèçàöèÿ àëãîðèòìà – O(sqrt(n))
#include <stdio.h>
long long n, k, res;
long long f(long long n)
{
return n * (n + 1) /
2;
}
int main()
{
scanf("%lld", &k);
// find min n: f(n) >= k
n = 0;
while (f(n) <= k) n++;
printf("%d\n", n);
}