PROBLEM LINK:
Practice
Contest
Author: Pratik
Tester: Varun
Editorialist: Pratik
DIFFICULTY:
MEDIUM .
PREREQUISITES:
Greedy, STL.
PROBLEM:
Normal form of Fibonacci series upto N is A1, A2, A3, …, AN-1, AN.
Our special fibonacci series is A1, AN, A2, AN-1, …, AN/2.
For a given N, print the first M numbers for this special Fibonacci series.
As the numbers can be very big, print the number modulo 1000000007.
EXPLANATION:
-
For N=10 Fibonacci series would be: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
-
And is the above order it would be: [0, 34, 1, 21, 1, 13, 2, 8, 3, 5]
-
To print first M numbers: 0 34 1 21 1 13
Basically, we will take normal fibonacci series as input , then we will check index of i if i is odd we will print odd index from normal fibonacci series, otherwise we will print even index of fibonacci series.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int modd=1000000007;
long long int fibarr[1000001];
void fibb(void)
{
fibarr[0]=0;
fibarr[1]=1;
for(int i=2;i<=1000001;i++)
{
fibarr[i] = (fibarr[i-1]+fibarr[i-2])%modd;
}
}
int main()
{
int t;
cin>>t;
fibb();
while(t–)
{
int n,m;
cin>>n>>m;
int odd=0;
int even=n-1;
vectorres;
for(int i=0;i<=m;i++)
{
if(i%2==1)
{
res.push_back(fibarr[even]);
even–;
}
else
{
res.push_back(fibarr[odd]);
odd++;
}
}
for(int i=0;i<m;i++)
{
cout<<res[i]<<" ";
}
cout<<endl;
}
}
Tester's Solution
cook your dish here
import sys
input = sys.stdin.readline
fib=[0](106 + 1)
fib[1]=1
mo=109+7
for i in range(2,106+1):
fib[i]=(fib[i-1]+fib[i-2])
for _ in range(int(input())):
n,m=map(int,input().split())
left=0;right=n-1
for i in range(m):
if(i%2):
print(fib[right],end=" “)
right-=1
else:
print(fib[left],end=” ")
left+=1
Editorialist's Solution
import java.io.*;
import java.util.Arrays;
class Main
{
public static void main(String[] args) throws Exception{
Solution obj = new Solution();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine().trim());
while(T–>0){
System.out.println(obj.solve(in.readLine().trim().split(" ")));
}
}
}
class Solution {
int nums[] = new int[1000000];
int M = 1000000007;
Solution(){
nums[0] = 0; nums[1] = 1;
for(int i=1; i<1000000-1;i++){
nums[i+1] = (nums[i]+nums[i-1])%M;
}
}
String solve(String[] arr){
int n = Integer.parseInt(arr[0]), m = Integer.parseInt(arr[1]);
int i;
StringBuilder s = new StringBuilder();
int rev = 0, front = 0;
for(i = 0 ; i<m;i++){
if ((i%2)==0){
s.append(nums[front]);
front++;
} else {
s.append(nums[n - rev-1]);
rev++;
}
s.append(" ");
}
return s.toString().trim();
}
}