3275 - I2P(I)2025_Chou_Hu_Hw8_ClassA Scoreboard

Time

2025/11/24 20:30:00 2025/12/01 18:30:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team
# Problem Pass Rate (passed user / total user)
14838 May I take your order
14845 File Tree

14838 - May I take your order   

Status  |  Limits Submit

Description

Elfnt is hungry and wants to order a delicious tree for breakfast.

Since it’s breakfast, the waiter needs the tree’s pre-order as the meal code.

However, elfnt has forgotten the pre-order.

Fortunately, he still remembers the tree’s in-order and post-order.

Please help elfnt reconstruct the pre-order so he can enjoy his breakfast.

Hint: Try to use the given information to find the size of left and right subtree. Then do the recursion to find the answer.

Input

  • The first line contains $n$ integers -- the in-order of the tree.
  • The second line contains $n$ integers -- the post-order of the tree.

Constraints

  • $1 \le n \le 1000$
  • The tree contains n distinct nodes, labeled $1$ to $n$.
  • The input is guaranteed to describe a valid binary tree.

Output

Print the pre-order of the tree, each number followed by a space (including the last one).

No \n at the end.

Sample Input  Download

Sample Output  Download




Discuss




14845 - File Tree   

Status  |  Limits Submit

Description

Terminology

  • A file tree is a tree structure that organizes files and directories (folders).
  • At the top, there is a special directory called the root directory, written as /.
  • Current working directory, means the directory you are currently at.
  • A path describes how to reach a file or a directory, you can refer to 02-basic-computing page 13 for more information about absolute path and relative path.

Task description

  • You have to implement a file tree.
  • You start from an empty file tree that only has a single root directory /.
  • You will then receive a sequence of commands, and you need to process the commands in order, update the file tree, and print the outputs of some commands.

Notices

  • EXAMPLE in the following decription are the extra sample. You can test them manualy by setting DEBUG_MODE to True.
    • The command after > is the input.
    • The path before > is the current working directory.
  • All the PATH mentioned in the following can be an absolute path or a relative path.
  • We have modified or simplified some commands for convenience, so some details might be different from the the os module or a real file system, try not to mix them up.

TODO function

  • path_to_nodes(PATH)
    • Given a path, you have to return the absoulte path in a list of nodes List[Node].
    • If PATH does not exist, return None.

TODO commands

  • cd PATH
    • Functionality:
      • Change the current working directory to PATH.
    • Exception:
      • If PATH does not exist or is not a directory, do nothing.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      /A/C
      Commands start here:
      / > cd ..                # Already in /, do nothing
      / > cd ./A 
      /A > cd B
      /A/B > cd ..
      /A > cd /D                     # Directory D does not exist, do nothing
      /A > cd /A/C
      /A/C >
  • ls
    • Functionality:
      • Print the names of all direct children (files and directories) in lexicographical order in a single line.
      • Every names are separated by a single space (No additional space after last one).
    • Exception:
      • If the directory is empty, print an empty line.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      /A/e
      /A/Z
      Commands start here:
      / > ls
      A
      / > cd A
      /A > ls
      B Z e
      /A > cd B
      /A/B > ls

      /A/B >
  • touch PATH
    • PATH can be decomposed into {PARENT_PATH, FILE_NAME}.
    • Functionality:
      • Create a file named FILE_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH  does not exist or is not a directory, do nothing.
      • If a file or a directory named FILE_NAME already exists under PARENT_PATH directory, do nothing.

    • EXAMPLE

    • Current existing directories:
      /
      /A
      /A/B
      Commands start here:
      / > cd A
      /A > touch hi             #       File /A/hi is created
      /A > touch /A/B/sus       # File /A/B/sus is created
      /A > touch /C/no          # /C does not exist, do nothing
  • rm PATH
    • PATH can be decomposed into {PARENT_PATH, FILE_NAME}
    • Functionality:
      • Remove a file named FILE_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
      • If FILE_NAME does not exists under PARENT_PATH directory, do nothing.

    • EXAMPLE

    • Current existing directories and files:
      /
      /A
      /A/B
      /A/f (file)
      /A/g (file)
      Commands start here:
      / > cd A
      /A > rm /A/f             # File /A/f is removed
      /A > rm ./g              #       File /A/g is removed
      /A > rm B                # /A/B is not a file, do nothing

