Chef and math CodeChef Solution

Problem -Chef and math CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Chef and math CodeChef Solution in C++14

#include <bits/stdc++.h> 
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define ll long long
#define int long long
#define dbg(x) cerr<<#x<<" = "<<x<<"\n"

const int N = 43;
vector<int>dp(N, 0);

void f(int idx, vector<int>&arr, vector<map<int, int>>&dp, int k = 0, int sum = 0) {
    if(k > 10) return;
    if(sum > 1e9) return;


    if(idx == arr.size()) {
        dp[k][sum]++;
        return;
    }

    f(idx, arr, dp, k + 1, sum + arr[idx]);
    f(idx + 1, arr, dp, k, sum);
} 

int solve(int idx, int k, int sum) {
    if(k == 0 and sum == 0) return 1;
    if(k <= 0 || sum <= 0 || idx < 0) return 0;

    int cnt = 0;
    if(sum - dp[idx] >= 0 and sum <= k * dp[idx])
        cnt += solve(idx, k - 1, sum - dp[idx]);
    cnt += solve(idx - 1, k, sum);
    return cnt;
}  

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt", "w", stderr);
    # endif
    
    dp[0] = 1; dp[1] = 2;

    for(int i = 2; i < N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    vector<int>set1, set2;
    for(int i = 0; i < N / 2; i++)
        set1.push_back(dp[i]);
    for(int i = N / 2; i < N; i++)
        set2.push_back(dp[i]);

    // debug(set1); debug(set2);

    vector<map<int, int>>dp1(11);
    vector<map<int, int>>dp2(11);


    // f(0, set1, dp1);
    // f(0, set2, dp2);

    int q; cin >> q;

    while(q--) {
        int sum, k; cin >> sum >> k;

        // int cnt = 0LL;
        // for(int i = 0; i <= k; i++) {
        //     for(const auto &[el, fre]: dp1[i]) {
        //         if(el > sum) break;
        //         int req = sum - el;
        //         if(dp2[k - i].count(req))
        //             cnt += fre * dp2[k - i][req];
        //     }
        // }

        // cout << cnt << '\n';

        cout << solve(N - 1, k, sum) << '\n';
    }


    return 0;
}

Chef and math CodeChef Solution in PYTH 3

# cook your dish here
def chefonacci(n):
    f = []
    for val in range(n):
        if(val==0):f.append(1)
        if(val==1):f.append(2)
        if(val>1):f.append(f[val-1] +f[val-2])
    return f

def F(x,k,n):
    if(k>0 and x<k*f[0] and x>=0):return 0
    if(x<0):return 0
    if(K==1):
        for val in f:
            if(val==X):
                return 1
        return 0
    if (k == 0):
        if x == 0:
            return 1
        else:
            return 0
    elif (x == 0 or n == 0):
        return 0
    else:
        total = F(x,k,n-1)
        if x >= f[n-1] and x <= k*f[n-1]:
            total += F(x-f[n-1],k-1,n)
        return total

def compute_answer(X,K):
    return F(X,K,43)

f = chefonacci(44)
Q = int(input())
for case in range(Q):
    X,K = list(map(int,input().split()))
    number = compute_answer(X,K)
    print(number)

Chef and math CodeChef Solution in C

#include<stdio.h>
 
#define MOD 1000000007
 
int count;
 
void calc(int chef[], int n, int sum, int index)
{
	//printf("n=%d sum=%d index=%d count=%d\n",n,sum,index,count);
	if(index<0)
		return;
	if(sum<0)
		return;
	if((long long)chef[index]*n < sum)
		return;
	if(n==0)
	{
		if(sum==0)
			count=(count+1)%MOD;
		return;
	}
	calc(chef,n-1,sum-chef[index],index);
	calc(chef,n,sum,index-1);	
}
 
int main()
{
	int i, q, x, k;
	int chef[43];
	chef[0]=1;
	chef[1]=2;
	for(i=2;i<43;i++)
		chef[i]=chef[i-1]+chef[i-2];
	scanf("%d",&q);
	while(q--)
	{
		count=0;
		scanf("%d%d",&x,&k);
		calc(chef,k,x,42);
		printf("%d\n",count);
	}
	return 0;
}  

