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→10, while you cannot make moves 2→6 or 2→7).
You are given a starting cell s and an ending cell e. Starting at cell s, find the number of ways to reach cell e. This number can be large, so print the answer modulo 109+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 T, the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two space-separated integers s and e, 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 s to ee modulo 109+7.
Constraints
- 1≤T≤1000
- 1≤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 1 way to move from 2 to 7, which is:
- 2→4→7
In the second test case, there exist 2 ways to move from 1 to 5, which are:
- 1→2→5
- 1→3→5
In the third test case, it is not possible to move from 5 to 3.
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