codeforces-scrape

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

44C.md (2340B)


      1 Source: https://codeforces.com/problemset/problem/44/C
      2 
      3 C. Holidays
      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 School holidays come in Berland. The holidays are going to continue for *n* days. The students of school №*N* are having the time of their lives and the IT teacher Marina Sergeyevna, who has spent all the summer busy checking the BSE (Berland State Examination) results, has finally taken a vacation break! Some people are in charge of the daily watering of flowers in shifts according to the schedule. However when Marina Sergeyevna was making the schedule, she was so tired from work and so lost in dreams of the oncoming vacation that she perhaps made several mistakes. In fact, it is possible that according to the schedule, on some days during the holidays the flowers will not be watered or will be watered multiple times. Help Marina Sergeyevna to find a mistake.
     22 
     23 Input
     24 
     25 The first input line contains two numbers *n* and *m* (1 ≤ *n*, *m* ≤ 100) — the number of days in Berland holidays and the number of people in charge of the watering respectively. The next *m* lines contain the description of the duty schedule. Each line contains two integers *a**i* and *b**i* (1 ≤ *a**i* ≤ *b**i* ≤ *n*), meaning that the *i*-th person in charge should water the flowers from the *a**i*-th to the *b**i*-th day inclusively, once a day. The duty shifts are described sequentially, i.e. *b**i* ≤ *a**i* + 1 for all *i* from 1 to *n* - 1 inclusively.
     26 
     27 Output
     28 
     29 Print "OK" (without quotes), if the schedule does not contain mistakes. Otherwise you have to find the minimal number of a day when the flowers will not be watered or will be watered multiple times, and output two integers — the day number and the number of times the flowers will be watered that day.
     30 
     31 Examples
     32 
     33 Input
     34 
     35 ```
     36 10 5  
     37 1 2  
     38 3 3  
     39 4 6  
     40 7 7  
     41 8 10
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 OK
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 10 5  
     54 1 2  
     55 2 3  
     56 4 5  
     57 7 8  
     58 9 10
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 2 2
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 10 5  
     71 1 2  
     72 3 3  
     73 5 7  
     74 7 7  
     75 7 10
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 4 0
     82 ```
     83 
     84 Note
     85 
     86 Keep in mind that in the second sample the mistake occurs not only on the second day, but also on the sixth day, when nobody waters the flowers. However, you have to print the second day, i.e. the day with the minimal number.