B. Final Problem

Codeforces
IDCF10219B
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
You have a problem set of ten problems. Each team in the contest has a skill level from 1 to 10 and each of the ten problems has a difficulty level from 1 to 10. A team can only solve problems that have a difficulty level less than or equal to their skill level. You want to add one more problem with difficulty from 1 to 10 such that each team solves *at least* one problem. What is the maximum difficulty that this problem can have? The first line of input contains n (1 ≤ n ≤ 32), the number of teams participating in the contest. The second line of input contains n integers si (1 ≤ si ≤ 10), the skill level of the teams. The third line of input contains 10 integers di (1 ≤ di ≤ 10), the difficulty level of the problems in the problem set so far. Output on a single line the maximum possible difficulty level for the new problem from 1 to 10 such that each team solves *at least* one problem. ## Input The first line of input contains n (1 ≤ n ≤ 32), the number of teams participating in the contest.The second line of input contains n integers si (1 ≤ si ≤ 10), the skill level of the teams.The third line of input contains 10 integers di (1 ≤ di ≤ 10), the difficulty level of the problems in the problem set so far. ## Output Output on a single line the maximum possible difficulty level for the new problem from 1 to 10 such that each team solves *at least* one problem. [samples]
**Definitions** Let $ n \in \mathbb{Z} $ be the number of teams. Let $ S = \{s_1, s_2, \dots, s_n\} \subseteq \{1, 2, \dots, 10\} $ be the set of team skill levels. Let $ D = \{d_1, d_2, \dots, d_{10}\} \subseteq \{1, 2, \dots, 10\} $ be the set of existing problem difficulties. **Constraints** 1. $ 1 \leq n \leq 32 $ 2. $ 1 \leq s_i \leq 10 $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq d_j \leq 10 $ for all $ j \in \{1, \dots, 10\} $ **Objective** Find the maximum $ x \in \{1, 2, \dots, 10\} $ such that for every team skill level $ s \in S $, there exists at least one problem (either in $ D $ or the new problem with difficulty $ x $) with difficulty $ \leq s $. That is, define the set of solvable problems for team $ s $ as $ D \cup \{x\} \cap \{1, 2, \dots, s\} $. We require: $$ \forall s \in S,\quad \left( D \cap \{1, 2, \dots, s\} \right) \cup \left( \{x\} \cap \{1, 2, \dots, s\} \right) \neq \emptyset $$ Maximize $ x \in \{1, 2, \dots, 10\} $ satisfying the above.
API Response (JSON)
{
  "problem": {
    "name": "B. Final Problem",
    "description": {
      "content": "You have a problem set of ten problems. Each team in the contest has a skill level from 1 to 10 and each of the ten problems has a difficulty level from 1 to 10. A team can only solve problems that ha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10219B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a problem set of ten problems. Each team in the contest has a skill level from 1 to 10 and each of the ten problems has a difficulty level from 1 to 10. A team can only solve problems that ha...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of teams.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} \\subseteq \\{1, 2, \\dots, 10\\} $ be the set of team skill levels.  \nLet $ D = \\{d_1, d_2, \\dots, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments