Description
The problem is not meant for analyzing the worst case time complexity of algorithms or data structures. It is more about using simple data structures as e ciently as possible and ensuring correctness of the program. There are more e cient data structures for some of these problems that we will do later, but for this lab you should use simple data structures that will work well for ‘typical’ usage.
You have to maintain a data structure to process registration data. You are given a list of courses being o ered. Each course is assigned a slot and may have an upper bound on the number of students who can register for the course. You are also given the list of students on roll.
You have to process a sequence of operations. An operation may be to register a given student for a course, drop a course from a student’s registration, print the students registered for a course, print the courses a student has registered for.
Some other operations are to nd all common students between two courses and nd common courses between two students.
There are some constraints that must be satis ed. A limit max courses will be speci ed on the maximum number of courses a student can register for. A student cannot register for two courses in the same slot. The number of students in a course cannot exceed the speci ed limit.
Input Format. The rst line of input will specify the number of courses, number of students, the maximum number of courses a student can register for, and the number of operations to be processed. The number of courses is at most 1000, number of students at most 100000, maximum number of courses a student can register for is at most 10, and the number of operations is at most 107.
The next lines will give the details of the courses. Each course is speci ed by a character string of length 6. This is followed by the slot number which is between 1 to 20 and the maximum number of registrations allowed for the course. This is -1 if there is no limit.
The next lines give the roll number of students, which are 9 character strings, one per line.
After that you are given a sequence of operations. Each operation will be speci ed in one of the following forms, one per line.
-
R rollno course
regsiter student rollno for course.
-
D rollno course
drop course from student rollno’s registration.
-
P rollno
print the courses registered for by rollno.
-
P course
print students registered for course
-
P rollno1 rollno2
1
print common courses for students rollno1 and rollno2
-
P course1 course2
print common students in courses course1 and course2.
The Output should be the outcome of each operation printed one per line, in the same order. If a registration operation is successful, print “success” else print “fail”, without quotes. Note that the operation fails if either the student or the course is invalid, or the student is already registered for the course, or one of the constraints is violated. The same holds for drop, it fails if the student is not currently registered for the course. For all print operations, print the output in lexicographically sorted order on one line separated by a space. The operations must be performed in the given order, and the result is based on the registration at the time the operation is performed.
The amount of I/O is large so use scanf/printf OR set the ags for fast I/O with cin/cout. DO NOT use both.
You will get half credit if your programs work correctly for small inputs with say 100 courses, 10000 students and 105 operations. There is no xed time limit, you should try to optimize the time that your program requires.
Submission. Submit a single le named RollNo 7.cpp.
2
