codeforces-scrape

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

1971E.md (3082B)


      1 Source: https://codeforces.com/problemset/problem/1971/E
      2 
      3 E. Find the Car
      4 
      5 time limit per test
      6 
      7 3 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 Timur is in a car traveling on the number line from point $0$ to point $n$. The car starts moving from point $0$ at minute $0$.
     22 
     23 There are $k+1$ signs on the line at points $0, a_1, a_2, \dots, a_k$, and Timur knows that the car will arrive there at minutes $0, b_1, b_2, \dots, b_k$, respectively. The sequences $a$ and $b$ are strictly increasing with $a_k = n$.
     24 
     25  ![](https://espresso.codeforces.com/c5ec45581a60511ef12703d09478d2b514395067.png) 
     26 
     27 Between any two adjacent signs, the car travels with a constant speed. Timur has $q$ queries: each query will be an integer $d$, and Timur wants you to output how many minutes it takes the car to reach point $d$, rounded down to the nearest integer.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains three integers $n$, $k$, and $q$, ($k \leq n \leq 10^9$; $1 \leq k, q \leq 10^5$) — the final destination, the number of points Timur knows the time for, and the number of queries respectively.
     34 
     35 The second line of each test case contains $k$ integers $a_i$ ($1 \leq a_i \leq n$; $a_i \lt a_{i+1}$ for every $1 \leq i \leq k-1$; $a_k = n$).
     36 
     37 The third line of each test case contains $k$ integers $b_i$ ($1 \leq b_i \leq 10^9$; $b_i \lt b_{i+1}$ for every $1 \leq i \leq k-1$).
     38 
     39 Each of the following $q$ lines contains a single integer $d$ ($0 \leq d \leq n$) — the distance that Timur asks the minutes passed for.
     40 
     41 The sum of $k$ over all test cases doesn't exceed $10^5$, and the sum of $q$ over all test cases doesn't exceed $10^5$.
     42 
     43 Output
     44 
     45 For each query, output a single integer — the number of minutes passed until the car reaches the point $d$, rounded down.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 
     54 10 1 3
     55 
     56 10
     57 
     58 10
     59 
     60 0
     61 
     62 6
     63 
     64 7
     65 
     66 10 2 4
     67 
     68 4 10
     69 
     70 4 7
     71 
     72 6
     73 
     74 4
     75 
     76 2
     77 
     78 7
     79 
     80 1000000000 1 1
     81 
     82 1000000000
     83 
     84 1000000000
     85 
     86 99999999
     87 
     88 6 1 3
     89 
     90 6
     91 
     92 5
     93 
     94 2
     95 
     96 6
     97 
     98 5
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 0 6 7 
    105 5 4 2 5 
    106 99999999 
    107 1 5 4
    108 ```
    109 
    110 Note
    111 
    112 For the first test case, the car goes from point $0$ to point $10$ in $10$ minutes, so the speed is $1$ unit per minute and:
    113 
    114 * At point $0$, the time will be $0$ minutes.
    115 * At point $6$, the time will be $6$ minutes.
    116 * At point $7$, the time will be $7$ minutes.
    117 
    118 For the second test case, between points $0$ and $4$, the car travels at a speed of $1$ unit per minute and between $4$ and $10$ with a speed of $2$ units per minute and:
    119 
    120 * At point $6$, the time will be $5$ minutes.
    121 * At point $4$, the time will be $4$ minutes.
    122 * At point $2$, the time will be $2$ minutes.
    123 * At point $7$, the time will be $5.5$ minutes, so the answer is $5$.
    124 
    125 For the fourth test case, the car travels with $1.2$ units per minute, so the answers to the queries are:
    126 
    127 * At point $2$, the time will be $1.66\dots$ minutes, so the answer is $1$.
    128 * At point $6$, the time will be $5$ minutes.
    129 * At point $5$, the time will be $4.16\dots$ minutes, so the answer is $4$.