GCJ101BB  Picking Up Chicks
A flock of chickens are running east along a straight, narrow road. Each one is running with its own constant speed. Whenever a chick catches up to the one in front of it, it has to slow down and follow at the speed of the other chick. You are in a mobile crane behind the flock, chasing the chicks towards the barn at the end of the road. The arm of the crane allows you to pick up any chick momentarily, let the chick behind it pass underneath and place the picked up chick back down. This operation takes no time and can only be performed on a pair of chicks that are immediately next to each other, even if 3 or more chicks are in a row, one after the other.
Given the initial locations (X_{i}) at time 0 and natural speeds (V_{i}) of the chicks, as well as the location of the barn (B), what is the minimum number of swaps you need to perform with your crane in order to have at least K of the N chicks arrive at the barn no later than time T?
You may think of the chicks as points moving along a line. Even if 3 or more chicks are at the same location, next to each other, picking up one of them will only let one of the other two pass through. Any swap is instantaneous, which means that you may perform multiple swaps at the same time, but each one will count as a separate swap.
Input
The first line of the input gives the number of test cases, C. C test cases follow. Each test case starts with 4 integers on a line  N, K, B and T. The next line contains the Ndifferent integers X_{i}, in increasing order. The line after that contains the N integers V_{i}. All distances are in meters; all speeds are in meters per second; all times are in seconds.
Output
For each test case, output one line containing "Case #x: S", where x is the case number (starting from 1) and S is the smallest number of required swaps, or the word "IMPOSSIBLE".
Limits
1 ≤ C ≤ 100;
1 ≤ B ≤ 1,000,000,000;
1 ≤ T ≤ 1,000;
0 ≤ X_{i} < B;
1 ≤ V_{i} ≤ 100;
1 ≤ N ≤ 50;
0 ≤ K ≤ N;
All the X_{i}'s will be distinct and in increasing order.
Example
Input: 3
5 3 10 5
0 2 5 6 7
1 1 1 1 4
5 3 10 5
0 2 3 5 7
2 1 1 1 4
5 3 10 5
0 2 3 4 7
2 1 1 1 4 Output: Case #1: 0
Case #2: 2
Case #3: IMPOSSIBLE
hide comments
rohan920s:
20230718 15:49:45
if Your solution is giving wrong ans even after 5 tastcases then you should print your ans like Case #1: 0


cryptosilicon:
20230223 15:09:36
If you get wrong answer after running all test cases, then staring printing from {Case #1:} not from {Case #0:} 

yashbansal01:
20220205 12:33:21
I am getting wrong answer on submission though sample test case is passing. What could be the reason. Please help!


umang0206:
20210810 19:28:29
it is very waste site


immortal2211:
20210726 06:26:32
Loved the question, although nothing complicated things were there 

rachit_agr:
20210328 15:38:21
Anyone getting wrong ans at test case 6?


deepakkumar01:
20210206 08:37:13
I am new at SPOJ , I see may problem that have very simple answer but the problem statment is totally frustrated .......... , 

sbrutal_0245:
20200527 05:27:48
AC One go!! 

crazydoggo18:
20200412 11:06:35
The method used in the editorial gives incorrect answer for the following case:


fighter_4:
20200409 16:04:28
Beware guys when you find time taken by specific chicken to reach barn, it will be the nearest integer, so use float instead. 
Added by:  Mohammad Kotb 
Date:  20100525 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: JSRHINO OBJC SQLITE 
Resource:  Google Code Jam 2010 