7438. Binary password

Jomart uses a binary string as the password for his computer. Recently, he forgot his old password and now wants to obtain a new one, which will be a binary string of length n. He considers a password sufficiently secure if it does not contain two consecutive zeros.

To obtain a new password, Jomart generates a random binary string of length n. If the string is not secure, he generates another one and repeats the process until he obtains a secure password.

Find the expected number of randomly generated passwords Jomart will need before he finds a secure one.

Input. One integer n (1 ≤ n ≤ 60).

Output. Print the expected value as a fraction p / q, where  p and q are coprime positive integers.

Sample input 1	Sample output 1
1	1/1
Sample input 2	Sample output 2
4	2/1

SOLUTION

mathematics

Algorithm analysis

A password (a string of length n) is considered secure if it does not contain two consecutive zeros. The number of such strings is equal to the Fibonacci number f_n, defined as follows:

f₁ = 2 (the strings 0, 1),

f₂ = 3 (the strings 01, 10, 11),

f_n = f_n-1 + f_n-2, n > 3

For example, the first Fibonacci numbers are:

The total number of binary strings of length n is 2ⁿ. Therefore, the expected number of randomly generated strings required to obtain a secure one is equal to

2ⁿ / f_n

This fraction should be reduced by dividing the numerator and the denominator by their greatest common divisor.

Example

For n = 1, the answer is 2¹ / f₁ = 2 / 2 = 1 / 1.

For n = 4, the answer is 2⁴ / f₄ = 16 / 8 = 2 / 1.

Algorithm implementation

Declare an array to store the Fibonacci numbers.

long long f[61];

The function gcd computes the greatest common divisor of two numbers.

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b, a % b);

}

The main part of the program. Read the input value n.

scanf("%d", &n);

Compute the Fibonacci numbers.

f[0] = 1; f[1] = 2;

for (i = 2; i <= n; i++)

f[i] = f[i - 1] + f[i - 2];

The answer is given as a fraction:

num / den = 2ⁿ / f_n

Reduce this fraction by dividing the numerator and the denominator by their greatest common divisor.

num = (1LL << n);

den = f[n];

d = gcd(num, den);

num /= d;

den /= d;

Print the answer.

printf("%lld/%lld\n", num, den);