문제 두 나라를 통합할 때, 두 나라에는 일반적으로 도로 표지판, 음식 등 각자의 고유한 버전이 존재합니다. 만약 한 나라의 버전을 다른 나라에 "강요"하게 되면, 이는 두 나라의 평등한 통합이라기보다는 병합에 가깝게 느껴질 수 있습니다. 그러므로 두 나라의 작은 요소들을 모두 고려해, 모두가 수용할 수 있는 전체를 만들어야 합니다. 예를 들어, 동독 사람들은 자신들만의 버전인 피클과 케첩을 좋아했습니다. 경우에 따라 양쪽 모두가 한 나라의 버전이 더 좋다고 동의하기도 하는데, 예를 들어 모든 사람들은 동독의 "Ampelmännchen"이라는 교통 신호 보행자 표지판을 좋아합니다. 각 나라가 각자의 버전을 선호할 때는 더 어려워지며, 이 경우 "우리는 피클에 정말 신경을 쓰니, 우리 버전을 유지하고, 대신 당신들의 케첩도 거의 좋아하니 그걸 받아들이겠습니다."와 같은 타협이 필요합니다. 여기서 여러분은 두 문화의 타협점을 찾아내야 합니다.
각 항목에 대해 양쪽 나라가 각 버전을 얼마나 선호하는지에 대한 정보가 주어집니다. 또한 두 나라 각각에 사는 사람 수가 주어집니다. 목표는 선택한 모든 항목에서 모든 사람의 "행복" 총합을 최대화하는 선택을 찾아내는 것입니다. 각 항목(예: "피클")에 대해 두 나라의 버전 중 하나만 선택할 수 있습니다.
입력 첫 번째 줄에는 입력 데이터 세트의 개수 K ≥ 1이 주어집니다. 이어서 K개의 데이터 세트가 다음 형식으로 주어집니다:
각 데이터 세트의 첫 번째 줄에는 세 개의 정수 n, W, E가 있습니다. 0 ≤ n ≤ 1000는 논란이 있는 항목의 개수를 나타내며, 0 ≤ W, E ≤ 10000은 각각 서쪽과 동쪽에 사는 사람 수입니다.
다음 n개의 줄에는 각 항목에 대해 네 개의 정수 0 ≤ Lw,w, Lw,e, Le,w, Le,e ≤ 100이 주어집니다. 이들은 각각 서쪽 사람들이 서쪽 버전을 얼마나 좋아하는지, 서쪽 사람들이 동쪽 버전을 얼마나 좋아하는지, 동쪽 사람들이 서쪽 버전을 얼마나 좋아하는지, 동쪽 사람들이 동쪽 버전을 얼마나 좋아하는지를 나타냅니다.
출력 각 데이터 세트에 대해 첫 번째 줄에 "Data Set x:"를 출력합니다. 여기서 x는 데이터 세트 번호입니다. 그 후, 각 항목에서 정확히 하나의 버전을 선택하여 얻을 수 있는 최대 총 행복을 출력합니다.
taeyang95 2년 전 3
문제
두 나라를 통합할 때, 두 나라에는 일반적으로 도로 표지판, 음식 등 각자의 고유한 버전이 존재합니다. 만약 한 나라의 버전을 다른 나라에 "강요"하게 되면, 이는 두 나라의 평등한 통합이라기보다는 병합에 가깝게 느껴질 수 있습니다. 그러므로 두 나라의 작은 요소들을 모두 고려해, 모두가 수용할 수 있는 전체를 만들어야 합니다. 예를 들어, 동독 사람들은 자신들만의 버전인 피클과 케첩을 좋아했습니다. 경우에 따라 양쪽 모두가 한 나라의 버전이 더 좋다고 동의하기도 하는데, 예를 들어 모든 사람들은 동독의 "Ampelmännchen"이라는 교통 신호 보행자 표지판을 좋아합니다. 각 나라가 각자의 버전을 선호할 때는 더 어려워지며, 이 경우 "우리는 피클에 정말 신경을 쓰니, 우리 버전을 유지하고, 대신 당신들의 케첩도 거의 좋아하니 그걸 받아들이겠습니다."와 같은 타협이 필요합니다. 여기서 여러분은 두 문화의 타협점을 찾아내야 합니다.
각 항목에 대해 양쪽 나라가 각 버전을 얼마나 선호하는지에 대한 정보가 주어집니다. 또한 두 나라 각각에 사는 사람 수가 주어집니다. 목표는 선택한 모든 항목에서 모든 사람의 "행복" 총합을 최대화하는 선택을 찾아내는 것입니다. 각 항목(예: "피클")에 대해 두 나라의 버전 중 하나만 선택할 수 있습니다.
입력
첫 번째 줄에는 입력 데이터 세트의 개수 K ≥ 1이 주어집니다. 이어서 K개의 데이터 세트가 다음 형식으로 주어집니다:
각 데이터 세트의 첫 번째 줄에는 세 개의 정수 n, W, E가 있습니다. 0 ≤ n ≤ 1000는 논란이 있는 항목의 개수를 나타내며, 0 ≤ W, E ≤ 10000은 각각 서쪽과 동쪽에 사는 사람 수입니다.
다음 n개의 줄에는 각 항목에 대해 네 개의 정수 0 ≤ Lw,w, Lw,e, Le,w, Le,e ≤ 100이 주어집니다. 이들은 각각 서쪽 사람들이 서쪽 버전을 얼마나 좋아하는지, 서쪽 사람들이 동쪽 버전을 얼마나 좋아하는지, 동쪽 사람들이 서쪽 버전을 얼마나 좋아하는지, 동쪽 사람들이 동쪽 버전을 얼마나 좋아하는지를 나타냅니다.
출력
각 데이터 세트에 대해 첫 번째 줄에 "Data Set x:"를 출력합니다. 여기서 x는 데이터 세트 번호입니다. 그 후, 각 항목에서 정확히 하나의 버전을 선택하여 얻을 수 있는 최대 총 행복을 출력합니다.
각 데이터 세트는 빈 줄로 구분되어야 합니다.