#include #include using namespace std; const int MAX_WIDTH = 20; const int MAX_HEIGHT = 20; const int MAX_PIECES = 20; const int INFINITY = 1000000; int largestArea[MAX_WIDTH+1][MAX_HEIGHT+1][MAX_PIECES+1]; int main (){ // initialization for (int w = 1; w <= MAX_WIDTH; w++){ for (int h = 1; h <= MAX_HEIGHT; h++){ largestArea[w][h][1] = w*h; } } // dynamic programming for (int m = 2; m <= MAX_PIECES; m++){ // build each piece using smaller pieces for (int w = 1; w <= MAX_WIDTH; w++){ for (int h = 1; h <= MAX_HEIGHT; h++){ largestArea[w][h][m] = INFINITY; for (int m1 = 1; m1 < m; m1++){ // try all vertical cuts for (int w1 = 1; w1 < w; w1++){ largestArea[w][h][m] = min (largestArea[w][h][m], max (largestArea[w1][h][m1], largestArea[w-w1][h][m-m1])); } // try all horizontal cuts for (int h1 = 1; h1 < h; h1++){ largestArea[w][h][m] = min (largestArea[w][h][m], max (largestArea[w][h1][m1], largestArea[w][h-h1][m-m1])); } } } } } while (true){ int width, height, numPieces; cin >> width >> height >> numPieces; if (width == 0 && height == 0 && numPieces == 0) break; cout << largestArea[width][height][numPieces] << endl; } return 0; }