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 of Output for Sample Input

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


  • -1
    mediocre  commented on Oct. 30, 2022, 9:54 p.m.

    I solved the problem but I'm wondering why I IR'd with my initial correct solution. Everything looks right in the latest submission with the IR. I also don't IR on case 1 and 3.


  • 3
    kujiyh  commented on Feb. 17, 2021, 11:20 p.m.

    I think i'm blind i just wasted an hour thinking the size had to be exactly what they wanted


    • 6
      DNKYrr  commented on April 5, 2021, 8:01 p.m.

      same. But I stuck for a whole week


  • 26
    orangewave  commented on Jan. 19, 2020, 8:35 p.m.

    I thought the requested jersey number referred to the number they wanted on the back of their jersey (player number) and I spent about an hour creating a solution, only to realize it was referring to the specific jersey they wanted.

    "Each athlete has requested a specific jersey number and a preferred size" I think this question is poorly worded. I feel like it should just be: "Each athlete has requested a specific jersey and a preferred size"


    • 3
      anonymous69  commented on Sept. 6, 2022, 3:20 p.m.

      yeah, unfortunately most coding questions are like that


  • 1
    P234rex  commented on Nov. 8, 2016, 3:34 a.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


    • 2
      1369738647  commented on Aug. 29, 2018, 10:46 p.m.

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


    • 3
      Xyene  commented on Nov. 8, 2016, 5: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).


  • 4
    andrew498  commented on July 31, 2015, 7: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).


    • 6
      lKunelk  commented on Aug. 1, 2015, 3:41 p.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


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

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