Note to plugin users: there are html elements in this statement that will not appear correct in plugins. Please use the statement to view them.
Russian Nesting Dolls are a set of dolls which nest inside each other. The dolls are constructed in such a way that each doll will fit comfortably inside any larger doll, and no two dolls are the same size. There are a finite number of ways to nest dolls inside one another so that a specific subset of the dolls is visible. For example, with 3 dolls, there is only one way that they could be nested such that only the largest doll is visible, but there are 2 ways to nest the dolls if the largest and medium doll are visible (depending on which of the two larger dolls the smallest doll is inside). In addition, if you are just given how many dolls are visible, there may be even more ways that the dolls could be nested. For example, if you know there are 2 dolls visible in a 3-doll set, there are 3 ways they could be nested (see example 0).
Your clever friend has used an entire set of N nesting dolls in an arrangement on a table. He assures you that all the nesting dolls are on the table, but you can only see a subset of the dolls. In addition, he has placed a piece of cardboard in front of some of the dolls so that you cannot see which ones they are, and he tells you how many are behind the board. He asks you how many possible ways he could have arranged the dolls such that the current configuration is on the table.
Each doll has a number painted on it from 1 to N, which identifies the size of the doll. You can fit a doll labeled i inside a doll labeled j as long as i < j. Your program will be given an int N, identifying how many dolls there are in the set, a int[] visible, identifying which dolls you can see on the table, and an int hidden, identifying how many more dolls would be visible if the board was removed. Two arrangements are different if any doll is nested immediately inside a different doll, or is nested in one arrangement but not in the other.
|