codeforces-scrape

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

629B.md (1954B)


      1 Source: https://codeforces.com/problemset/problem/629/B
      2 
      3 B. Far Relative’s Problem
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has *n* friends and each of them can come to the party in a specific range of days of the year from *a**i* to *b**i*. Of course, Famil Door wants to have as many friends celebrating together with him as possible.
     22 
     23 Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party.
     24 
     25 Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 5000) — then number of Famil Door's friends.
     30 
     31 Then follow *n* lines, that describe the friends. Each line starts with a capital letter 'F' for female friends and with a capital letter 'M' for male friends. Then follow two integers *a**i* and *b**i* (1 ≤ *a**i* ≤ *b**i* ≤ 366), providing that the *i*-th friend can come to the party from day *a**i* to day *b**i* inclusive.
     32 
     33 Output
     34 
     35 Print the maximum number of people that may come to Famil Door's party.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4  
     43 M 151 307  
     44 F 343 352  
     45 F 117 145  
     46 M 24 128
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 6  
     59 M 128 130  
     60 F 128 131  
     61 F 131 140  
     62 F 131 141  
     63 M 131 200  
     64 M 140 200
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 4
     71 ```
     72 
     73 Note
     74 
     75 In the first sample, friends 3 and 4 can come on any day in range [117, 128].
     76 
     77 In the second sample, friends with indices 3, 4, 5 and 6 can come on day 140.