This is a post describing my solution for 617B - Шоколад.
For this problem, the key is to view the act of breaking the candy bar as a sequential decision process. In a sequential decision process, we have a number of choices to choose from at each stage. Once we know how many possible choices each stage has, we can apply the rule of product and multiply these numbers to arrive at the total number of possible outcomes.
The candy bar-breaking sequential decision process proceeds as follows:
- Start at the left side of the candy bar
- Keep marching until we get between two nuts
- Make a break somewhere between these two nuts
- Go back to step 2
In step 3, there are several legal break points. If there are n zeros between the two nuts, then we can make a break so as to give 0 zeros to the left nut and n zeros to the right nut, or we can make a break so as to give 1 zeros to the left nut and n-1 zeros to the right nut, and so on. In total, we have n+1 decisions for this particular break.
To help visualize this process, consider the sequential decision making process described above on the sequence 10101:
We first consider nuts 1 and 2 and see that there is only one zero in between them. Hence we can make a total of 2 different breaks, as pictured by the two branches. After making this first break, we proceed to nuts 2 and 3. Once again, there is only a single zero between these two nuts, hence the number of breaks we can make here is 2. Notice the rightmost column enumerates all possible breaks, which is computed by multiplying these numbers for a total of 2*2 = 4 possible breaks.
One edge case that is useful to consider is when there are leading and/or trailing zeros. Note that for each of these cases there is only one legal break we can make among these regions of zeros. To see why this is the case, consider the case of leading zeros; the only legal break point is before the first zero as any other break would result in a piece of chocolate with zero nuts. The same holds for trailing zeros, except the only legal break is after the last zero. Since the number of possible breaks in both of these cases is 1 and multiplication by 1 has no effect on the final answer, I simply stripped leading and trailing zeros instead of explicitly coding for these special cases.
