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