Must be written in C++, thanks!: Your librarian has a 2-row bookshelf that can c
ID: 3862414 • Letter: M
Question
Must be written in C++, thanks!:
Your librarian has a 2-row bookshelf that can contain N books in each row. She wants to know the number of ways that she can fill the bookshelf with red-colored books and blue-colored books such that no 2 red-colored books are adjacent to each other (horizontally or vertically).
Input: the integer, N (1<=N<=2^1024)
Output: the number of ways you can place red-colored books and blue-colored books onto a N-column bookshelf. Since this number might be really big, output it mod 10^9+7.
Example: Input: 2
Your valid bookshelf layouts are:
Therefore, Output: 7
You do not need to output the bookself layout letters, just the number of ways you can place red-colored books and blue-colored books onto a N-column bookshelf.
Input is whatever the user puts, could be 5, could be 30, could be whatever integer.
Explanation / Answer
Hi buddy, this is a simple dynamic programming question. Let's denote the combination BB(Black on both the rows) as 0. BR(Black on top and red at thebottom) as 1, RB(Red on top and black at the bottom) as 2. Now we can form a recurrence.
Let ways[i][j] (where i<=n and j<=2) as the number of ways of arrangement when there are i elements in a row and the present combination is j
C++ Program
#include <iostream>
using namespace std;
int main() {
// your code goes here
int n;
int mod = 1000000007;
cin >> n;
//Let's denote ways of arranging books from ith index to the end
int ways[n+1][3];
//Initialize to 0
for(int i=0;i<=n;i++){
ways[i][0] = ways[i][1] = ways[i][2] =0;
}
//Number of ways of all combinations for the last row is 1
ways[n][0] = ways[n][1] = ways[n][2] = ways[n][3] = 1;
//Loop through and follow the recurrence
for(int i=n-1;i>=1;i--){
ways[i][0] = (ways[i+1][0] + ways[i+1][1] + ways[i+1][2])%mod;
ways[i][1] = (ways[i+1][0] + ways[i+1][2])%mod;
ways[i][2] = (ways[i+1][0] + ways[i+1][1])%mod;
}
//Final answer will be sum of all the combinations at index 1
int ans = (ways[1][0] + ways[1][1] + ways[1][2] )%mod;
cout << ans << endl;
return 0;
}
OUTPUT :
3
17
1
3
2
7
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.