Algorithm
Vasya plays The Elder Trolls IV: Oblivon. Oh, those creators of computer games! What they do not come up with! Absolutely unique monsters have been added to the The Elder Trolls IV: Oblivon. One of these monsters is Unkillable Slug. Why it is "Unkillable"? Firstly, because it can be killed with cutting weapon only, so lovers of two-handed amber hammers should find suitable knife themselves. Secondly, it is necessary to make so many cutting strokes to Unkillable Slug. Extremely many. Too many!
Vasya has already promoted his character to 80-th level and in order to gain level 81 he was asked to kill Unkillable Slug. The monster has a very interesting shape. It looks like a rectangular parallelepiped with size x × y × z, consisting of undestructable cells 1 × 1 × 1. At one stroke Vasya can cut the Slug along an imaginary grid, i.e. cut with a plane parallel to one of the parallelepiped side. Monster dies when amount of parts it is divided reaches some critical value.
All parts of monster do not fall after each cut, they remains exactly on its places. I. e. Vasya can cut several parts with one cut.
Vasya wants to know what the maximum number of pieces he can cut the Unkillable Slug into striking him at most k times.
Vasya's character uses absolutely thin sword with infinite length.
The first line of input contains four integer numbers x, y, z, k (1 ≤ x, y, z ≤ 106, 0 ≤ k ≤ 109).
Output the only number — the answer for the problem.
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).
2 2 2 3
8
2 2 2 1
2
In the first sample Vasya make 3 pairwise perpendicular cuts. He cuts monster on two parts with the first cut, then he divides each part on two with the second cut, and finally he divides each of the 4 parts on two.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <vector>
#include <algorithm>
int main(){
const int N = 3;
long x, y, z, m; scanf("%ld %ld %ld %ld", &x, &y, &z, &m);
std::vector<long> dim(N);dim[0] = x; dim[1] = y; dim[2] = z;
sort(dim.begin(), dim.end());
long a = m / 3; if(a > dim[0] - 1){a = dim[0] - 1;}
long b = (m - a) / 2; if(b > dim[1] - 1){b = dim[1] - 1;}
long c = (m - a - b) / 1; if(c > dim[2] - 1){c = dim[2] - 1;}
long long output = (1LL + a) * (1LL + b) * (1LL + c);
printf("%lld\n", output);
return 0;
}Input
Output
Demonstration
Codeforces Solution-A. The Elder Trolls IV: Oblivon-Solution in C, C++, Java, Python