codeforces-scrape

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

1922C.md (3397B)


      1 Source: https://codeforces.com/problemset/problem/1922/C
      2 
      3 C. Closest Cities
      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 There are $n$ cities located on the number line, the $i$-th city is in the point $a_i$. The coordinates of the cities are given in ascending order, so $a_1 \lt a_2 \lt \dots \lt a_n$.
     22 
     23 The distance between two cities $x$ and $y$ is equal to $|a_x - a_y|$.
     24 
     25 For each city $i$, let's define the closest city $j$ as the city such that the distance between $i$ and $j$ is not greater than the distance between $i$ and each other city $k$. For example, if the cities are located in points $[0, 8, 12, 15, 20]$, then:
     26 
     27 * the closest city to the city $1$ is the city $2$;
     28 * the closest city to the city $2$ is the city $3$;
     29 * the closest city to the city $3$ is the city $4$;
     30 * the closest city to the city $4$ is the city $3$;
     31 * the closest city to the city $5$ is the city $4$.
     32 
     33 The cities are located in such a way that for every city, the closest city is unique. For example, it is impossible for the cities to be situated in points $[1, 2, 3]$, since this would mean that the city $2$ has two closest cities ($1$ and $3$, both having distance $1$).
     34 
     35 You can travel between cities. Suppose you are currently in the city $x$. Then you can perform one of the following actions:
     36 
     37 * travel to any other city $y$, paying $|a_x - a_y|$ coins;
     38 * travel to the city which is the closest to $x$, paying $1$ coin.
     39 
     40 You are given $m$ queries. In each query, you will be given two cities, and you have to calculate the minimum number of coins you have to spend to travel from one city to the other city.
     41 
     42 Input
     43 
     44 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     45 
     46 Each test case is given in the following format:
     47 
     48 * the first line contains one integer $n$ ($2 \le n \le 10^5$);
     49 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$);
     50 * the third line contains one integer $m$ ($1 \le m \le 10^5$);
     51 * then $m$ lines follow; the $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$), denoting that in the $i$-th query, you have to calculate the minimum number of coins you have to spend to travel from the city $x_i$ to the city $y_i$.
     52 
     53 Additional constraints on the input:
     54 
     55 * in every test case, for each city, the closest city is determined uniquely;
     56 * the sum of $n$ over all test cases does not exceed $10^5$;
     57 * the sum of $m$ over all test cases does not exceed $10^5$.
     58 
     59 Output
     60 
     61 For each query, print one integer — the minimum number of coins you have to spend.
     62 
     63 Example
     64 
     65 Input
     66 
     67 ```
     68 1
     69 
     70 5
     71 
     72 0 8 12 15 20
     73 
     74 5
     75 
     76 1 4
     77 
     78 1 5
     79 
     80 3 4
     81 
     82 3 2
     83 
     84 5 1
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 3
     91 8
     92 1
     93 4
     94 14
     95 ```
     96 
     97 Note
     98 
     99 Let's consider the first two queries in the example from the statement:
    100 
    101 * in the first query, you are initially in the city $1$. You can travel to the closest city (which is the city $2$), paying $1$ coin. Then you travel to the closest city (which is the city $3$) again, paying $1$ coin. Then you travel to the closest city (which is the city $4$) again, paying $1$ coin. In total, you spend $3$ coins to get from the city $1$ to the city $4$;
    102 * in the second query, you can use the same way to get from the city $1$ to the city $4$, and then spend $5$ coins to travel from the city $4$ to the city $5$.