CCC '15 S2 - Jerseys
View as PDFCanadian Computing Competition: 2015 Stage 1, Senior #2
A school team is trying to assign jerseys numbered 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 which is the number of jerseys.
The second line of input is the integer which is the number of athletes.
The next lines are each the character
S, M or L. Line gives the size of jersey
(
).
The last lines are each the character
S, M or L followed by a space, followed by an integer. Line (
) gives the requested size and jersey number for athlete
where the athletes are numbered
.
For 50% of the test cases, and
.
For the remaining 50% of the test cases, and
.
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 1Output for Sample Input
1Explanation of Output for Sample Input
Jersey cannot be assigned because it is medium and athlete
requested large. No athlete requested jersey
or
. Jersey
, can be assigned to athlete
, but not athlete
.
Comments
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.
I think i'm blind i just wasted an hour thinking the size had to be exactly what they wanted
same. But I stuck for a whole week
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"
yeah, unfortunately most coding questions are like that
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
just try to make your code more efficient. You can solve this question with python for sure!
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).
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).
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
Wow, I had completely overlooked that haha. Thank you so much!