# DCP-408: CutLet Back to All Problems

Medium Search Techniques > Ternary Search

There is a n*m Grid. You're to make k cut. - Your cut should not divide any unit square of grid. means a cut must go through the edges of unit square. - A cut must be parallel to the row or column of the grid after each cut your grid must be divided into two part. you can keep any of them and discard another. then you'll continue cutting until k cut is completed. what is the maximum possible area of remaining grid after k cut? Input: ------ 1st line of input contain a integer **T (1<=T<=10<sup>5</sup>)** , denotes the number of test case. then each of next t line contain 3 integer n,m,k **(1<=n,m,k<=10<sup>9</sup>)** Output: ------- If k cut is possible, Print 3 integer (a,x,y),separated by space for each test case in a line. a is the maximum possible area of the rectangle after k cut. , x is number of cut you make parallel to the row,y is number of cut you make parallel to the column, - x+y should be equal to k - if multiple answer is possible print that one for which x is minimum if its not possible to make k cut , then print -1 Sample Input ------------ 10 3 10 1 10 3 1 4 5 4 5 4 4 10 20 50 20 10 5 5 5 23 100 578 250 350 470 80 25 25 23 Sample Output ------------- 27 0 1 27 1 0 6 1 3 6 2 2 -1 150 5 0 -1 32800 0 250 136500 0 80 182 11 12

### Problem Limits

 Language Time Limit (seconds) C 0.75 C++ 0.75 C++14 0.75 C# 1.00 Go 1.00 Java 1.00 JavaScript 1.00 Objective-C 1.00 Perl 1.00 PHP 1.00 Python 1.00 Python3 1.00 Ruby 1.00 VB.Net 1.00

# 20/63

Solve/Submission

### Ranking

# User Language Timing
01 emotionless Cpp14 0.05s
02 tariqiitju Cpp 0.07s
03 ssavi Cpp 0.07s
04 MazedRupok Cpp 0.07s
05 feodorv C 0.07s
06 unknown420 Cpp 0.07s
07 mepromee Cpp 0.07s
08 DynamicOvi Cpp 0.07s
09 kissu_pari_na Cpp 0.07s
10 Pure_Protea Cpp14 0.08s
Feedback