{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"A project can be divided into several parts. Each part should be completed continuously. \nThis means if a part should take 3 days, we should use a continuous 3 days do \ncomplete it. There are four types of constrains among these parts which are FAS, \nFAF, SAF and SAS. A constrain between parts is FAS if the first one should finish \nafter the second one started. FAF is finish after finish. SAF is start after finish, \nand SAS is start after start. Assume there are enough people involved in the projects, \nwhich means we can do any number of parts concurrently. You are to write a program \nto give a schedule of a given project, which has the shortest time. \n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eInput\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n The input file consists a sequences of projects.\u003c/p\u003e\n\u003cp\u003eEach project consists the following lines:\u003c/p\u003e\n\u003cp\u003ethe count number of parts (one line) (0 for end of input)\u003cbr\u003e\n \u003cbr\u003e\n times should be taken to complete these parts, each time occupies one line\u003cbr\u003e\n \u003cbr\u003e\n a list of FAS, FAF, SAF or SAS and two part number indicates a constrain of \n the two parts\u003cbr\u003e\n \u003cbr\u003e\n a line only contains a \u0027#\u0027 indicates the end of a project\n\u003c/p\u003e\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n Output should be a list of lines, each line includes a part number and the time \n it should start. Time should be a non-negative integer, and the start time of \n first part should be 0. If there is no answer for the problem, you should give \n a non-line output containing \"impossible\".\u003c/p\u003e\n\u003cp\u003eA blank line should appear following the output for each project.\u003cbr\u003e\n \u003cbr\u003e\n\u003c/p\u003e\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n 3\u003cbr\u003e\n 2\u003cbr\u003e\n 3\u003cbr\u003e\n 4\u003cbr\u003e\n SAF 2 1\u003cbr\u003e\n FAF 3 2\u003cbr\u003e\n #\u003cbr\u003e\n 3\u003cbr\u003e\n 1\u003cbr\u003e\n 1\u003cbr\u003e\n 1\u003cbr\u003e\n SAF 2 1\u003cbr\u003e\n SAF 3 2\u003cbr\u003e\n SAF 1 3\u003cbr\u003e\n #\u003cbr\u003e\n 0\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003eSample Output\u003c/b\u003e\u003cbr\u003e\n \u003cbr\u003e\n Case 1:\u003cbr\u003e\n 1 0\u003cbr\u003e\n 2 2\u003cbr\u003e\n 3 1\u003c/p\u003e\n\u003cp\u003eCase 2:\u003cbr\u003e\n impossible\u003cbr\u003e\n\u003c/p\u003e\n"}}]}