M. Mathematics society problem

Codeforces

IDCF10289M

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Nlogonia secret mathematics society helds meetings with distinguished members that are able to solve a given mathematical problem. Being one of the most prestigious mathematics societies in the region you want to participate in the meeting, they discuss in this meetings a lot of interesting problems and their solutions, and therefore, it could be also a very good place to train your algorithmic skills. The problem to be invited to the next meeting has been posted, last month meeting they used an interesting problem that generated long lists of numbers. This time, they want you to work with some of these numbers. They will give you a number $N$ that contains only digits from $1$ to $9$, your task is to remove a specified amount of each digit from $N$ and get the biggest possible number. Will you be able to join this month meeting? The first line of input contains a number $N$, $N$ will have at most $1000$ digits. The second and last line of input contains $9$ integer numbers separated by a space, where the $i$-th number represents the amount of times the digit $i$ should be removed from $N$. It is guaranteed that no digit should be removed more times than it appears in $N$, and that in no case all digits from $N$ should be removed. Output a line containing a number, representing the biggest number you can get after removing the specified digits from $N$. ## Input The first line of input contains a number $N$, $N$ will have at most $1000$ digits. The second and last line of input contains $9$ integer numbers separated by a space, where the $i$-th number represents the amount of times the digit $i$ should be removed from $N$. It is guaranteed that no digit should be removed more times than it appears in $N$, and that in no case all digits from $N$ should be removed. ## Output Output a line containing a number, representing the biggest number you can get after removing the specified digits from $N$. [samples]

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case, let $ n \in \mathbb{Z}^+ $ be the number of nodes, and let $ P = (p_1, p_2, \dots, p_n) $ and $ Q = (q_1, q_2, \dots, q_n) $ be the preorder and postorder traversal sequences of a binary tree, respectively, where all elements are distinct. **Constraints** 1. $ 1 \le T \le 10^5 $ 2. $ \sum n \le 10^5 $ 3. $ P $ and $ Q $ are permutations of the same set of $ n $ distinct elements. 4. $ p_1 = q_n $ (root is first in preorder and last in postorder). **Objective** Determine whether the pair $ (P, Q) $ uniquely determines a binary tree. That is, output "Yes" if there exists exactly one binary tree with preorder $ P $ and postorder $ Q $; otherwise output "No".

API Response (JSON)

{
  "problem": {
    "name": "M. Mathematics society problem",
    "description": {
      "content": "Nlogonia secret mathematics society helds meetings with distinguished members that are able to solve a given mathematical problem. Being one of the most prestigious mathematics societies in the region",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10289M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Nlogonia secret mathematics society helds meetings with distinguished members that are able to solve a given mathematical problem. Being one of the most prestigious mathematics societies in the region...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case, let $ n \\in \\mathbb{Z}^+ $ be the number of nodes, and let $ P = (p_1, p_2, \\dots, p_n) $ and $ Q = (q_1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments