codeforces-scrape

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

60A.md (1799B)


      1 Source: https://codeforces.com/problemset/problem/60/A
      2 
      3 A. Where Are My Flakes?
      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 ![](https://espresso.codeforces.com/d1498b1262e9be4d39048f1d8d3113d0d81e77f4.png) 
     22 
     23 One morning the Cereal Guy found out that all his cereal flakes were gone. He found a note instead of them. It turned out that his smart roommate hid the flakes in one of *n* boxes. The boxes stand in one row, they are numbered from 1 to *n* from the left to the right. The roommate left hints like "Hidden to the left of the *i*-th box" ("To the left of *i*"), "Hidden to the right of the *i*-th box" ("To the right of *i*"). Such hints mean that there are no flakes in the *i*-th box as well. The Cereal Guy wants to know the minimal number of boxes he necessarily needs to check to find the flakes considering all the hints. Or he wants to find out that the hints are contradictory and the roommate lied to him, that is, no box has the flakes.
     24 
     25 Input
     26 
     27 The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 1000, 0 ≤ *m* ≤ 1000) which represent the number of boxes and the number of hints correspondingly. Next *m* lines contain hints like "To the left of *i*" and "To the right of *i*", where *i* is integer (1 ≤ *i* ≤ *n*). The hints may coincide.
     28 
     29 Output
     30 
     31 The answer should contain exactly one integer — the number of boxes that should necessarily be checked or "-1" if the hints are contradictory.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 2 1  
     39 To the left of 2
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 1
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 3 2  
     52 To the right of 1  
     53 To the right of 2
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 1
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 3 1  
     66 To the left of 3
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 3 2  
     79 To the left of 2  
     80 To the right of 1
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 -1
     87 ```