CF66C.Petya and File System
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Recently, on a programming lesson little Petya showed how quickly he can create files and folders on the computer. But he got soon fed up with this activity, and he decided to do a much more useful thing. He decided to calculate what folder contains most subfolders (including nested folders, nested folders of nested folders, and so on) and what folder contains most files (including the files in the subfolders).
More formally, the subfolders of the folder are all its directly nested folders and the subfolders of these nested folders. The given folder is not considered the subfolder of itself. A file is regarded as lying in a folder, if and only if it either lies directly in this folder, or lies in some subfolder of the folder.
For a better understanding of how to count subfolders and files for calculating the answer, see notes and answers to the samples.
You are given a few files that Petya has managed to create. The path to each file looks as follows:
diskName:\_folder_1\_folder_2\...\ folder__n\fileName
- diskName is single capital letter from the set {C,D,E,F,G}.
- _folder_1, ..., folder__n are folder names. Each folder name is nonempty sequence of lowercase Latin letters and digits from 0 to 9. (n ≥ 1)
- fileName is a file name in the form of name.extension, where the name and the extension are nonempty sequences of lowercase Latin letters and digits from 0 to 9.
It is also known that there is no file whose path looks like diskName:\fileName. That is, each file is stored in some folder, but there are no files directly in the root. Also let us assume that the disk root is not a folder.
Help Petya to find the largest number of subfolders, which can be in some folder, and the largest number of files that can be in some folder, counting all its subfolders.
最近,在一节编程课上,小彼得亚展示了他创建文件和文件夹的惊人速度。但他很快对这项活动感到厌倦,转而决定做一件更有意义的事情:他想计算出包含最多子文件夹(包括嵌套的子文件夹、子文件夹的子文件夹,依此类推)的文件夹,以及包含最多文件(包括其所有子文件夹中的文件)的文件夹。
更形式化地定义如下:
一个文件夹的子文件夹,是指它所有直接嵌套的子文件夹,以及这些直接子文件夹的所有子文件夹(递归定义)。注意:该文件夹自身不被视为自身的子文件夹。
一个文件被认为位于某文件夹中,当且仅当它直接位于该文件夹内,或位于该文件夹的某个子文件夹中。
为更清晰地理解如何统计子文件夹与文件数量以得出答案,请参阅样例的注释及答案说明。
现给出彼得亚已创建的一些文件。每个文件的路径格式如下:
_diskName_:\\_folder_1\\_folder_2\\...\\_folder__n_\\_fileName_
_diskName_是来自集合{C,D,E,F,G}中的一个大写英文字母;_folder_1, ..., _folder__n_是文件夹名,每个文件夹名是非空的、由小写拉丁字母和数字0到9组成的字符串(其中 n ≥ 1);_fileName_是形如_name_._extension_的文件名,其中_name_和_extension_均为非空的、由小写拉丁字母和数字0到9组成的字符串。
此外已知:不存在路径形如 _diskName_:\\_fileName_ 的文件。也就是说,每个文件都存放在某个文件夹中,但根目录下没有直接存放的文件。同时,我们假定磁盘根目录本身不被视为一个文件夹。
请帮助彼得亚找出:
- 某个文件夹所能拥有的最多子文件夹数;
- 某个文件夹所能拥有的最多文件数(计入其所有子文件夹中的文件)。
输入格式
Each line of input data contains the description of one file path. The length of each line does not exceed 100, and overall there are no more than 100 lines. It is guaranteed, that all the paths are correct and meet the above rules. It is also guaranteed, that there are no two completely equal lines. That is, each file is described exactly once.
There is at least one line in the input data.
每行输入数据包含一个文件路径的描述。每行长度不超过 100,且总行数不超过 100 行。保证所有路径均合法,并满足上述规则。同时保证不存在两条完全相同的行,即每个文件恰好被描述一次。
输入数据中至少包含一行。
输出格式
Print two space-separated numbers. The first one is the maximal number of possible subfolders in a folder (including nested folders, nested folders of nested folders, and so on). The second one is the maximal number of files in a folder (including nested files in subfolders). Note that the disks are not regarded as folders.
输出两个以空格分隔的数字。第一个数字表示一个文件夹中可能包含的子文件夹的最大数量(包括嵌套的子文件夹、嵌套子文件夹的子文件夹,以此类推)。第二个数字表示一个文件夹中可能包含的文件的最大数量(包括子文件夹中嵌套的文件)。注意:磁盘不被视为文件夹。
输入输出样例
输入#1
C:\folder1\file1.txt
输出#1
0 1
输入#2
C:\folder1\folder2\folder3\file1.txt C:\folder1\folder2\folder4\file1.txt D:\folder1\file1.txt
输出#2
3 2
输入#3
C:\file\file\file\file\file.txt C:\file\file\file\file2\file.txt
输出#3
4 2
说明/提示
In the first sample we have one folder on the "C" disk. It has no subfolders, which is why the first number in the answer is 0. But this folder contains one file, so the second number of the answer is 1.
In the second sample we have several different folders. Consider the "folder1" folder on the "C" disk. This folder directly contains one folder, "folder2". The "folder2" folder contains two more folders — "folder3" and "folder4". Thus, the "folder1" folder on the "C" drive has exactly 3 subfolders. Also this folder contains two files, even though they do not lie directly in the folder, but they are located in subfolders of "folder1".
In the third example we see that the names of some folders and some subfolders are identical. Consider the "file" folder, which lies directly on the "C" disk. That folder contains another "file" folder, which in turn contains another "file" folder, which contains two more folders, "file" and "file2". Thus, the "file" folder, which lies directly on the "C" disk, contains 4 subfolders.
在第一个样例中,“C”盘上有一个文件夹。该文件夹没有子文件夹,因此答案中的第一个数字为 0。但该文件夹包含一个文件,所以答案中的第二个数字为 1。
在第二个样例中,我们有多个不同的文件夹。考虑“C”盘上的“folder1”文件夹。该文件夹直接包含一个文件夹“folder2”。“folder2”文件夹又包含两个文件夹——“folder3”和“folder4”。因此,“C”盘上的“folder1”文件夹恰好有 3 个子文件夹。此外,该文件夹还包含两个文件,尽管这两个文件并不直接位于该文件夹中,而是位于“folder1”的子文件夹中。
在第三个样例中,我们看到某些文件夹及其子文件夹的名称相同。考虑直接位于“C”盘上的“file”文件夹。该文件夹包含另一个名为“file”的文件夹,而后者又包含另一个名为“file”的文件夹,该文件夹再包含两个文件夹:“file”和“file2”。因此,直接位于“C”盘上的“file”文件夹共有 4 个子文件夹。
输入解题思路,AI测评打分。不知道怎么写?