codeforces-scrape

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

1131B.md (1733B)


      1 Source: https://codeforces.com/problemset/problem/1131/B
      2 
      3 B. Draw!
      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 You still have partial information about the score during the historic football match. You are given a set of pairs $(a_i, b_i)$, indicating that at some point during the match the score was "$a_i$: $b_i$". It is known that if the current score is «$x$:$y$», then after the goal it will change to "$x+1$:$y$" or "$x$:$y+1$". What is the largest number of times a draw could appear on the scoreboard?
     22 
     23 The pairs "$a_i$:$b_i$" are given in chronological order (time increases), but you are given score only for some moments of time. The last pair corresponds to the end of the match.
     24 
     25 Input
     26 
     27 The first line contains a single integer $n$ ($1 \le n \le 10000$) — the number of known moments in the match.
     28 
     29 Each of the next $n$ lines contains integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 10^9$), denoting the score of the match at that moment (that is, the number of goals by the first team and the number of goals by the second team).
     30 
     31 All moments are given in chronological order, that is, sequences $x_i$ and $y_j$ are non-decreasing. The last score denotes the final result of the match.
     32 
     33 Output
     34 
     35 Print the maximum number of moments of time, during which the score was a draw. The starting moment of the match (with a score 0:0) is also counted.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3  
     43 2 0  
     44 3 1  
     45 3 4
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 3  
     58 0 0  
     59 0 0  
     60 0 0
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 1  
     73 5 4
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 5
     80 ```
     81 
     82 Note
     83 
     84 In the example one of the possible score sequences leading to the maximum number of draws is as follows: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.