Contents
Chef vs Bharat Codechef Solution
Chef and his friend Bharat have decided to play the game “The Chefora Spell”.
In the game, a positive integer NN (in decimal system) is considered a “Chefora” if the number of digits dd is odd and it satisfies the equation
N=∑i=0d−1Ni⋅10i,N=∑i=0d−1Ni⋅10i,
where NiNi is the ii-th digit of NN from the left in 00-based indexing.
Let AiAi denote the ii-th largest Chefora number.
They’ll ask each other QQ questions, where each question contains two integers LL and RR. The opponent then has to answer with(∏i=L+1R(AL)Ai)mod109+7.(∏i=L+1R(AL)Ai)mod109+7.
Bharat has answered all the questions right, and now it is Chef’s turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!
See Also : July Long Challenge 2021 Solutions Codechef
Input
- The first line contains an integer QQ – the number of questions Bharat asks.
- Each of the next QQ lines contains two integers LL and RR.
Output
Print QQ integers – the answers to the questions on separate lines.
Constraints
- 1≤N,Q≤1051≤N,Q≤105
- 1≤L<R≤N1≤L<R≤N
Subtasks
Subtask #1 (30 points): 1≤N,Q≤5⋅1031≤N,Q≤5⋅103
Subtask #2 (70 points): Original constraints
Sample Input
2
1 2
9 11
Sample Output
1
541416750
Explanation
- For the first question:(A1)A2=12=1.(A1)A2=12=1.
- For the second question:(A9)A10⋅(A9)A11=9101⋅9111≡541416750(mod109+7).
Solution
Program Python:
Credit : here
class palinpsum:
def __init__(self, n):
self.n = n
self.i = 0
self.palindromes = [0]*n
self.prefixSums = [0]*n
def add(self, val):
self.palindromes[self.i] = val
self.prefixSums[self.i] = val
if self.i != 0:
self.prefixSums[self.i] += self.prefixSums[self.i-1]
self.i = self.i+1
def isFull(self):
return self.i == self.n
def prefixsum(self, L, R):
return self.prefixSums[R]-self.prefixSums[L]
def getFirstPalin(self, index):
return self.palindromes[index]
def oddpalin(inp):
n = inp
palin = inp
n = n//10
while n > 0:
palin = palin*10+(n%10)
n = n//10
return palin;
def gpalin(palinpsum):
i = 1
while not palinpsum.isFull():
palinpsum.add(oddpalin(i))
i = i+1
def formula(L, R, palinpsum):
power = palinpsum.prefixsum(L-1, R-1);
base = palinpsum.getFirstPalin(L-1);
return pow(base, power, 1000000007);
palinpsum = palinpsum(100001)
gpalin(palinpsum)
q = int(input())
while q > 0:
q = q-1
L,R=map(int,input().split())
print(formula(L, R, palinpsum))Program Python:
Credit: here
def findpower(base,power):
mod = 10**9+7
res = 1
while power!=0:
if power%2==0:
base = ((base%mod)*(base%mod))%mod
power = power//2
else:
res = ((res%mod)*(base%mod))%mod
power = power-1
return res
def findshefola(num):
palin = num
num = num//10
while num>0:
palin = palin*10+num%10
num = num//10
return palin
arr = [0]*(10**5+1)
arrsm = [0]*(10**5+1)
for i in range(1,10**5+1):
arr[i] = findshefola(i)
arrsm[i] = arrsm[i-1] + arr[i]
for _ in range(int(input())):
l,r = map(int,input().split())
power = arrsm[r]-arrsm[l]
print(findpower(arr[l],power))July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
