2181H.md (1498B)
1 Source: https://codeforces.com/problemset/problem/2181/H 2 3 H. Honey Cake 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 1024 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hannah and Henry are going to host a party for $n$ people, including themselves. 22 23 They bought a honey cake of size $w \times h \times d$ inches for the party, and want to split it into $n$ equal pieces. 24 25 The honey cake can be cut parallel to any of its faces. To make cuts precise, each edge of length $w$ is cut into the same number of equal parts, each having integer length; similarly for edges of lengths $h$ and $d$. 26 27 Given the dimensions of the honey cake, determine whether it is possible to cut it into $n$ equal pieces, and if so, how. 28 29 Input 30 31 The first line of input contains three integers: $w$, $h$, and $d$, the dimensions of the honey cake in inches ($1 \le w, h, d \le 10^9$). 32 33 The second line contains a single integer $n$ ($1 \le n \le 10^9$). 34 35 Output 36 37 Output three integers $w_c$, $h_c$, $d_c$, the number of cuts to be made along each of the dimensions $w$, $h$, and $d$, respectively, if it is possible to cut the cake, or a single integer $-1$ otherwise. Note that making zero cuts along a dimension is allowed, too. 38 39 Example 40 41 Input 42 43 ``` 44 10 20 6 45 40 46 ``` 47 48 Output 49 50 ``` 51 4 3 1 52 ``` 53 54 Note 55 56 In the first example, the cake will be cut into $5 \cdot 4 \cdot 2 = 40$ pieces of size $2 \times 5 \times 3$ inches. 57 58 