All submissions for this problem are available.
Today is the Robolympics athletic event. N batons numbered 0 to N - 1 are placed in a circular fashion where baton numbers increase in clockwise direction. Also, some of the batons are special. M robots start in the event by standing near a baton position and picking it up. Note that a baton cannot be held by more than one robot, therefore all robots have distinct positions in the circular array of batons.
Now, this event lasts for N seconds. In each second, each robot drops the baton currently in its hand and moves to next position in clockwise direction i.e. if a robot has baton i in its hand at t = 0, at t = 1 he will be holding baton (i + 1) % N.
Crowd goes berserk whenever there comes a moment when all robots have picked up special batons. Your aim is to count how many times it will happen during the whole race. Note that crowd can go berserk even at t = 0. But since race is over at t = N, crowd doesn't care anymore. e. The crowd will not go berserk at t = N.
First line contains N and M denoting the number of batons and number of robots participating in the event. Next line contains N space separated integers where ith integer is 0 or 1 denoting whether baton numbered i - 1 is special or not. Next line contains M integers denoting the index(0 to N-1) of initial baton that robots have picked up.
Output one and only integer denoting the required answer.
- 1 ≤ N ≤ 5*105
- 1 ≤ M ≤ N
Input 1: 3 1 1 0 1 0 Output 1: 2Input 2: 4 2 1 0 1 0 1 3 Output 2: 2
Example input 1.
Batons numbered 0 and 2 are special. Batons held by robots at t = 0:  Batons held by robots at t = 1:  Batons held by robots at t = 2:  Note that at t = 0, 2 all robots have special batons held.
Example input 2.
Batons numbered 0 and 2 are special. Batons held by robots at t = 0: [1, 3] Batons held by robots at t = 1: [2, 0] Batons held by robots at t = 2: [3, 1] Batons held by robots at t = 3: [0, 2] Note that at t = 1, 3 all robots have special batons held.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.