Editorialist : Sudheera Y S
Problem link : https://www.iarcs.org.in/inoi/2010/zio2010/zio2010-qpaper.pdf
Prerequisites : Logical thinking
Problem Statement :
f(n) = 1 if n = 4
= 3f( ( (2n + 2) mod 11 ) - 1 ) otherwise
g(n) = y mod 10 where
y = 1 if n = 0
= g(n-1) + f( g(n-1) ) + f(n-1) + h(n-1) otherwise
h(n) = x mod 10 where
x = 1 if n = 0
= 2* h(n-1) + g(n-1) + q( f(n-1) mod 10 ) otherwise
q(n) = 1 if n = 7
= f(n) + q(3*n mod 10 ) otherwise
Idea :
We can observe that the function which is easiest to find values is the function f(x) as it only depends on itself and to calculate the value of any function we need to use f(n) β¦β¦β¦ we can find function g(n) and h(n) simultaneously and then if we need to find q(n) then we will find it using f(n) and q(n)
We will start filling the table and then we can compute our answers easily
We will find the values of f(n) only till 7 as we need to find the first 7 values of g and h
f(n) β
f(4) = 1 β¦ base case
We need to calculate f(n) using f(4)
So β¦ 4 = (2n+2) mod 11 - 1 β 5 = (2n+2) mod 11 β n = 7
f(7) = 3*f(4) = 3 β f(7) = 3
We need to calculate f(n) using f(7)
So β¦ 7 = (2n+2) mod 11 - 1 β 8 = (2n+2) mod 11 β n = 3
f(3) = 3*f(7) = 9 β f(3) = 9
We need to calculate f(n) using f(3)
So β¦ 3 = (2n+2) mod 11 - 1 β 4 = (2n+2) mod 11 β n = 1
f(1) = 3*f(3) = 27 β f(1) = 27
We need to calculate f(n) using f(1)
So β¦ 1 = (2n+2) mod 11 - 1 β 2 = (2n+2) mod 11 β n = 0
f(0) = 3*f(1) = 81 β f(0) = 81
We need to calculate f(n) using f(0)
So β¦ 0 = (2n+2) mod 11 - 1 β 1 = (2n+2) mod 11 β n = 5
f(5) = 3*f(0) = 243 β f(5) = 243
We need to calculate f(n) using f(5)
So β¦ 5 = (2n+2) mod 11 - 1 β 6 = (2n+2) mod 11 β n = 2
f(2) = 3*f(5) = 729 β f(2) = 729
We need to calculate f(n) using f(2)
So β¦ 2 = (2n+2) mod 11 - 1 β 3 = (2n+2) mod 11 β n = 6
f(6) = 3*f(2) = 2187 β f(6) = 2187
So here we have calculated all the values of f(n) till 7.
Now let us proceed and calculate g(n) and h(n)
g(n) β
h(n) β
g(0) = 1 β¦. Base case
h(0) = 1 β¦. Base case
We need to do g(n) and h(n) simultaneously
g(1) = (g(0) + f(1) + f(0) + h(0)) %10 = (110)%10 = 0
g(n) β
h(1) = (2*h(0) + g(0) + q(1))%10 = (3+q(1))%10
Now we have to calculate q(1) now
q(n) β
To find q(1) we need to find q(3) and to find q(3) we need to find q(9) and to find it we need q(7) which we already know as 1.
So now let us calculate q(9) β¦β¦
q(9) = f(9) + q(7) = f(9) + 1 β¦β¦
We havenβt found f(9) yet So let us calculate f(9) in order to find q(9) β¦
To find f(9) we need to know f(8) and we havenβt found f(8) yet β¦ Let us calculate f(8) β¦
To find f(8) we need to know the value of f(6) which is known β¦ So we can calculate f(8) and f(9)
f(8) = 3*f(6) = 6561
f(9) = 3*f(8) = 19683
Now we can find q(9)
q(9) = f(9) + q(7) = 19683 + 1 = 19684
q(n) β
Now we will find q(3)
q(3) = f(3) + q(9) = 9 + 19684 = 19693
q(n) β
Now we will find q(1)
q(1) = f(1) + q(3) = 27 + 19693 = 19720
q(n) β
Remember ? we did all of this to calculate h(1)
h(1) = (2*h(0) + g(0) + q(1))%10 = (19723)%10 = 3
h(n) β
Now we will continue to find the values of g(n) and h(n) till 7
g(2) = (g(1) + f(0) + f(1) + h(1))%10 = 1
g(n) β
h(2) = (2*h(1) + g(1) + q(7))%10 = 7
h(n) β
g(3) = (g(2) + f(9) + f(2) + h(2))%10 = 4
g(n) β
h(3) = (2*h(2) + g(2) + q(9))%10 = 9
h(n) β
g(4) = (g(3) + f(8) + f(3) + h(3))%10 = 3
g(n) β
h(4) = (2*h(3) + g(3) + q(9))%10 = 6
h(n) β
g(5) = (g(4) + f(3) + f(4) + h(4))%10 = 9
g(n) β
h(5) = (2*h(4) + g(4) + q(1))%10 = 5
h(n) β
g(6) = (g(5) + f(9) + f(5) + h(5))%10 = 0
g(n) β
h(6) = (2*h(5) + g(5) + q(3))%10 = 2
h(n) β
g(7) = (g(6) + f(0) + f(6) + h(6))%10 = 0
g(n) β
Now we have all our answers for all the subtasks , we can stop here
Subtask A :
Find g(4)
Answer : 3
Subtask B :
Find g(7)
Answer : 0
Subtask C :
Find h(6)
Answer : 2
Code in C++ : ZIO 2010 P3 - Pastebin.com
Hope you understood