레이팅 미적용베시(Bessie)와 친구들에 대해 잘 알려지지 않은 사실 하나는, 이들이 계단 오르기 경주를 사랑한다는 것이다. 더 잘 알려진 사실은 소들이 계단을 내려가는 것을 정말 싫어한다는 것이다. 그래서 소들은 가장 좋아하는 고층 빌딩 꼭대기까지 경주를 마친 후 곤란해졌다. 계단으로 다시 내려가기를 거부한 소들은, 1층으로 돌아가기 위해 어쩔 수 없이 엘리베이터를 타야 한다.
엘리베이터의 최대 적재 중량은 W (1 <= W <= 100,000,000) 파운드이고, 소 i의 무게는 C_i (1 <= C_i <= W) 파운드이다. N마리 (1 <= N <= 18)의 소 전부를 최소 횟수의 엘리베이터 운행으로 1층까지 내려보내는 방법을 알아내는 것을 베시에게 도와주자. 각 엘리베이터 운행에서 탑승한 소들의 무게 합은 W 이하여야 한다.
첫째 줄: 공백으로 구분된 N과 W.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 소 한 마리의 무게를 나타내는 정수 C_i가 주어진다.
첫째 줄: 필요한 엘리베이터 운행의 최소 횟수를 나타내는 정수 R.
둘째 줄부터 1+R번째 줄까지: 각 줄은 R번의 운행 중 한 번에 함께 내려가는 소들의 집합을 설명한다. 각 줄은 집합에 속한 소의 수를 나타내는 정수로 시작하고, 그 뒤에 집합에 속한 각 소의 번호가 이어진다.
(이 문제는 유효한 출력이 여러 개일 수 있으며, 최소 횟수의 유효한 운행 집합이라면 무엇이든 스페셜 저지가 정답으로 인정한다.)
skyscraper.in · 출력을 쓸 파일 skyscraper.out4 10
5
6
3
73
2 1 3
1 2
1 4Input details: There are four cows weighing 5, 6, 3, and 7 pounds. The elevator has a maximum weight capacity of 10 pounds.
Output details: We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined. Several other solutions are possible for this input.