King Arthur II has problems with pronouncing the digit 3. People are afraid of presenting something which includes 3 in it. The solution found is that if any number includes 3 as a digit, the number is divided by 2. This process continues as far as the new numbers include new 3s.
You are working as assistant director in South East Town School and you need to present information to the King. In the brief, you will show top k students according to the graduation exam results. However, if the King Arthur II wants to see the entire list, you are to show the entire list. So, you need to make sure that no student grades includes 3 in it.
Question: Write a program that will get n students information. You will show top k student information, after preparing "the proper list” ☺
Input specification
First you will be given two integers (n) the number of students and (k) the top students to show in your brief where 1 ≤ n ≤ 40,000 and 1 ≤ k ≤ 10,000. Then in the following n lines you will be given n student information. Every line has:
• ID of student: an integer between 1 and 1e6
• Name and surname of the student: at most 50 char including English letters and digits and and space. Some students might have middle names. Name and surname ends with a semicolon.
• Grade point of student: an integer less than 10,000
Output specification
Show name surname and grades of top k students. If two students have the same points, the student with the greater ID comes first.
Sample Input I
6 3
5 Thelma Campbell; 243
7 Brenda Gordon; 315
9 Pablo Mathis; 1454
12 Lila Sullivan; 89
15 Tasha Angelo Moss; 536
17 Michael Davis; 1693 Sample Output I
Pablo Mathis 1454
Michael Davis 846
Tasha Angelo Moss 268
Explanation: Here is the list after processing and sorting.
• Pablo Mathis 1454
• Tasha Angelo Moss 268
• Michael Davis 168
• Brenda Gordon 157
• Thelma Campbell 121
• Lila Sullivan 89
To solve this problem, we need to follow these steps:
1. Read the input values: First, we need to read the values of n and k from the input. These values represent the number of students and the number of students to be shown in the brief, respectively.
2. Read the student information: Next, we need to read the information of each student. Each student's information consists of their ID, name and surname, and grade point. We will store this information in a suitable data structure, such as a list of dictionaries.
3. Filter out students with a grade point containing the digit 3: For each student, we need to check if their grade point contains the digit 3. If it does, we will divide the grade point by 2 until there are no more 3s in the number.
4. Sort the students based on their grade point: Once we have filtered out the students with a grade point containing the digit 3, we need to sort the remaining students based on their grade points. If two students have the same grade point, we will compare their IDs to determine the order.
5. Show the top k students' information: Finally, we need to display the information of the top k students in the brief. We will print their name, surname, and grade points in the desired format.
Here is a Python implementation of the above steps:
```python
# Step 1: Read the input values
n, k = map(int, input().split())
# Step 2: Read the student information
students = []
for _ in range(n):
student_info = input().split(";")
student_id = int(student_info[0])
name_surname = student_info[1]
grade_point = int(student_info[2].strip())
students.append({"id": student_id, "name_surname": name_surname, "grade_point": grade_point})
# Step 3: Filter out students with a grade point containing the digit 3
filtered_students = []
for student in students:
grade_point = student["grade_point"]
while "3" in str(grade_point):
grade_point = grade_point // 2
filtered_students.append({"id": student["id"], "name_surname": student["name_surname"], "grade_point": grade_point})
# Step 4: Sort the students based on their grade point
sorted_students = sorted(filtered_students, key=lambda s: (s["grade_point"], -s["id"]), reverse=True)
# Step 5: Show the top k students' information
for i in range(k):
student = sorted_students[i]
print(student["name_surname"], student["grade_point"])
```
Note: This solution assumes that the input values are valid and follow the specified format. Error handling and input validation can be added for production use.