The Great Circus
All submissions for this problem are available.
The Great Circus has come to Pilani. It is an amazing circus with lots of funny clowns, daredevil stuntsmen, magicians, performers and amazing animals. But with all this success comes a lot of workload. Thus the circus-master has decided to hire you as an assistant to help him with all the different problems he will face.
The circus is being setup in the Pilani. The fences have been setup by the elephants. Now the circus-master has allocated the job of painting the whole fence to the head clown.
The unpainted fence has N planks. The planks are numbered from 1 to N. The circus-master has given the clown C buckets of paint, each of a different color. The colors are numbered from 1 to C. Since the clown is fat and lazy, he just wants to lie down outside and enjoy the sun. So he instead orders M monkeys to do his job.
The monkeys make a line and take turns painting the fence. In each turn, the painter monkey randomly chooses a non-empty segment of the fence (a segment is a contiguous sequence of planks of the fence) and paints all planks in that segment with his/her favorite color. The random choice is made in such a way that the probability of selecting any non-empty segment is the same.
Now the clown wonders how the fence will look like after the monkeys finish painting it. He already knows the order in which monkeys will paint and he knows each monkey's favorite color. Since he knows that you are a good assistant, he asks for your help. He will shout out to you Q times . Each time he will tell you a color and the plank numbers of the start and end of a segment. You have to tell him the expected number of planks which have that color in that segment.
The first line of each test case contains 3 integers N, C and M (number of planks, number of colors and number of monkeys respectively).
The next line contains M space-separated integers. The ith integer is the favorite color of the ith painter.
The next line contains a single integer Q, the number of times the circus-master shouted out to you.
The next Q lines contain 3 space-separated integers each, the first and last plank numbers of a segment and a color.
For each of the Q shout outs to you, output the expected number of planks in that segment with that color.
Answer should have relative and absolute accuracy of at least 10-6.
1 ≤ N,M,C ≤ 100
1 ≤ Q ≤ 200000
2 1 1 1 1 1 2 1
There are 2 planks. There are 3 segments (the left plank, the right plank, both planks). We have to find out the expected number of painted segments (there is just one color in this test case and the given segment covers the whole fence). That is equal to the sum of number of painted planks multiplied by the probability of having that many painted planks.
Let f(i) = Probability that i planks are painted = (number of segments of length i)/(total number of segments)
f(1) = 2/3, f(2) = 1/3
Result = 1*f(1) + 2*f(2) = 2/3 + 2/3 = 4/3 = 1.33333...
Fast IO required
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, RUBY, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.