Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
67 - ZOJ Monthly, June 2008 - 1007
Software Installer

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Background

Software is composed of several packages and other software. A package can also be shared by some software. The only difference between software and package is that in one hand, package is the basic unit while software is not, in the other hand software can run directly while package can not.

Problem

Your task is to write a program to install or uninstall software and not influence other software's normal function.
For example, there is 3 software s1,s2,s3 and 6 packages p1,p2,p3,p4,p5,p6. The dependency is as follows:
s1 depends on p1,p2,p3,p4.
s2 depends on p2 and p5,
s3 depends on p1 p6 and s2.

If you want to install s1, you need to install p1, p2, p3 and p4.
Then you try to install s3, you need to install p6 and s2 (p1 has been already installed) in the order of dependency.(just out put "install p6 s2" instead of "install p6 p5")
You will fail to uninstall s2, because it is used by s3.
If you want to uninstall s3, you only need to uninstall p6.
At last, if you try to uninstall s1, you have to uninstall p1, p2, p3, and p4.

Input

The input contains several cases .In each case, there are three parts.
1. First part tells you names of all the software and packages .It contains two lines. In first line, there is an integer s (1<=s<=100) and s software's name separated by spaces. In second line, there is an integer p(1<=p<=1000) and p packages' name separated by spaces.
2. Second part tells you the dependency of all the software. It contains s line. The ith line contains an integer n, following n packages/software, which the ith software need.
3.Third part tells you the tasks to perform.
First line contains T(1<=T<=200), the number of tasks, following T lines of commands .Each command's format is "install/uninstall s", where s is the name of software. All the commands will be performed in order.

The length of the input string is no more than 255 characters. I recommend that you use C function "scanf" and "printf" instead of C++ stream "cin" and "cout" to speed up your program.
Of course there will be no cyclic dependency.

Output

For each case, output "case #i:" where i is the number of case, starting at 1.
Output one line for each task:
1. If the software is unknown, output "s is not found ", where s is the name of software.
2. For commands of install, if the software has been already installed, output "s has been already installed", where s is the name of software, else output "install", following names of software and packages need to install by the order of input.
3. for commands of uninstall, if the software has been already uninstalled, output "s has been already uninstalled", where s is the name of software.
If the software is still used by others, output "uninstall failed: s is used by other software", where s is the name of software, else output "uninstall", following names of software and packages need to uninstall by the order of input.
Every two strings should be separated by a single space.
Output one blank line after each case.

Sample Input

3 s1 s2 s3
6 p1 p2 p3 p4 p5 p6
4 p1 p2 p3 p4
2 p2 p5
3 p1 p6 s2
10
install s1
install s3
install s2
install s3
install s5
uninstall s3
uninstall s2
uninstall s1
uninstall s1
uninstall s5
3 s1 s2 s3
6 p1 p2 p3 p4 p5 p6
4 p1 p2 p3 p4
2 p2 p5
3 p1 p6 s2
5
install s1
install s3
uninstall s3
uninstall s1
uninstall s2

Sample Output

case 1:
install p1 p2 p3 p4
install p6 s2
s2 has been already installed
s3 has been already installed
s5 is not found
uninstall p6
uninstall p5
uninstall p1 p2 p3 p4
s1 has been already uninstalled
s5 is not found

case 2:
install p1 p2 p3 p4
install p6 s2
uninstall p6
uninstall p1 p3 p4
uninstall p2 p5

Author: LUO. Yan


Submit    Status