Problem Link:
Author: Niket Agarwal
Tester: Pritish Priyatosh Nayak
Editorialist: Niket Agawal
Difficulty:
Easy
Prerequisites:
Dynamic Programming
Problem:
Find the number of elements on the n-th day such that there is one element on day 1 and the elements double themselves everyday after k-days.
Explanation:
This has a linear DP solution with a relation of
dp[i]=dp[i-1]+dp[i-k]
where, the (i-1)-th element represent that all the elements from the previous day are carried over,
the (i-k)-th element represents the number of elements that will double on i-th day.
Remember to use the modulus operator in the right places.
Fun Fact: For K=2, this turns into finding the N-th fibonacci number
Solutions:
Setter's/Editorialist's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
int k=ni();
long[]dp=new long[n+1];
dp[1]=1l;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1];
if(i>k)
dp[i]=(dp[i]+dp[i-k])%mod;
}
pn(dp[n]);
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj = true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static long mod=(long)1e9+7l;
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
#define asserti(x,l,r) assert( (x) >= (l) && (x) <= (r))
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pair<int,int>>;
constexpr int mod = 1000000007;
constexpr int N = 2e8 + 5;
constexpr int inf = 1e18 , eps = 1e-6;
void Onigiri()
{
int n,k;
cin>>n>>k;
asserti(n,2,100000);
asserti(k,2,100000);
int dp[n];
rep(i,0,n)
if(i>=k)dp[i]=(dp[i-1]+dp[i-k])%mod;
else dp[i]=1;
cout<<dp[n-1];
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t=1;
cin>>t;
asserti(t,1,10);
while(t--)
{Onigiri();cout<<"\n";}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}