codeforces-scrape

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

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.