Chef vs Bharat Codechef Solution

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’s will be post with explanation. Join Us on Telegram for update

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

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment

error: Content is protected !!
Please Click on 1 or 2 Ads to help us run this site.