主观题：Professional Ability Test
Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a **prerequisite** of Level B if one must pass Level A with a score no less than $$S$$ in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than $$S$$ will receive a voucher（代金券）of $$D$$ yuans (Chinese dollar) for taking Level B.
At the moment, this PAT is only in design and hence people would make up different plans. A plan is **NOT** consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total $$S$$) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$N$$ ($$\le 1000$$) and $$M$$, being the total numbers of tests and prerequisite relations, respectively. Then $$M$$ lines follow, each describes a prerequisite relation in the following format:
T1 T2 S D
where T1 and T2 are the indices (from 0 to $$N-1$$) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.
Then another positive integer $$K$$ ($$\le N$$) is given, followed by $$K$$ queries of tests. All the numbers in a line are separated by spaces.
### Output Specification:
Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.
If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:
T0->T1->...->T
However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.
If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.
### Sample Input 1:
in
8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7
### Sample Output 1:
out
Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7
### Sample Input 2:
in
4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1
### Sample Output 2:
out
Impossible.
You may take test 3 directly.
Error.
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
At the moment, this PAT is only in design and hence people would make up different plans. A plan is **NOT** consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total $$S$$) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$N$$ ($$\le 1000$$) and $$M$$, being the total numbers of tests and prerequisite relations, respectively. Then $$M$$ lines follow, each describes a prerequisite relation in the following format:
T1 T2 S D
where T1 and T2 are the indices (from 0 to $$N-1$$) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.
Then another positive integer $$K$$ ($$\le N$$) is given, followed by $$K$$ queries of tests. All the numbers in a line are separated by spaces.
### Output Specification:
Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.
If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:
T0->T1->...->T
However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.
If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.
### Sample Input 1:
in
8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7
### Sample Output 1:
out
Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7
### Sample Input 2:
in
4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1
### Sample Output 2:
out
Impossible.
You may take test 3 directly.
Error.
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