Chef and math CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    static long solve(long[] fib,int index, long num, long k){
    if(k == 0 && num == 0){
        return 1;
    }
    if(num <= 0 || k <= 0 || index < 0){
        return 0;
    }
    long count = 0;
        if(num - fib[index] >= 0 && num <= k * fib[index]){
            count += solve(fib,index,num - fib[index],k - 1);
        }
        count += solve(fib, index - 1, num, k); 
    return count;
}
   static long[] fib(int n){
    long[] fib = new long[n];
    long a = 1;
    long b = 2;
    int i = 0; 
    while (n-- > 0){
        long sum = a + b;
        fib[i++] = a;
        a = b;
        b = sum;
    }
    return fib;
   } 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long[] arr = fib(50);
        while(t-- > 0){
            int num = sc.nextInt();
            int k = sc.nextInt();
            System.out.println(solve(arr, 49, num, k));
        }
    }
}

Chef and math CodeChef Solution in PYPY 3

# cook your dish here
chefonacci= [0] * 44
chefonacci[0]=1
chefonacci[1]=2
for i in range(2,44):
    chefonacci[i]= chefonacci[i - 1] + chefonacci[i - 2]

def no_of_ways(x,k,index):
    if k==0:
        if x==0: return 1
        else:return 0
    else:
        if (x==0 or index==0): return 0
        else:
            if (x>=0 and x<=k*chefonacci[index]):
                return no_of_ways(x,k,index-1)+no_of_ways(x - chefonacci[index - 1], k - 1, index)
    return 0

for i in range(int(input())):
    x,k=map(int,input().split())
    # start recursion from index where chefonacci(n) just greater than x
    global index_1
    for i in chefonacci:
        if i>x:
            index_1=chefonacci.index(i)
    # ------------
    print(no_of_ways(x,k,index_1))

Chef and math CodeChef Solution in PYTH

MD = 10**9 +7
CF = [1,2]
v = 3
while v < 10**9:
	CF.append(v)
	v = CF[-1]+CF[-2]
# endwhile
def F(x,k,n):
	if k == 0:
		if x == 0:
			r = 1
		else:
			r = 0
		# endif
	else:
		if (n == 0) or (x <= 0) or (x > k*CF[n-1]):
			r = 0
		else:
			r = F(x,k,n-1) + F(x-CF[n-1],k-1,n)
		# endif
	# endif
	return r%MD
# end fun
t = int(raw_input())
for i in range(t):
	st = raw_input().split()
	X = int(st[0])
	K = int(st[1])
	r = F(X,K,43)
	print r
# endfor i

Chef and math CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace program
{
    class solution
    {
        public static long[] fib = new long[50];
        public static int x, k, K;
        static int LowerBound(long [] arr,int lo,int hi,long val)
        {
            while (lo <= hi)
            {
                int mid = (lo + hi) >> 1;
                if (arr[mid] > val)
                {
                    hi = mid - 1;
                }
                else
                {
                    lo = mid + 1;
                }
            }
            return lo - 1;
        }
        static void precompute()
        {
            fib[1] = 1;
            fib[2] = 2;
            for (int i = 3; i <= 46; i++)
            {
                fib[i] = fib[i - 1] + fib[i - 2];
            }
        }
        static long solve(long x, int k, int i)
        {
            if ((k == K && x == 0) || (K-k == x))
                return 1;
            if (x <= 0 || k >= K || x < K - k)
                return 0;
            long good = 0;
            int index = LowerBound(fib,1,i,x);
            for (int xx = LowerBound(fib, 1, index, x / (K - k)); xx <= index; xx++)
            {
                good += solve(x - fib[xx], k + 1, xx);
            }
            return good;
        }
        static void Main(string[] args)
        {
            precompute();
            int q = int.Parse(Console.ReadLine());
            while (q-- > 0)
            {
                string[] s = Console.ReadLine().Split(' ');
                int.TryParse(s[0], out x);
                int.TryParse(s[1], out K);
                Console.WriteLine(solve(x, 0, LowerBound(fib, 1, 46, x)));
            }
            return;
        }
    }
}

Chef and math CodeChef Solution Review:

In our experience, we suggest you solve this Chef and math CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and math CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Chef and math CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn