Question F and G

Continuing from previous article,

Problem F:- Final Boss

Link:- https://codeforces.com/contest/1985/problem/F

Question:- The problem tells us that we have to defeat a boss with health 'h' and our character has 'n' attacks but every attack has a cooldown of its own. In each turn we can use all the attacks that are not on cooldown. We have to find the no. of turns required to kill the boss.

Approach:- Here, I have used Binary Search on Answer to find the right value required to eliminate in the boss. My upper bound was taken as 1e15 and the lower bound was taken to be 0. Another method ok(vector<int> ,vector<int> ,int ) was taken to verify the success of an attack. This method actually checked the amount of damage that a particular series of attacks with the cooldown in effect. We continue this process until (lower bound + 1)<upper bound.

Comments on the hack:- One thing I realised after the contest was that my pre-conceived notion of selecting any upper bound less that the max value of long long was actually incorrect. I got an idea about this post-contest from Debayan Ghosh and from https://codeforces.com/blog/entry/130381

Problem G:- D-function

Link:- https://codeforces.com/contest/1985/problem/G

Question:- Given, D(n) represents the sum of all digits in the number 'n'. We have to find the no. of integers 'n' where 10?<=n<=10? satisfy D(k.n)=k.D(n). Return the answer module 10? + 7.

Approach:- Now intuitively, if we multiply each digit of n with k, they cannot exceed 9. So, for any value of k>=10[0 to 9] the answer will always be zero. Now for the other cases, we compute ceil(10/k) and store it in 'base'. Then we perform modular exponentiation on base? and base?. The final answer is (base?-base?+MOD)%MOD. Here, MOD equals 10? + 7.

Hope, you people found this helpful.