cho.sh병아리 들어 올리기 (작은 입력)
병아리들의 위치와 속도가 주어질 때 인접 교환으로 K마리 이상을 시각 T 안에 헛간에 도착시킵니다.
보통5그리디수학아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제
병아리 떼가 좁고 곧은 길을 따라 동쪽으로 달린다. 병아리마다 고유한 속도가 있고 그 속도는 변하지 않는다. 뒤에 있던 병아리가 바로 앞 병아리를 따라잡으면 속도를 줄여 앞 병아리와 같은 속도로 따라간다. 당신은 병아리 떼 뒤에서 이동식 크레인을 몰며 길 끝의 헛간 쪽으로 병아리를 몬다.
크레인 팔로 병아리 한 마리를 잠깐 들어 올리고, 바로 뒤 병아리를 그 아래로 지나가게 한 다음, 들어 올린 병아리를 다시 내려놓을 수 있다. 이 동작에는 시간이 전혀 걸리지 않는다. 또 줄에서 바로 이웃한 두 마리에게만 쓸 수 있고, 세 마리 이상이 한 줄로 붙어 있어도 마찬가지다.
시각 0에서 병아리 N마리의 위치 Xi와 고유 속도 Vi, 헛간의 위치 B가 주어진다. N마리 중 K마리 이상이 시각 T까지 헛간에 도착하게 하려면 자리를 바꾸는 횟수가 최소 몇 번이어야 하는지 구하라.
병아리는 직선 위를 움직이는 점으로 본다. 세 마리 이상이 같은 위치에 겹쳐 있어도 한 마리를 들어 올리면 나머지 두 마리 중 한 마리만 지나갈 수 있다. 자리 바꾸기는 순간에 끝나므로 같은 시각에 여러 번 해도 되지만, 한 번마다 따로 센다.
입력
첫 줄에 테스트 케이스의 수 C가 주어진다.
각 테스트 케이스의 첫 줄에는 정수 N, K, B, T가 공백으로 구분되어 주어진다. 다음 줄에는 서로 다른 정수 Xi가 증가하는 순서로 N개 주어진다. 그다음 줄에는 정수 Vi가 N개 주어진다.
거리의 단위는 미터, 속도의 단위는 초당 미터, 시간의 단위는 초다.
제한
- 1≤C≤100
- 1≤N≤10
- 0≤K≤min(3,N)
- 1≤B≤109
- 1≤T≤1000
- 0≤Xi<B
- 1≤Vi≤100
- Xi는 서로 다르며 증가하는 순서로 주어진다.
출력
각 테스트 케이스마다 Case #x: S 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, S는 필요한 자리 바꾸기의 최소 횟수다.
어떻게 바꾸어도 시각 T까지 헛간에 도착하는 병아리를 K마리 이상 만들 수 없으면 S 자리에 IMPOSSIBLE을 출력한다.