CCC '15 S2 - Jerseys

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2015 Stage 1, Senior #2

A school team is trying to assign jerseys numbered 1, 2, 3, \dots, J to student athletes. The size of each jersey is either small (S), medium (M) or large (L).

Each athlete has requested a specific jersey number and a preferred size. The athletes will not be satisfied with a jersey that is the wrong number or that is smaller than their preferred size. They will be satisfied with a jersey that is their preferred size or larger as long as it is the right number. Two students cannot be given the same jersey.

Your task is to determine the maximum number of requests that can be satisfied.

Input Specification

The first line of input is the integer J which is the number of jerseys.

The second line of input is the integer A which is the number of athletes.

The next J lines are each the character S, M or L. Line j gives the size of jersey j (1 \le j \le J).

The last A lines are each the character S, M or L followed by a space, followed by an integer. Line a (1 \le a \le A) gives the requested size and jersey number for athlete a where the athletes are numbered 1, 2, 3, \dots, A.

For 50% of the test cases, 1 \le J \le 10^3 and 1 \le A \le 10^3.

For the remaining 50% of the test cases, 1 \le J \le 10^6 and 1 \le A \le 10^6.

Output Specification

The output will consist of a single integer which is the maximum number of requests that can be satisfied.

Sample Input

4
3
M
S
S
L
L 3
S 3
L 1

Output for Sample Input

1

Explanation Sample Output

Jersey 1 cannot be assigned because it is medium and athlete 3 requested large. No athlete requested jersey 2 or 4. Jersey 3, can be assigned to athlete 2, but not athlete 1.


Comments


  • 0
    Xenosi  commented on March 17, 2019, 1:35 p.m. edited

    I keep on getting segmentation error on all of my submissions. Can someone please take a look at my code and see what's wrong? Edit: Fixed


  • -1
    P234rex  commented on Nov. 7, 2016, 10:34 p.m.

    Is there actually a way to do this with python or nah I keep TLE on the last case and i've done all the optimization i can imagine


    • 1
      1369738647  commented on Aug. 29, 2018, 6:46 p.m.

      just try to make your code more efficient. You can solve this question with python for sure!


    • 0
      Xyene  commented on Nov. 8, 2016, 12:34 a.m.

      You should give the PyPy interpreter a try. It often outperforms CPython on problems like these, at the expense of a higher memory footprint.

      That said, you might also want to check out the Python Tips page: while your solution will pass under PyPy, there are some other optimizations you could have gone for (not necessarily ones that would allow you to pass with plain CPython, though).


  • 0
    andrew498  commented on July 31, 2015, 3:32 a.m.

    I'm just wondering why on the last three test cases the answer always returns 9, is it a problem with my algorithm or is it because I'm using an ArrayList or something of that nature? Thanks. (on my most recent submission btw).


    • 4
      lKunelk  commented on Aug. 1, 2015, 11:41 a.m.

      The problem is when you're taking the substring. The way you have your code written, you're assuming that all numbers are one digit. What happens if the input has more than one digit??? I suggest that you use the split() for reading input


      • 2
        andrew498  commented on Aug. 3, 2015, 12:02 a.m.

        Wow, I had completely overlooked that haha. Thank you so much!