Tag: 199C

199C – About Bacteria

by MSiddeek, posted in Ad-hoc, Algorithms, Math, Problems

Let’s follow the straight-forward approach:

  • Start with one bacteria. Calculate the growth after n seconds.
  • Start with t bacteria. Keep growing until you reach the amount in the first step.
  • The time you waited for in the previous step is the solution.

The amount of bacteria for the next second givenx current bacteria goes as follows:
f(x) = k \cdot x + b
So, ifz_i(x) is the amount afteri seconds starting withx bacteria:
z_1(x) = x k + b
z_2(x) = x k^2 + k b + b
z_3(x) = x k^3 + k^2 b + k b + b
\\
\\
...
z_i(x) = x k^{i} + k^{i-1} b + k^{i-2} b + ... b
So, starting with 1 bacteria and after n seconds:
z_n(1) = 1 k^{n} + k^{n-1} b + k^{n-2} b + ... b
And starting with t bacteria after m seconds:
z_m(t) = t k^{m} + k^{m-1} b + k^{m-2} b + ... b
As we see, the computations are exponential and won’t fit into integer arithmetic. So, we can’t calculate z_n(1) which is the first step of the solution. The straight-forward solution won’t work. We have to find another way around.
Let’s continue with the math. For bothz_n(1), z_m(t)to be equal, m has to be the solution:
z_n(1) = z_m(t)
1 k^{n} + k^{n-1} b + k^{n-2} b + ... b = t k^{m} + k^{m-1} b + k^{m-2} b + ... b
Subtract b then divide by k
1 k^{n-1} + k^{n-2} b + ... b = t k^{m-1} + k^{m-2} b + ... b
Subtract b then divide by k
1 k^{n-2} + ... b = t k^{m-2} + ... b
Keep going but remember that n > m:
\\
\\
...
1 k^{n-m} + k^{n-m-1} b + k^{n-m-2} b + ... b = t = z_{n-m}(1)
So, for z_n, z_m to be equal:

  • We need to start with 1 bacteria. Wait until it grows to t bacteria (t = z_{n-m}(1)).
  • The time we waited is n – m. So the solution m is n – (n – m).

The computations aren’t that large this time. C++ implementation:

#include <iostream>
using namespace std;

typedef unsigned long long int64;

int main(void) {
	int64 k, b, n, t, m, zm = 1;
	cin >> k >> b >> n >> t;
	for (m = 0; m < n && zm < t; ++m)
		zm = k * zm + b;
	if (zm > t)
		m--;
	cout << n - m << endl;
	return 0;
}