페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10372
채점 보류

초대형 팬케이크 절단기 20s 1024MB

문제

당신은 Infinite House of Pancakes의 수석 셰프로 출근했는데, 여느 때처럼 진행 중인 재난을 발견했다! 다른 셰프들이 실수로 모두 같은 크기의 거대한 원형 팬케이크를 몇 장이나 만들어 버렸다. 이 팬케이크들은 통째로 내기에는 너무 커서, 이미 조각(slice)으로 자르기 시작했다. (이 문제에서 조각은 부채꼴(circular sector)이다.) 현재 당신은 N개의 조각을 가지고 있고, i번째 조각은 중심각이 Ai 나노도(nanodegree)인 부채꼴이다. (나노도는 10-9도이다.)

당신을 기다리는 손님이 D명 있다. 각 손님은 다른 모든 손님의 조각과 똑같은 크기의 조각을 1개씩 원하지만, 그 크기가 어떤 값인지는 상관하지 않는다. 현재 있는 조각들만으로는 이것이 불가능할 수도 있으므로, 하나 이상의 반지름 방향 절단(cut)을 해야 할 수도 있다.

한 번의 절단은 중심각이 X인 기존 조각 하나를 중심각이 Y와 X - Y인 두 새 조각으로 바꾼다. 0 < Y < X인 어떤 값에 대해서도 가능하며, 이 값들은 정수일 필요가 없다. 이렇게 만들어진 새 조각들 중 하나 또는 둘 모두에 대해 추가 절단을 적용할 수도 있고, 이런 식으로 계속할 수 있다.

손님들에게 나눠 주지 않고 남는 조각이 있어도 된다. (이 재난 때문에 당신도 아침을 못 먹고 있으니, 나중에 당신이 먹으면 된다!)

손님들의 요구를 만족시키기 위해 필요한 절단의 총 개수의 최솟값을 구하라.


입력

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 두 정수 N, D가 주어진 한 줄로 시작한다. 이는 각각 현재 가진 조각의 개수와 손님의 수이다. 그 다음 한 줄에 N개의 정수 A1, A2, ..., AN이 주어진다. i번째 값은 i번째 조각의 중심각(나노도 단위)이다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 최소 절단 횟수이다.


예제 

4
1 3
1
5 2
10 5 359999999999 123456789 10
2 3
8 4
3 2
1 2 3
Case #1: 2
Case #2: 0
Case #3: 1
Case #4: 1
샘플 케이스 #1에서는 시작 슬라이스가 아주 작은 하나뿐이다. 최적 해는 한 번 잘라 이를 내부각이 1/3 나노도와 2/3 나노도인 두 조각으로 만든 뒤, 후자를 다시 잘라 내부각이 1/3 나노도인 두 조각으로 만드는 것이다. 샘플 케이스 #2에서는 같은 크기의 조각이 이미 두 개 있으므로, 그 둘을 그대로 두 손님에게 주면 된다. 추가 절단이 필요 없다. 샘플 케이스 #3에서는 내부각이 8 나노도인 조각을 반으로 자르는 것이 최적이다. 그 후 내부각이 4 나노도인 조각이 정확히 3개가 되고, 남는 조각이 없다. 샘플 케이스 #4에서는 각 손님이 반드시 하나의 조각만 받아야 함을 기억하라. 총 면적이 같더라도 한 손님에게 "3" 조각을, 다른 손님에게 "1"과 "2" 조각을 줄 수는 없다. 이 경우 요구 조건을 만족하려면 적어도 한 번은 잘라야 한다.

출처

GCJ 2020r1c C

로그인해야 코드를 작성할 수 있어요.