### hello__world_'s blog

By hello__world_, history, 6 weeks ago,

You are given two types of people, type A and type B. You need to place n people of any type but the condition is that no two A type people is close to each other, means [A,A,B,A,B] not possible since two A type person are close to each other. You need to find all the possible arrangement. Print the answer modulo 1e9 + 7.

Constraints

1 <= n <= 100000

Input: 3 Output: 5

Explanation: if n = 3 then possible combinations are [B,B,B] [A,B,B] [B,A,B] [B,B,A] [A,B,A]

• +6

 » 6 weeks ago, # |   0 Is there a link to that problem?
•  » » 6 weeks ago, # ^ |   +3 The problem is same as finding number of n bit strings without any pair of consecutive ones. For n = 3, all strings:000, 001 , 010, 011, 100, 101, 110, 111strings satisfying the constraints:000, 001, 010 ,100, 101So total 5 string are there.
 » 6 weeks ago, # | ← Rev. 2 →   +3 I believe this was asked in Publicis Sapient — Jumpstart, my approachthis is a basic dp problem, where we can have states like dp[i][0] -> number of such strings ending with A dp[i][1] -> number of such strings ending with B transitions will go like dp[i][0] = dp[i-1][1] //if i_th char is A then i-1 th char has to be B dp[i][1] = dp[i-1][0] + dp[i-1][1] // if i_th char is B then i_1th char can be anything base case will be one character strings, so dp[0][0] = 1 dp[0][1] = 1 something coolit is fibonacci ;-;
•  » » 6 weeks ago, # ^ |   0 This problem was also in dynamic programming course, on informatics.msk.ru. If you know russian and want to learn classic dp problems, check the course out.
•  » » 6 weeks ago, # ^ |   +1 Could the reasoning be something like this? More DetailsLet us answer the question how many strings of length $i$ are there that satisfy the conditions. To solve denote $f(i) =$ number of valid strings of length $i$. Now two cases: We have a $1$ as the $ith$ bit in which case the number of valid strings is the number of valid strings of length $i - 2$, i.e. $f(i - 2)$ because given a $1$ at position $i$ the previous number must be $0$. Anything before $0$ must also be a valid string. We have a $0$ as the $ith$ bit in which case the number of valid strings is the number of valid strings of length $i - 1$, i.e. $f(i - 1)$ because given a $0$ at position $i$ we just need the previous $i - 1$ characters to form a valid string. Thus the answer is $f(i) = f(i - 1) + f(i - 2)$, i.e. Fibonacci.
 » 6 weeks ago, # | ← Rev. 2 →   0 if n = 1 ans = 2 if n = 2 ans = 3 if n = x ans = f(x-1) + f(x-2)
 » 6 weeks ago, # | ← Rev. 2 →   0 this can be done easily in math. We convert the problem this way: given all the B's already arranged, insert A's into them such that no 2 of them take the same place. It is now obvious that the answer is (number of B)+1 choose number of A places to insert them.
 » 6 weeks ago, # | ← Rev. 2 →   0 you can easily solve it with stars and bars, assume z spaces like __ a1 __ a2 __ a3... __ a4 __ , which would be lets say, z = |a| + 1, so what you have is b1 + b2 + b3 + ... + bz = |b| here b1,bz >= 0 and b2,b3...b_{z-1} >= 1 so b1 + b2 + b3 + ... + bz = |b| — |a| + 1for stars and bars we know that ,its (n + k — 1) C (r — 1)so its (|b| — |a| + 1 + z — 1 ) C (z — 1)which is (|b| + 1) C (|a|)we know |b| + |a| = n(n — |a| + 1) C |a|you can easily find summation pattern from this as |a| is in range [0 , n]
»
6 weeks ago, # |
0

# include <bits/stdc++.h>

using namespace std;

# define mod 1000000007

int main() { int n; cin>>n; vectordp(n+1); dp[0]=1; dp[1]=2; for(int i=2;i<=n;i++) { dp[i]=(dp[i-2]%mod + dp[i-1]%mod)%mod; } cout<< dp[n]; }

 » 6 weeks ago, # |   0 nice but easy problem