Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
68 - ZOJ Monthly, July 2008 - 1002
Directory Tree

Time Limit: 2 Seconds      Memory Limit: 65536 KB

In the ZIP archive, it maintains the relative path and name of all the compressed files and directories in it. When the GUI software(such as WinZIP) opens the archive, it can reconstruct the tree structure from these information. Now it's your task to write a program to do the job.

Input

The input have multiple cases.
In each test case, the first line is a number N (1<=N<=20000), indicating the number of files and directories in the ZIP archive.
Then n lines follows, each line has the relative path and name of the file or directory(each line has no more than 260 characters).

Notice:
1.The ASCII value of all the characters in the path and file name lies in [0x20,0x7F]. And the following characters will not appear in the path and file name:'/:*?"<>|'. '\' is only used as path delimiter.
2.The path and name is case-sensitive.
3.Directory is ended by '\'.
4.There will not be duplicated items in the input.
5.The size of whole input will not exceeds 2MB.

Output

Assume all the paths are relative to the 'root' directory. Start from the root directory, for each directory, first output its name, then output all the subdirectories recursively in alphabatic order, then output all the files in it alphabatically.
Notice:To make the tree look nice, before printing the name, you should first output n leading tabs('\t') according to its level relative to the root directory(for example, you should output one tab if the file is in the 'root' folder and output two tabs if it is in the subdirectories of the 'root' folder).

To keep the size of output, you are not required to output the tree directly. Just output its 'hash' which is defined as:

unsigned int Hash(const char *Key) {
	unsigned int HashVal=0,i=1;
	while (*Key) {
		HashVal+=(*Key++)*(i++);
		HashVal%=0x8000000B;
		HashVal*=0xFFFFFFEF;
	}
	return HashVal;
}

Notice: cin and cout is not recommended here, use them at your own risk~

Sample Input

6
b
c\
ab\cd
a\bc
ab\d
a\d\a

Sample Output

966637654

(Hint:
The directory tree is as follows:

root
	a
		d
			a
		bc
	ab
		cd
		d
	c
	b

and 966637654=hash("root\n\ta\n\t\td\n\t\t\ta\n\t\tbc\n\tab\n\t\tcd\n\t\td\n\tc\n\tb\n")

Author: FAN, Xiang


Submit    Status