1985E.md (2370B)
1 Source: https://codeforces.com/problemset/problem/1985/E 2 3 E. Secret Box 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Ntarsis has a box $B$ with side lengths $x$, $y$, and $z$. It lies in the 3D coordinate plane, extending from $(0,0,0)$ to $(x,y,z)$. 22 23 Ntarsis has a secret box $S$. He wants to choose its dimensions such that all side lengths are positive integers, and the volume of $S$ is $k$. He can place $S$ somewhere within $B$ such that: 24 25 * $S$ is parallel to all axes. 26 * every corner of $S$ lies on an integer coordinate. 27 28 $S$ is magical, so when placed at an integer location inside $B$, it will not fall to the ground. 29 30 Among all possible ways to choose the dimensions of $S$, determine the maximum number of distinct locations he can choose to place his secret box $S$ inside $B$. Ntarsis does not rotate $S$ once its side lengths are selected. 31 32 Input 33 34 The first line consists of an integer $t$, the number of test cases ($1 \leq t \leq 2000$). The description of the test cases follows. 35 36 The first and only line of each test case contains four integers $x, y, z$ and $k$ ($1 \leq x, y, z \leq 2000$, $1 \leq k \leq x \cdot y \cdot z$). 37 38 It is guaranteed the sum of all $x$, sum of all $y$, and sum of all $z$ do not exceed $2000$ over all test cases. 39 40 Note that $k$ may not fit in a standard 32-bit integer data type. 41 42 Output 43 44 For each test case, output the answer as an integer on a new line. If there is no way to select the dimensions of $S$ so it fits in $B$, output $0$. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 3 3 3 8 54 55 3 3 3 18 56 57 5 1 1 1 58 59 2 2 2 7 60 61 3 4 2 12 62 63 4 3 1 6 64 65 1800 1800 1800 4913000000 66 ``` 67 68 Output 69 70 ``` 71 8 72 2 73 5 74 0 75 4 76 4 77 1030301 78 ``` 79 80 Note 81 82 For the first test case, it is optimal to choose $S$ with side lengths $2$, $2$, and $2$, which has a volume of $2 \cdot 2 \cdot 2 = 8$. It can be shown there are $8$ ways to put $S$ inside $B$. 83 84 The coordinate with the least $x$, $y$, and $z$ values for each possible arrangement of $S$ are: 85 86 1. $(0, 0, 0)$ 87 2. $(1, 0, 0)$ 88 3. $(0, 1, 0)$ 89 4. $(0, 0, 1)$ 90 5. $(1, 0, 1)$ 91 6. $(1, 1, 0)$ 92 7. $(0, 1, 1)$ 93 8. $(1, 1, 1)$ 94 95 The arrangement of $S$ with a coordinate of $(0, 0, 0)$ is depicted below: 96 97  98 99 For the second test case, $S$ with side lengths $2$, $3$, and $3$ are optimal.