codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/cb10b493232ebb7dd1b3501f222f3dddc15aff95.png)