Problem Description
A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.
In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

Input
There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

Output
The output contains one line for each data set, formatted as shown in the sample output.

Sample Input
4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1

Sample Output
The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.

1个回答

【秋】【春】【秋】【春】【秋】【春】【秋】【春】【秋】【春】

Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.

Problem Description A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall. In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue. Input There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above. Output The output contains one line for each data set, formatted as shown in the sample output. Sample Input 4 6 cs123 mt42 cs456 cs789 mt42 F 0 cs123 S 0 cs456 S 2 cs123 mt42 cs789 B 1 cs456 3 6 math1 comp2 comp3 comp3 S 1 comp2 math1 S 0 comp2 F 1 math1 4 3 m10 m20 c33 c44 m10 B 0 m20 B 0 c33 B 0 c44 B 0 -1 -1 Sample Output The minimum number of semesters required to graduate is 5. The minimum number of semesters required to graduate is 4. The minimum number of semesters required to graduate is 2.
Code Permutations 写法问题
Gauss Elimination 高斯消去问题
Problem Description Li Zhixiang have already been in “Friendship” ocean-going freighter for three months. The excitement has gradually disappeared. He stands on the board, holding the railing and watching the dazzling ocean in the sun silently. Day after day, the same scenery is monotonous and tasteless, even the merry seagulls following the freighter cannot arouse his interest. Hearing the footsteps behind, he turns back to see the old captain is coming towards him. The captain has understood his idea, however, he starts a new topic with the young man. “Do you know how far our voyage is?” The captain asks. Li Zhixiang feels ashamed because he can not answer. Then the captain says with a smile, “5050 miles. Do you still remember the story of 5050?” This time the young man really blushes. The old captain continues saying:” You definitely know the story of 5050. When the German mathematician, “the prince of mathematicians”, Gauss was 10 years old …” Young man remembers this story and goes on to tell, “ When Gauss was 10 years old, he could add a list of integers from 1 to 100 in a few seconds, which shocked the teachers.” The old captain adds, “Gauss has many other stories like this. When he entered the university at the age of 17, he was able to construct heptadecagon by compass and straightedge. His university teachers were also impressed by his ability. Not only could college graduate students fail to do it, but also they felt hard to understand Gauss’s constructing process.” At this time, vice-captain greets the old captain. The old captain says to Li Zhixiang: “Come over to my office tonight, let’s continue the conversation.” It is still calm and tranquil in the evening. The freighter travels smoothly on the sea in the silver moonlight. The captain tells the young man the following words. Among the mathematicians through the ages, there are three greatest mathematicians: Archimedes, Newton and Gauss. Most of Gauss’s mathematical achievements are difficult to understand. Nevertheless, there are some comparatively easy. For instance, when it comes to solving multivariate system of linear equations, there is a solution called “Gauss Elimination”. In the navigation business, many problems can be solved by “Gauss elimination”. If you are interested in it, I will show you a simple question. Try it.” Input There are several test cases. In the first line of each case, a number n indicates that there are n equations. The following n lines, each line has n+1 numbers, ai1,ai2,ai3…..ain, bi(1<= i <=n), these numbers indicate the coefficients of systems of the equations. ai1*x1+ai2*x2+......ain*xn=bi. Input is terminated by the end of file. Output For each given systems of equations, if there are solutions, output n solutions in the order of appearance in the equations（n<=100）, each solution number is in one line. If solution is not integer, show it in fraction. If no solution, output “No solution.” Leave a blank line after each case. Sample Input 2 1000000000000000000000000 1000000000000000000000000 1000000000000000000000000 -1000000000000000000000000 1000000000000000000000000 0 1 0 4 Sample Output 1/2 1/2 No solution.
Sokoban 是怎么计算的
Problem Description Soko-ban is a Japanese word for a warehouse worker, and the name of a classic computer game created in the 1980s. It is a one-player game with the following premise. A single worker is in an enclosed warehouse with one or more boxes. The goal is to move those boxes to a set of target locations, with the number of target locations equalling the number of boxes. The player indicates a direction of motion for the worker using the arrow keys (up, down, left, right), according to the following rules. 1.If the indicated direction of motion for the worker leads to an empty location (i.e., one that does not have a box or wall), the worker advances by one step in that direction. 2.If the indicated direction of motion would cause the worker to move into a box, and the location on the other side of the box is empty, then both the worker and the box move one spot in that direction (i.e., the worker pushes the box). 3.If the indicated direction of motion for a move would cause the worker to move into a wall, or to move into a box that has another box or a wall on its opposite side, then no motion takes place for that keystroke. The goal is to simultaneously have all boxes on the target locations. In that case, the player is successful (and as a formality, all further keystrokes will be ignored). The game has been studied by computer scientists (in fact, one graduate student wrote his entire Ph.D. dissertation about the analysis of sokoban). Unfortunately, it turns out that finding a solution is very difficult in general, as it is both NP-hard and PSPACE-complete. Therefore, your goal will be a simpler task: simulating the progress of a game based upon a player's sequence of keystrokes. For the sake of input and output, we describe the state of a game using the following symbols: For example, the initial configuration diagrammed at the beginning of this problem appears as the first input case below. Input Each game begins with a line containing integers R and C, where 4 ≤ R ≤ 15 represents the number of rows, and 4 ≤ C ≤ 15 represents the number of columns. Next will be R lines representing the R rows from top to bottom, with each line having precisely C characters, from left-to-right. Finally, there is a line containing at most 50 characters describing the player's sequence of keystrokes, using the symbols U, D, L, and R respectively for up, down, left, and right. You must read that entire sequence from the input, even though a particular game might end successfully prior to the end of the sequence. The data set ends with the line 0 0. We will guarantee that each game has precisely one worker, an equal number of boxes and locations, at least one initially misplaced box, and an outermost boundary consisting entirely of walls. Output For each game, you should first output a line identifying the game number, beginning at 1, and either the word complete or incomplete, designating whether or not the player successfully completed that game. Following that should be a representation of the final board configuration. Sample Input 8 9 ######### #...#...# #..bb.b.# #...#w#.# #...#b#.# #...++++# #...#..## ######### ULRURDDDUULLDDD 6 7 ####### #..#### #.+.+.# #.bb#w# ##....# ####### DLLUDLULUURDRDDLUDRR 0 0 Sample Output Game 1: incomplete ######### #...#...# #..bb...# #...#.#.# #...#.#.# #...+W+B# #...#b.## ######### Game 2: complete ####### #..#### #.B.B.# #.w.#.# ##....# #######
GRE Words 单词的程序设计
Problem Description Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words. Now George is working on a word list containing N words. He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember. So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn't want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word. Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence. Input The first line contains an integer T(1 <= T <= 50), indicating the number of test cases. Each test case contains several lines. The first line contains an integer N(1 <= N <= 2 * 104), indicating the number of words. Then N lines follows, each contains a string Si and an integer Wi, representing the word and its importance. Si contains only lowercase letters. You can assume that the total length of all words will not exceeded 3 * 105. Output For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is the largest importance of the remaining sequence of words. Sample Input 1 5 a 1 ab 2 abb 3 baba 5 abbab 8 Sample Output Case #1: 14

