codeforces-scrape

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

1730B.md (2631B)


      1 Source: https://codeforces.com/problemset/problem/1730/B
      2 
      3 B. Meeting on the Line
      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 $n$ people live on the coordinate line, the $i$-th one lives at the point $x_i$ ($1 \le i \le n$). They want to choose a position $x_0$ to meet. The $i$-th person will spend $|x_i - x_0|$ minutes to get to the meeting place. Also, the $i$-th person needs $t_i$ minutes to get dressed, so in total he or she needs $t_i + |x_i - x_0|$ minutes.
     22 
     23 Here $|y|$ denotes the absolute value of $y$.
     24 
     25 These people ask you to find a position $x_0$ that minimizes the time in which all $n$ people can gather at the meeting place.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. Then the test cases follow.
     30 
     31 Each test case consists of three lines.
     32 
     33 The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of people.
     34 
     35 The second line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{8}$) — the positions of the people.
     36 
     37 The third line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \le t_i \le 10^{8}$), where $t_i$ is the time $i$-th person needs to get dressed.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print a single real number — the optimum position $x_0$. It can be shown that the optimal position $x_0$ is unique.
     44 
     45 Your answer will be considered correct if its absolute or relative error does not exceed $10^{−6}$. Formally, let your answer be $a$, the jury's answer be $b$. Your answer will be considered correct if $\frac{|a−b|}{max(1,|b|)} \le 10^{−6}$.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 7
     53 
     54 1
     55 
     56 0
     57 
     58 3
     59 
     60 2
     61 
     62 3 1
     63 
     64 0 0
     65 
     66 2
     67 
     68 1 4
     69 
     70 0 0
     71 
     72 3
     73 
     74 1 2 3
     75 
     76 0 0 0
     77 
     78 3
     79 
     80 1 2 3
     81 
     82 4 1 2
     83 
     84 3
     85 
     86 3 3 3
     87 
     88 5 3 3
     89 
     90 6
     91 
     92 5 4 7 2 10 4
     93 
     94 3 2 5 1 4 6
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 0
    101 2
    102 2.5
    103 2
    104 1
    105 3
    106 6
    107 ```
    108 
    109 Note
    110 
    111 * In the $1$-st test case there is one person, so it is efficient to choose his or her position for the meeting place. Then he or she will get to it in $3$ minutes, that he or she need to get dressed.
    112 * In the $2$-nd test case there are $2$ people who don't need time to get dressed. Each of them needs one minute to get to position $2$.
    113 * In the $5$-th test case the $1$-st person needs $4$ minutes to get to position $1$ ($4$ minutes to get dressed and $0$ minutes on the way); the $2$-nd person needs $2$ minutes to get to position $1$ ($1$ minute to get dressed and $1$ minute on the way); the $3$-rd person needs $4$ minutes to get to position $1$ ($2$ minutes to get dressed and $2$ minutes on the way).