codeforces-scrape

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

289A.md (1713B)


      1 Source: https://codeforces.com/problemset/problem/289/A
      2 
      3 A. Polo the Penguin and Segments
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Little penguin Polo adores integer segments, that is, pairs of integers [*l*; *r*] (*l* ≤ *r*).
     22 
     23 He has a set that consists of *n* integer segments: [*l*1; *r*1], [*l*2; *r*2], ..., [*l**n*; *r**n*]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [*l*; *r*] to either segment [*l* - 1; *r*], or to segment [*l*; *r* + 1].
     24 
     25 The value of a set of segments that consists of *n* segments [*l*1; *r*1], [*l*2; *r*2], ..., [*l**n*; *r**n*] is the number of integers *x*, such that there is integer *j*, for which the following inequality holds, *l**j* ≤ *x* ≤ *r**j*.
     26 
     27 Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by *k*.
     28 
     29 Input
     30 
     31 The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 105). Each of the following *n* lines contain a segment as a pair of integers *l**i* and *r**i* ( - 105 ≤ *l**i* ≤ *r**i* ≤ 105), separated by a space.
     32 
     33 It is guaranteed that no two segments intersect. In other words, for any two integers *i*, *j* (1 ≤ *i* < *j* ≤ *n*) the following inequality holds, *min*(*r**i*, *r**j*) < *max*(*l**i*, *l**j*).
     34 
     35 Output
     36 
     37 In a single line print a single integer — the answer to the problem.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2 3  
     45 1 2  
     46 3 4
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 3 7  
     59 1 2  
     60 3 3  
     61 4 7
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 0
     68 ```