GCJ101BB - Picking Up Chicks

no tags 

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 (Xi) at time 0 and natural speeds (Vi) 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, CC test cases follow. Each test case starts with 4 integers on a line -- NKB and T. The next line contains the Ndifferent integers Xi, in increasing order. The line after that contains the N integers Vi. 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 ≤ Xi < B;
1 ≤ Vi ≤ 100;
1 ≤ N ≤ 50;
0 ≤ K ≤ N;

All the Xi'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
sbrutal_0245: 2020-05-27 05:27:48

AC One go!!

crazydoggo18: 2020-04-12 11:06:35

The method used in the editorial gives incorrect answer for the following case:
1
3 1 8 2
0 2 4
8 2 1
Answer should be 1 as we can just swap the last two and the last one would reach within time,
but the editorial method gives 2.

The problem might be incorrect or needs modification.

Last edit: 2020-04-12 11:07:39
fighter_4: 2020-04-09 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.

fighter_4: 2020-04-09 15:52:49

I have checked all the test cases which i could and it is passing all of them, but giving WA upon submission, can anyone please share his/her critical test cases?

spider0061: 2020-04-02 15:01:34

No complicated approach. But loved this question.

wingman__7: 2019-10-03 09:38:28

The main logic is that none of faster chicks will slow down. just calculate their ETA from the barn and calculate the swaps

rishstage1: 2019-08-05 15:39:02

Question statement is somewhat unclear, just assume that at one position ,only one chick can be there, its not like a road.

nadstratosfer: 2019-03-15 21:44:01

Fun problem. Note that the part "it has to slow down" is not true if we're swapping; the whole purpose of swapping is to allow the faster chick to maintain its speed.

kiran577: 2019-03-13 11:10:07

AC in one go!!

rohan_24: 2018-09-05 00:51:00

ACE IN ONE GO


Added by:Mohammad Kotb
Date:2010-05-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: JS-RHINO OBJC SQLITE
Resource:Google Code Jam 2010