codeforces-scrape

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

159B.md (2272B)


      1 Source: https://codeforces.com/contest/159/problem/B
      2 
      3 B. Matchmaker
      4 
      5 time limit per test
      6 
      7 3 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 Polycarpus has *n* markers and *m* marker caps. Each marker is described by two numbers: *x**i* is the color and *y**i* is the diameter. Correspondingly, each cap is described by two numbers: *a**j* is the color and *b**j* is the diameter. Cap (*a**j*, *b**j*) can close marker (*x**i*, *y**i*) only if their diameters match, that is, *b**j* = *y**i*. Besides, a marker is considered to be beautifully closed, if the cap color and the marker color match, that is, *a**j* = *x**i*.
     22 
     23 Find the way to close the maximum number of markers. If there are several such ways, then choose the one that has the maximum number of beautifully closed markers.
     24 
     25 Input
     26 
     27 The first input line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 105) — the number of markers and the number of caps, correspondingly.
     28 
     29 Next *n* lines describe the markers. The *i*-th line contains two space-separated integers *x**i*, *y**i* (1 ≤ *x**i*, *y**i* ≤ 1000) — the *i*-th marker's color and diameter, correspondingly.
     30 
     31 Next *m* lines describe the caps. The *j*-th line contains two space-separated integers *a**j*, *b**j* (1 ≤ *a**j*, *b**j* ≤ 1000) — the color and diameter of the *j*-th cap, correspondingly.
     32 
     33 Output
     34 
     35 Print two space-separated integers *u*, *v*, where *u* is the number of closed markers and *v* is the number of beautifully closed markers in the sought optimal way. Remember that you have to find the way to close the maximum number of markers, and if there are several such ways, you should choose the one where the number of beautifully closed markers is maximum.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 4  
     43 1 2  
     44 3 4  
     45 2 4  
     46 5 4  
     47 2 4  
     48 1 1  
     49 1 2
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 3 2
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 2 2  
     62 1 2  
     63 2 1  
     64 3 4  
     65 5 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 1 0
     72 ```
     73 
     74 Note
     75 
     76 In the first test sample the first marker should be closed by the fourth cap, the second marker should be closed by the first cap and the third marker should be closed by the second cap. Thus, three markers will be closed, and two of them will be beautifully closed — the first and the third markers.