199C – About Bacteria

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 givencurrent bacteria goes as follows:

So, ifis the amount afterseconds starting withbacteria:







So, starting with 1 bacteria and after n seconds:

And starting with t bacteria after m seconds:

As we see, the computations are exponential and won’t fit into integer arithmetic. So, we can’t calculate 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 bothto be equal, m has to be the solution:


Subtract b then divide by k

Subtract b then divide by k

Keep going but remember that n > m:




So, for to be equal:

• We need to start with 1 bacteria. Wait until it grows to t bacteria ().
• 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;
}

199A – Hexadecimal’s theorem

The basic approach is:


Hence, if we generate the list of all Fibonacci numbers up to (input bound) the answer is just a binary-search-away.
C++ implementation:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long long int64;
#define N 48

int64 fib[N];
int nFib;

int64 generate() {
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < N; ++i)
		fib[i] = fib[i - 1] + fib[i - 2];
	return fib[N - 1];
}

int main(void) {
	generate();
	int64 n;
	cin >> n;
	int64 * p = upper_bound(fib, fib + N, n) - 1;
	if (p - 4 >= fib)
		cout << *(p - 4) << " " << *(p - 3) << " " << *(p - 1) << endl;
	else
		cout << "0 0 " << *p << endl;
	return EXIT_SUCCESS;
}

There’s an other naive (totally valid) solution. You noticed that 0 is a Fibonacci.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int n;
	scanf("%d", &n);
	printf("0 0 %d\n", n);
	return EXIT_SUCCESS;
}

Ironic!!!