Code From Class 2026/04/29

Recursive solution

#include<iostream>
long GLOBAL_counter=0;
long countLucky(long n, long k, long l){
    ++GLOBAL_counter;
    if(n==1){return 1;}
    long total=0;
    for(long i=1;i<=k;++i){
        if( !( (i==1) && (l==3)  ) ){
            total += countLucky(n-1,k,i);
        }
    }
    return total;
}
int main(){
    long n,k; std::cin>>n>>k;
    std::cout<<countLucky(n+1,k,0)<<"\n";
    std::cout<<"Total number of recursive calls was "<<GLOBAL_counter<<"\n";

    return 0;
}

Memoization

#include<iostream>
#include "ssm.cpp"
class Memo{
    public:
    long n; long l;
    long numLucky;
    int operator<(const Memo& ) const;
};
int Memo::operator<(const Memo& b) const{
    if(n<b.n){return 1;}
    if(n>b.n){return 0;}
    if(l<b.l){return 1;}
    return 0;
}
long GL_counter=0;
long countLucky(ssm::set<Memo>& knowledge, long n, long k, long l){
    ++GL_counter;
    if(n==1){return 1;}
    Memo temp;
    temp.n=n ; temp.l=l;
    long index=knowledge.find(temp);
    if(index!=-1){return (knowledge[index]).numLucky;}
    long total=0;
    for(long i=1;i<=k;++i){
        if(!( (i==1) && (l==3) ) ){
            total+=countLucky(knowledge, n-1,k,i);
        }
    }
    temp.numLucky=total;knowledge.insert(temp);
    return total;
}
int main(){
    ssm::set<Memo> kn;
    long n,k;
    std::cin>>n>>k;
    std::cout<<countLucky(kn,n+1,k,0)<<"\n";
    std::cout<<"Total number of recursive calls was "<<GL_counter<<"\n";
    return 0;
}