Light OJ - 1105 - Fi Binary Number Tutorial

 Problem Description here

Problem: এই প্রব্লেমে আমাকে nth Fi Binary Number বের করতে হবে। Fi Binary Number হচ্ছে এমন একটি নাম্বার যা শুধু 0 এবং 1 নিয়ে গঠিত এবং সেই নাম্বারে পাশাপাশি দুটি 1 থাকতে পারবে না। কয়েকটি Fi Binary Number হচ্ছেঃ

 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101

Solution: 

১) ভালো করে লক্ষ্য করলে দেখবে যে Fi Binary Number এ

    ১ ডিজিট এর সংখ্যা আছে ১ টি

    ২ ডিজিট এর সংখ্যা আছে ১ টি

    ৩ ডিজিট এর সংখ্যা আছে ২ টি

    ৪ ডিজিট এর সংখ্যা আছে ৩ টি

    ৫ ডিজিট এর সংখ্যা আছে ৫ টি

তার মানে, আমরা একটি ফিবোনাচি সিরিজ পাচ্ছি!!!

২) এখন, আমি চাইলে এমন একটি ফাংশন লিখতে পারি যাকে আমি n প্যারামিটার হিসেবে দিলে সে আমাকে বলে দিবে nth নাম্বার টি কত ডিজিটের নাম্বার এবং ততো ডিজিটের কত তম নাম্বার এটি। অর্থাৎ, আমি যদি n = 12 দিয়ে ফাংশন কে কল দেই, তাহলে সে আমাকে বলবে যে nth নাম্বার টি ৫ টি ডিজিট নিয়ে গঠিত এবং ৫ডিজিটসমৃদ্ধ নাম্বার এর মধ্যে এটি ৫ম।

৩) এবার কতগুলো Fi Binary Number নিয়ে ঘাটাঘাটি করলে দেখবে যে একটি Fi Binary Number অনেকগুলো Fi Binary Number এর সমন্বয়ে তৈরী করা হয় যদি না এটি ততো ডিজিট সমৃদ্ধ ১ম সংখ্যা হয়! (মাথার উপর দিয়ে গেলে কয়েকবার পড় এবং খাতায়, মাথায় চিন্তা কর) 

তার মানে আমরা এমন একটি রিকার্সিভ ফাংশন লিখতে পারি যে অনেকগুলো ছোট ছোট Fi Binary Number নিয়ে আমাকে একটি বড় Fi Binary Number তৈরী করে দিবে।

আশা করি, যথেষ্ট চিন্তা করলে রিকার্সিভ ফাংশনটি নিজেই লিখতে পারবে। তাও না পারলে নিচের কোড দেখতে পারোঃ

	#include<bits/stdc++.h>
	#define ll long long int
	#define pii pair<int,int>
	#define sc scanf
	#define scin(x) sc("%d",&(x))
	#define pf printf
	#define ms(a,b) memset(a,b,sizeof(a))
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	ll fib[50],fibsum[50];
	void FuN()
	{
	fib[1] = 1;
	fibsum[1] = fib[1];
	fib[2] = 1;
	fibsum[2] = fibsum[1]+fib[2];
	for(int i=3 ; ; i++){
	fib[i] = fib[i-1] + fib[i-2];
	fibsum[i] = fibsum[i-1] + fib[i];
	if(fibsum[i] >= 1e9){
	break;
	}
	}
	}
	pii findOut(ll n)
	{
	pii ret;
	for(ll i=1 ; i<=50 ; i++){
	if(fibsum[i] >= n){
	int digit = i;
	int kth = n-fibsum[i-1];
	ret = {digit , kth};
	break;
	}
	}
	return ret;
	}
	void haveFuN(ll digit,ll kth)
	{
	if(digit <= 0)
	return;
	if(kth == 1){
	pf("1");
	for(ll i=2 ; i<=digit ; i++)
	pf("0");
	pf("\n");
	return;
	}
	pf("1");
	pii pr = findOut(kth-1);
	ll faka = digit-1-pr.first;
	for(ll i=1 ; i<=faka ; i++)
	pf("0");
	haveFuN(pr.first , pr.second);
	}
	void Solve(int t)
	{
	int i,j,k,n,kth,digit;
	scin(n);
	pii pr = findOut(n);
	digit = pr.first;
	kth = pr.second;
	pf("Case %d: ",t);
	haveFuN(digit , kth);
	}
	int main()
	{
	FuN();
	int t,T;
	scin(T);
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw LOJ - 1105.cpp hosted with ❤ by GitHub

Happy Coding 😊