Ways to Climb with Broken Steps
JavaScript
Hard
3 views
Problem Description
You have n steps. You can climb 1 or 2 steps. Some steps are broken (cannot land). Count number of ways to reach step n mod 1000000007.
Input Format
Line1: n m. Line2: m broken step numbers.
Output Format
One integer ways mod.
Official Solution
const fs=require('fs');const raw=fs.readFileSync(0,'utf8').trim();if(!raw)process.exit(0);const a=raw.split(/\\s+/);let i=0;const n=Number(a[i++]);const m=Number(a[i++]);let broken=new Uint8Array(n+1);for(let j=0;j<m;j++){const b=Number(a[i++]);if(b>=0&&b<=n)broken[b]=1;}const MOD=1000000007n;let dp0=1n,dp1=0n;for(let step=1;step<=n;step++){let cur=(dp0+dp1)%MOD;if(broken[step])cur=0n;dp0=dp1;dp1=cur;}process.stdout.write(dp1.toString());
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!