2009C.md (1516B)
1 Source: https://codeforces.com/problemset/problem/2009/C 2 3 C. The Legend of Freya the Frog 4 5 time limit per test 6 7 2 seconds 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 Freya the Frog is traveling on the 2D coordinate plane. She is currently at point $(0,0)$ and wants to go to point $(x,y)$. In one move, she chooses an integer $d$ such that $0 \leq d \leq k$ and jumps $d$ spots forward in the direction she is facing. 22 23 Initially, she is facing the positive $x$ direction. After every move, she will alternate between facing the positive $x$ direction and the positive $y$ direction (i.e., she will face the positive $y$ direction on her second move, the positive $x$ direction on her third move, and so on). 24 25 What is the minimum amount of moves she must perform to land on point $(x,y)$? 26 27 Input 28 29 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 30 31 Each test case contains three integers $x$, $y$, and $k$ ($0 \leq x, y \leq 10^9, 1 \leq k \leq 10^9$). 32 33 Output 34 35 For each test case, output the number of jumps Freya needs to make on a new line. 36 37 Example 38 39 Input 40 41 ``` 42 3 43 44 9 11 3 45 46 0 10 8 47 48 1000000 100000 10 49 ``` 50 51 Output 52 53 ``` 54 8 55 4 56 199999 57 ``` 58 59 Note 60 61 In the first sample, one optimal set of moves is if Freya jumps in the following way: ($0,0$) $\rightarrow$ ($2,0$) $\rightarrow$ ($2,2$) $\rightarrow$ ($3,2$) $\rightarrow$ ($3,5$) $\rightarrow$ ($6,5$) $\rightarrow$ ($6,8$) $\rightarrow$ ($9,8$) $\rightarrow$ ($9,11$). This takes 8 jumps.