5103. Koza Nostra
While the
students are taking their exams, the teachers play Mafia. There are n teachers sitting in a circle. The
dealer must distribute cards with aces (any number of aces, possibly 0) to
some of them, and those teachers will be the Mafia. However, no two Mafia
members should sit next to each other.
In how many ways the
dealer can distribute the cards? Two ways are considered different if there is
at least one teacher who is Mafia in one case, but not Mafia in the other.
Input. The number of teachers n (1 ≤ n ≤ 30),
siting in a circle.
Output. Print the number of ways to deal the cards.
|
Sample
input 1 |
Sample
output 1 |
|
1 |
2 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
2 |
3 |
SOLUTION
Fibonacci numbers
Algorithm analysis
Let g(n) be the number of ways to distribute the cards to n teachers who are arranged in a
row (the first one is not next to the last one). This problem is equivalent to finding the number of sequences
of length n consisting of 0s and 1s, where no two 1s are adjacent. Its solution is given by the Fibonacci
number defined
by the recurrence relation:
Let f(n) be the number of ways to distribute cards to n teachers arranged in a circle.
If the first
teacher did not receive an ace, then the remaining n – 1 teachers can be given aces in g(n – 1) ways. If the first teacher received an ace, then we should
not give aces to the second and last teachers. The remaining n – 3 teachers can be given aces in g(n – 3) ways. We have the following relationship:
f(n) = g(n – 1) + g(n – 3), if n ≥ 3
Example
For n = 3 we need the value of g(0), that can be calculated from the equation g(0) + g(1) = g(2), where g(0) = g(2) – g(1) = 3 – 2 = 1.
Therefore, f(3) = g(2) + g(0) = 3 + 1
= 4.
Here is the base cases:
·
f(1) = 2
·
f(2) = 3
Algorithm realization
Declare an array to store Fibonacci numbers.
#define MAX 46
int fib[MAX];
The main part of the program. Calculate Fibonacci numbers.
fib[0] = 1; fib[1] = 2;
for (int i = 2; i < MAX; i++)
fib[i] =
fib[i - 1] + fib[i - 2];
Read the input number n.
scanf("%d", &n);
Find the answer res.
if (n == 1) res = 2; else
if (n == 2) res = 3; else
res = fib[n - 1] + fib[n - 3];
Print the answer.
printf("%d\n", res);
Java realization
import java.util.*;
public class Main
{
private static final int MAX = 46;
public static void main(String[] args)
{
Declare an array to store Fibonacci numbers.
int[] fib = new int[MAX];
Calculate Fibonacci numbers.
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < MAX; i++)
fib[i] = fib[i - 1] + fib[i - 2];
Read the input number n.
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Find the answer res.
int res;
if (n == 1) res = 2;
else if (n == 2) res = 3;
else res = fib[n - 1] + fib[n - 3];
Print the answer.
System.out.println(res);
}
}
Python realization
Declare an array to store Fibonacci numbers.
fib
= [0] * 46
Calculate Fibonacci numbers.
fib[0] = 1
fib[1] = 2
for i in range(2, 46):
fib[i] = fib[i - 1] + fib[i - 2]
Read the input number n.
n = int(input())
Find the answer res.
if n == 1: res = 2
elif n == 2: res = 3
else: res = fib[n - 1] + fib[n - 3]
Print the answer.
print(res)