codeforces-scrape

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

938B.md (2029B)


      1 Source: https://codeforces.com/problemset/problem/938/B
      2 
      3 B. Run For Your Prize
      4 
      5 time limit per test
      6 
      7 1 second
      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 You and your friend are participating in a TV show "Run For Your Prize".
     22 
     23 At the start of the show *n* prizes are located on a straight line. *i*-th prize is located at position *a**i*. Positions of all prizes are distinct. You start at position 1, your friend — at position 106 (and there is no prize in any of these two positions). You have to work as a team and collect all prizes in minimum possible time, in any order.
     24 
     25 You know that it takes exactly 1 second to move from position *x* to position *x* + 1 or *x* - 1, both for you and your friend. You also have trained enough to instantly pick up any prize, if its position is equal to your current position (and the same is true for your friend). Carrying prizes does not affect your speed (or your friend's speed) at all.
     26 
     27 Now you may discuss your strategy with your friend and decide who will pick up each prize. Remember that every prize must be picked up, either by you or by your friend.
     28 
     29 What is the minimum number of seconds it will take to pick up all the prizes?
     30 
     31 Input
     32 
     33 The first line contains one integer *n* (1 ≤ *n* ≤ 105) — the number of prizes.
     34 
     35 The second line contains *n* integers *a*1, *a*2, ..., *a**n* (2 ≤ *a**i* ≤ 106 - 1) — the positions of the prizes. No two prizes are located at the same position. Positions are given in ascending order.
     36 
     37 Output
     38 
     39 Print one integer — the minimum number of seconds it will take to collect all prizes.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 2 3 9
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 8
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 2  
     60 2 999995
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 5
     67 ```
     68 
     69 Note
     70 
     71 In the first example you take all the prizes: take the first at 1, the second at 2 and the third at 8.
     72 
     73 In the second example you take the first prize in 1 second and your friend takes the other in 5 seconds, you do this simultaneously, so the total time is 5.