문제
오늘 아침 은주는 팬케익을 만들었다. 자 이제 신혜는 이 팬케익을 먹으려고 한다.
은주가 만든 팬케익은 박스 모양이고, 가로 Acm, 세로 Bcm, 높이 Ccm 크기이다.
신혜는 팬케익을 D번 먹으려고 한다. 매번 신혜가 팬케익을 먹으려고 할 때, 은주는 팬케익을 변에 평행하게 자른 후에 신혜에게 준다.
은주는 뛰어난 요리사이기 때문에, 자르는 케익은 모두 두께가 1cm이다.
원래 은주는 팬케익을 다 먹으려고 했으나, 어쩔수 없이 신혜에게 주는 것이다. 따라서, 최대한 많은 양을 남기려고 한다.
신혜가 팬케익을 D번 먹은 후에 남은 케익의 양은 은주가 케익을 자르는 방법에 따라서 달라지게 된다.
A, B, C, D가 주어졌을 때, 신헤가 팬케익을 D번 먹은 후에 남은 팬케익 부피의 가능한 최댓값을 구하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 빈 줄로 구분되며, 다음과 같이 구성되어 있다.
테스트 케이스의 첫째 줄에 A, B, C, D가 주어진다.
출력
각 테스트 케이스에 대해 은주가 남길 수 있는 팬케익의 최대 부피를 차례대로 한 줄에 하나씩 출력한다. 이 부피는 부호있는 64비트 정수 범위 안에 들어온다.
제한
- 0 ≤ D ≤ A + B + C - 3
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| Easy | 1 | 0 < A, B, C ≤ 1000 |
| Hard | 2 | 0 < A, B, C ≤ 1018 |
예제 입력
1
2
3
4
5
6
7
3
4 5 6 0
4 5 6 3
1 1 10 9
예제 출력
1
2
3
120
64
1
풀이과정
문제를 보자마자 생각해낸 방법은 반복문을 통해 입력받은 A,B,C 중 가장 큰 수를 구한 후, 그 수를 하나 씩 줄이는 방법을 사용했는데, 1점을 받았다.
시간을 더 단축 시켜야 된다는 걸 깨닫고 다른 방법을 구해보았다.
구하려는 부피가 최대가 되려고 하면 결국 A, B, C의 크기가 비슷해져 되기 때문에 이를 이용하는 다른 방법으로 시간 단축을 해보았다.