Editorial for COCI '12 Contest 4 #5 Dlakavac
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us present infected people in one day as an object which has a defined operator
We can think of a day as an array of
Let us take a look at the solution for day 3:
Here we add an operator of exponentiation as a shortened writing of consecutive multiplication. Let us take a look at the properties of this operator.
This is obviously right because we have defined exponentiation as shorthand for consecutive multiplication.
This relation is also true for our operator
The algorithm:
power(B, k) =
if k is 0,
return {0, 1, 0, 0, ...}
if k is even,
half = power(B, k / 2)
return half * half
if k is odd,
return power(B, k - 1) * B
If
Comments