Back to Problem Solutions forum
Can someone explain me what do I have to do in this task please? In example we have N=4 B=3. Like I understood
it means that we have the ticket with 4 digits and in any digits we can put only 0-2 digit because base is 3?
My recursive take a lot of time, how I can optimize it?
Yeah, you are right. With N = 4 and B = 3 you have 4 digits in range 0..2.
And lucky tickets for this input are:
0000
0101
0110
1001
1010
0202
0211
0220
1102
1111
1120
2002
2011
2020
1212
1221
2112
2121
2222
(19 tickets in total)
Sadly, I don't remember the algorithm I used to solve this task. Gotta investigate my source code for this task with pencil and paper and find out what the hell I was doing in my program :).
Wrote a lengthy description of my algorithm, and suddenly the light turned off. Sigh.
To be very short:
F(2k + 1) = B * F(2k)
F(2k) = P(C(k))
And I'm not going to write a description for P() and C(k) second time.
Time complexity of my algorithm is very bad, it is: O(math.power(B, math.floor(N / 2))).
Okay, I did it, thank you)