prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8<h2>Problem K:9$L_{\infty}$ Jumps10</h2>11 12<p>13  Given two points $(p, q)$ and $(p', q')$ in the XY-plane, the $L_{\infty}$ <i>distance</i> between them is defined as $max(|p − p'|, |q − q'|)$. In this problem, you are given four integers $n$, $d$, $s$, $t$. Suppose that you are initially standing at point $(0, 0)$ and you need to move to point $(s, t)$. For this purpose, you perform jumps exactly $n$ times. In each jump, you must move exactly $d$ in the $L_{\infty}$ distance measure. In addition, the point you reach by a jump must be a lattice point in the XY-plane. That is, when you are standing at point $(p, q)$, you can move to a new point $(p', q')$ by a single jump if $p'$ and $q'$ are integers and $max(|p − p'|, |q − q'|) = d$ holds.14</p>15 16<p>17  Note that you cannot stop jumping even if you reach the destination point $(s, t)$ before you perform the jumps $n$ times.18</p>19 20<p>21  To make the problem more interesting, suppose that some cost occurs for each jump. You are given $2n$ additional integers $x_1$, $y_1$, $x_2$, $y_2$, . . . , $x_n$, $y_n$ such that $max(|x_i|, |y_i|) = d$ holds for each $1 \leq i \leq n$. The cost of the $i$-th (1-indexed) jump is defined as follows: Let $(p, q)$ be a point at which you are standing before the $i$-th jump. Consider a set of lattice points that you can jump to. Note that this set consists of all the lattice points on the edge of a certain square. We assign integer 1 to point $(p + x_i, q + y_i)$. Then, we assign integers $2, 3, . . . , 8d$ to the remaining points in the set in the counter-clockwise order. (Here, assume that the right direction is positive in the $x$-axis and the upper direction is positive in the $y$-axis.) These integers represent the costs when you perform a jump to these points.22</p>23 24<p>25  For example, Figure K.1 illustrates the points reachable by your $i$-th jump when $d = 2$ and you are at $(3, 1)$. The numbers represent the costs for $x_i = −1$ and $y_i = −2$.26</p>27 28<center>29<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2014_K1" width="400"><br>30<p>Figure K.1. Reachable points and their costs</p>31</center>32 33 34<p>35  Compute and output the minimum required sum of the costs for the objective.36</p>37 38<h3>Input</h3>39 40<p>41  The input consists of a single test case.<br>42  <br>43$n$ $d$ $s$ $t$<br>44$x_1$ $y_1$<br>45$x_2$ $y_2$<br>46.<br>47.<br>48.<br>49$x_n$ $y_n$<br>50<br>51 52The first line contains four integers. $n$ ($1 \leq n \leq 40$) is the number of jumps to perform. $d$ ($1 \leq d \leq 10^{10}$) is the $L_{\infty}$ distance which you must move by a single jump. $s$ and $t$ ($|s|, |t| \leq nd$) are the $x$ and $y$ coordinates of the destination point. It is guaranteed that there is at least one way to reach the destination point by performing $n$ jumps.53</p>54 55<p>56Each of the following $n$ lines contains two integers, $x_i$ and $y_i$ with $max(|x_i|, |y_i|) = d$.57</p>58 59<h3>Output</h3>60 61<p>62Output the minimum required cost to reach the destination point.63</p>64 65<h3>Sample Input 1</h3>66 67<pre>3 2 4 0682 269-2 -270-2 2</pre>71 72<h3>Sample Output 1</h3>73 74<pre>15</pre>75 76<h3>Sample Input 2</h3>77 78<pre>4 1 2 -2791 -1801 0811 182-1 0</pre>83 84<h3>Sample Output 2</h3>85 86<pre>10</pre>87 88<h3>Sample Input 3</h3>89 90<pre>6 5 0 2915 292-5 2935 094-3 595-5 4965 5</pre>97 98<h3>Sample Output 3</h3>99 100<pre>24</pre>101 102<h3>Sample Input 4</h3>103 104<pre>5 91 -218 -35110591 9110691 9110791 9110891 9110991 91</pre>110 111<h3>Sample Output 4</h3>112 113<pre>1958</pre>114 115<h3>Sample Input 5</h3>116 117<pre>1 10000000000 -10000000000 -25275323461188198855077 10000000000</pre>119 120<h3>Sample Output 5</h3>121 122<pre>30726387424</pre>123 124