Template

  • class Node
    • Each node represents a directory or a file in the file tree.
  • mkdir PATH
    • PATH can be decomposed into {PARENT_PATH, DIR_NAME}
    • Functionality:
      • Create a directory named DIR_NAME under PARENT_PATH directory.
    • Exception:
      • If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
      • If a file or a directory named DIR_NAME already exists under PARENT_PATH directory, do nothing.
import sys

class Node:
    def __init__(self, name, is_dir, parent=None):
        self.name = name
        self.is_dir = is_dir
        self.parent = parent
        self.children = {}

class FileTree:
    def __init__(self):
        self.root = Node("/", True, None)
        self.cwd = self.root
   
    # !!! You can add more functions if needed !!! #
   
    def path_to_nodes(self, path):
        # TODO
        pass

    def mkdir(self, path):
        if path.endswith('/') and len(path) > 1:
            path = path[:-1]
        idx = path.rfind('/')
        if idx == -1:
            p_path, name = ".", path
        elif idx == 0:
            p_path, name = "/", path[1:]
        else:
            p_path, name = path[:idx], path[idx+1:]
        nodes = self.path_to_nodes(p_path)
        if nodes:
            parent = nodes[-1]
            if parent.is_dir and name not in parent.children:
                parent.children[name] = Node(name, True, parent)

    def cd(self, path):
        # TODO
        pass

    def ls(self):
        # TODO
        pass

    def touch(self, path):
        # TODO
        pass

    def rm(self, path):
        # TODO
        pass

    # Debug functions
    def print_prompt(self):
        nodes = self.path_to_nodes(".")
        path_str = "/" + "/".join([n.name for n in nodes[1:]])
        if path_str.endswith("/") and len(path_str) > 1: path_str = path_str[:-1]
        print(f"{path_str} >", end=" ", flush=True)

    def print_all(self, node=None, prefix=""):
        if node is None: node, prefix = self.root, ""
        current = prefix + ("/" + node.name if node != self.root else "")
        print(current if node.is_dir else f"{current} (file)")
        if node.is_dir:
            for k in sorted(node.children): self.print_all(node.children[k], current)

def main():
    ft = FileTree()
    # !!! Enable debug mode here !!!
    # !!! Remember to disable it when submitting !!!
    DEBUG_MODE = True
    
    while True:
        if DEBUG_MODE: ft.print_prompt()
        try:
            line = sys.stdin.readline()
            if not line:
                if DEBUG_MODE: print()
                break
        except: break

        line = line.strip()
        if not line: continue

        p = line.split()
        cmd, args = p[0], p[1:]

        if   cmd == 'mkdir' and len(args)==1: ft.mkdir(args[0])
        elif cmd == 'cd'    and len(args)==1: ft.cd(args[0])
        elif cmd == 'ls'    and len(args)==0: ft.ls()
        elif cmd == 'touch' and len(args)==1: ft.touch(args[0])
        elif cmd == 'rm'    and len(args)==1: ft.rm(args[0])
        elif cmd == 'print_all':              ft.print_all()

        if DEBUG_MODE and cmd != 'ls':
            print("--- Tree ---"); ft.print_all(); print("------------")

if __name__ == "__main__":
    main()

​

Input

  • Each line contains a single command.
  • Command names and arguments are separated by a single space.
  • Paths never contain spaces.
  • File and directory names consist only of letters and digits.
  • Input is read until EOF.

Output

Only the following command produce output:

  • ls
    • Print the names of all direct children (files and directories) in lexicographical order.
    • Print all names on one line, separated by a single space. (No additional space after last one)
    • If the directory is empty, print an empty line.

Sample Input  Download

Sample Output  Download




Discuss