《奇巧淫技》系列-python！！每天早上八点自动发送天气预报邮件到QQ邮箱

YOLO 是我非常喜欢的目标检测算法，堪称工业级的目标检测，能够达到实时的要求，它帮我解决了许多实际问题。 这就是 YOLO 的目标检测效果。它定位了图像中物体的位置，当然，也能预测物体的类别。 之前我有写博文介绍过它，但是每次重新读它的论文，我都有新的收获，为此我准备写一个系列的文章来详尽分析它。这是第一篇，从它的起始 YOLOv1 讲起。 YOLOv1 的论文地址：https://www.c...

20行Python代码爬取王者荣耀全英雄皮肤

2019年互联网寒冬，大批企业开始裁员，下图是网上流传的一张截图： 裁员不可避免，那如何才能做到不管大环境如何变化，自身不受影响呢？ 我们先来看一个有意思的故事，如果西游记取经团队需要裁员一名，会裁掉谁呢，为什么？ 西游记团队组成： 1.唐僧 作为团队teamleader，有很坚韧的品性和极高的原则性，不达目的不罢休，遇到任何问题，都没有退缩过，又很得上司支持和赏识(直接得到唐太宗的任命，既给袈...
Python语言高频重点汇总
Python语言高频重点汇总 GitHub面试宝典仓库 回到首页 目录： Python语言高频重点汇总 目录： 1. 函数-传参 2. 元类 3. @staticmethod和@classmethod两个装饰器 4. 类属性和实例属性 5. Python的自省 6. 列表、集合、字典推导式 7. Python中单下划线和双下划线 8. 格式化字符串中的%和format 9. 迭代器和生成器 10...

ES6基础-ES6的扩展

Python爬虫爬取淘宝，京东商品信息

Java工作4年来应聘要16K最后没要,细节如下。。。

Python爬虫精简步骤1 获取数据

CPU对每个程序员来说，是个既熟悉又陌生的东西？ 如果你只知道CPU是中央处理器的话，那可能对你并没有什么用，那么作为程序员的我们，必须要搞懂的就是CPU这家伙是如何运行的，尤其要搞懂它里面的寄存器是怎么一回事，因为这将让你从底层明白程序的运行机制。 随我一起，来好好认识下CPU这货吧 把CPU掰开来看 对于CPU来说，我们首先就要搞明白它是怎么回事，也就是它的内部构造，当然，CPU那么牛的一个东

2020年1月17日，国家统计局发布了2019年国民经济报告，报告中指出我国人口突破14亿。 猪哥的朋友圈被14亿人口刷屏，但是很多人并没有看到我国复杂的人口问题：老龄化、男女比例失衡、生育率下降、人口红利下降等。 今天我们就来分析一下我们国家的人口数据吧！ 更多有趣分析教程，扫描下方二维码关注vx公号「裸睡的猪」 即可查看！ 一、背景 1.人口突破14亿 2020年1月17日，国家统计局发布
web前端javascript+jquery知识点总结
Javascript javascript 在前端网页中占有非常重要的地位，可以用于验证表单，制作特效等功能，它是一种描述语言，也是一种基于对象（Object）和事件驱动并具有安全性的脚本语言 ，语法同java类似，是一种解释性语言，边执行边解释。 JavaScript的组成： ECMAScipt 用于描述: 语法，变量和数据类型，运算符，逻辑控制语句，关键字保留字，对象。 浏览器对象模型（Br
Qt实践录：开篇

B 站上有哪些很好的学习资源?

Web播放器解决了在手机浏览器和PC浏览器上播放音视频数据的问题，让视音频内容可以不依赖用户安装App，就能进行播放以及在社交平台进行传播。在视频业务大数据平台中，播放数据的统计分析非常重要，所以Web播放器在使用过程中，需要对其内部的数据进行收集并上报至服务端，此时，就需要对发生在其内部的一些播放行为进行事件监听。 那么Web播放器事件监听是怎么实现的呢？ 01 监听事件明细表 名
3万字总结，Mysql优化之精髓

1. 传统事件绑定和符合W3C标准的事件绑定有什么区别？ 传统事件绑定 &lt;div onclick=""&gt;123&lt;/div&gt; div1.onclick = function(){}; &lt;button onmouseover=""&gt;&lt;/button&gt; 注意： 如果给同一个元素绑定了两次或多次相同类型的事件，那么后面的绑定会覆盖前面的绑定 （不支持DOM事...
Python学习笔记（语法篇）

[Pyhon疫情大数据分析] 一.腾讯实时数据爬取、Matplotlib和Seaborn可视化分析全国各地区、某省各城市、新增趋势