Page Contents
Pyramid Traversal PYRAMIDMOVES Solution
You are given a pyramid of the following form with an infinite number of rows:
1
2 3
4 5 6
7 8 9 10
………………….
From a cell, you can move to either the bottom-left cell or the bottom-right cell directly in contact with the current one (For example, you can make the following moves: 1→2,1→3,6→9,6→101→2,1→3,6→9,6→10, while you cannot make moves 2→62→6 or 2→72→7).
You are given a starting cell ss and an ending cell ee. Starting at cell ss, find the number of ways to reach cell ee. This number can be large, so print the answer modulo 109+7109+7.
Two ways are said to be different if there exists at least one cell which was visited in one of the ways but not the other one.
Input Format
- The first line of input contains a single integer TT, the number of test cases. The description of TT test cases follows.
- The first and only line of each test case contains two space-separated integers ss and ee, denoting the starting and the ending cell respectively.
Output Format
For each test case, output a single line containing one integer: the number of ways to go from ss to ee modulo 109+7109+7.
Constraints
- 1≤T≤10001≤T≤1000
- 1≤s,e≤1091≤s,e≤109
Subtasks
Subtask 1(100 points): Original constraints
Sample Input 1
3 2 7 1 5 5 3
Sample Output 1
1 2 0
Explanation
In the first test case, there exists only 11 way to move from 22 to 77, which is:
- 2→4→72→4→7
In the second test case, there exist 22 ways to move from 11 to 55, which are:
- 1→2→51→2→5
- 1→3→51→3→5
In the third test case, it is not possible to move from 55 to 33.
SOLUTION
Program Python: Pyramid Traversal PYRAMIDMOVES Solution in Python
def ncr(n, r, p): # initialize numerator # and denominator num = den = 1 for i in range(r): num = (num * (n - i)) % p den = (den * (i + 1)) % p return (num * pow(den, p - 2, p)) % p def getcoord(num): y=int((2*num+0.25)**0.5+0.5) x=int(num-(y*(y-1))/2) if x==0: y-=1 x=y return (x,y) T=int(input()) for i in range(T): (s,e)=map(int,input().split()) E=getcoord(e) S=getcoord(s) n=E[1]-S[1] r=E[0]-S[0] if n<1 or r<0 or n<r: print(0) else : print(ncr(n, r, 10**9 +7))
Program C++: Pyramid Traversal PYRAMIDMOVES Solution in C++
#include <iostream> #include<cmath> using namespace std; typedef long long int lli; typedef long long ll; const lli mod7 = 1e9 + 7; const int MAXF = 1e5; lli fact [MAXF + 1]; lli last_elem(lli lvl) { return ((lvl + 1)*lvl) / 2; } ll powmod(ll a, ll b, ll p){ a %= p; if (a == 0) return 0; ll product = 1; while(b > 0){ if (b&1){ // you can also use b % 2 == 1 product *= a; product %= p; --b; } a *= a; a %= p; b /= 2; // you can also use b >> 1 } return product; } ll inv(ll a, ll p){ return powmod(a, p - 2, p); } ll nCk(ll n, ll k, ll p){ return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p; } pair<lli,lli> get_lvl_idx(lli n) { lli lvl =-1; lli idx = -1; if(n==1) { return {1,1}; } lli st=2; lli end = 1LL + ceil(sqrt(2*n)); while(st<=end) { lvl= (st+end)/2; if(last_elem(lvl)>=n && last_elem(lvl-1)<n) { break; } else if(last_elem(lvl)>n) { end = lvl - 1; } else { st = lvl + 1; } } idx = n - (lvl*(lvl-1))/2; return {lvl,idx}; } int main() { // your code goes here fact[0]=1; fact[1]=1; for(int i=2;i<=MAXF;i++) { fact[i] = fact[i-1]*i % mod7; } int t; cin>>t; while(t--) { lli s,e; cin>>s>>e; pair<lli, lli> res1, res2; res1 = get_lvl_idx(s); res2 = get_lvl_idx(e); lli slvl = res1.first; lli sidx = res1.second; lli elvl = res2.first; lli eidx = res2.second; lli L = elvl - slvl; lli K = eidx - sidx; lli ans = -1; if(L<=0 || K<0 || K>L) { ans=0; } else { ans = nCk(L,K,mod7); } cout<<ans<<endl; } return 0; }
December Long Challenge 2021 Solution
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef