Although Oskol is not really name of a specie of birds, In Iran it's known as a kind of bird which is very forgetful and can't even remember his way back to home when he flies away! It's commonly used instead of the word "stupid" among the kids! :D
In this problem you just have to now how many birds are there on each wire after each shot. A good trick for the first and the last wire would be to define wires 0 and n + 1. In this way the birds that fly away sit on these wires and you don't need to worry about accessing some element outside the range of your array.
As said in the statement, the thickness of each book is either 1 or 2. Think about when we want to arrange v1 books of thickness 1 and v2 books of thickness 2 vertically and arrange all other n - v1 - v2 books horizontally above them to achieve a configuration with total thickness of vertical books equal to v1 + 2v2. Is it possible to find such arrangement? Because the total thickness of vertical books is fixed it's good to calculate the minimum possible total width of horizontal books. As the width of a book doesn't matter in vertical arrangement it's good to use the books with shorter width horizontally and the ones with longer width vertically. So pick out v1 books with longest width among books of thickness 1 and do the same with books of thickness 2. The sum of width of n - v1 - v2 remaining books should be at most v1 + 2v2.
The solution would be to try the things we explained above for all possible values of v1 and v2. And print the best answer. :)
There exists other ways to solve this problem mostly using dynamic programming but this was the intended solution of the problem.
I just want to solve the third sample of this problem for you and you can figure out the rest by yourself. :)
The third sample is
# is a switched on lamp and
. is a switched off lamp. As you can see we have three different types of lights. The first three lights (Type A), the 5th to 8th lights (Type B) and the last three lights (Type C). We have to switch on the lights three times for each type of lights. Aside from the order of moves for each type there are possible permutations of the string AAABBBCCC which tells us how to combine the steps of different types. Switching on the lights is done uniquely for types 1 and 3. But for type 2 each time we have to possible options until we're left with one off light. So there are 23 - 1 ways to do this. So the answer would be
1680*1*4*1 = 6720.
The general solution would be to find all groups off consecutive switched off lamps and calculate the number of ways to combine all these groups. Then for each group you should calculate in how many ways it can be solved.
The implementation needs some standard combinatorial computations which you can see here: 3485187
I promise the editorial will be completed come soon soon soon! :)