codeforces-scrape

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

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  ![](https://espresso.codeforces.com/08665616987261ba852133fce4a6da9fcb5a2919.png) 
     98 
     99 For the second test case, $S$ with side lengths $2$, $3$, and $3$ are optimal.