팬케이크 먹기
면접 대비시간 제한1초메모리 제한128 MB
A×B×C 크기의 직육면체에서 매번 한 면과 평행하게 두께 1인 조각을 D번 잘라낼 때, 남는 부피가 최대가 되도록 자르는 방향을 정하는 문제입니다.
문제
오늘 아침 은주는 직육면체 모양의 팬케이크를 만들었다. 팬케이크의 가로, 세로, 높이는 각각 A cm, B cm, C cm이다.
신혜는 이 팬케이크를 D번 먹으려고 한다. 신혜가 한 번 먹을 때마다 은주는 현재 남아 있는 팬케이크를 한 면과 평행하게 잘라, 두께가 정확히 1 cm인 조각 하나를 신혜에게 준다. 은주는 어느 방향으로 자를지 매번 선택할 수 있다.
은주는 원래 팬케이크를 모두 먹고 싶었기 때문에, 신혜가 D번 먹은 뒤에도 가능한 한 많은 양을 남기고 싶다.
A, B, C, D가 주어졌을 때, 신혜가 D번 먹은 뒤 은주가 남길 수 있는 팬케이크 부피의 최댓값을 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분될 수 있다.
각 테스트 케이스는 한 줄에 A, B, C, D가 주어진다.
출력
각 테스트 케이스마다 은주가 남길 수 있는 팬케이크 부피의 최댓값을 한 줄에 하나씩 출력한다. 이 값은 부호 있는 64비트 정수 범위 안에 들어온다.
제한
- 0 ≤ D ≤ A + B + C - 3
힌트
두 번째 테스트 케이스에서는 먼저 4 × 5 면과 평행하게 두 번 잘라 높이를 6 cm에서 4 cm로 줄일 수 있다. 그다음 4 × 4 면과 평행하게 한 번 더 자르면 남은 팬케이크의 크기는 4 × 4 × 4가 되므로 부피는 64이다.