G. Akinator

Codeforces

IDCF10221G

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

One day hacker Dmitry found an interesting game called Akinator. The rules of the game are very simple: player thinks of some famous person and Akinator tries to guess this person in a limited number of questions. Every turn Akinator asks player: «Is this person i1 or i2 or ... or im?» (here m is the number of people in the question, it can differ from question to question). The player answers «Yes» or «No», and Akinator will use obtained information. As soon as Akinator knows the thought person, he says the answer and wins. If Akinator can't guess the person in the given number of questions, he loses. Akinator has k questions to guess the thought person. It is known in advance that Dmitry has thought of one of these n people: 1, 2, ..., n with the probabilities p1, p2, ..., pn. Determine if Akinator can guarantee his guess in k questions, and if he can, what is the minimal average number of questions he needs for that. First line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — number of possibly thought persons and number of questions. Second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 1012). Probabilities pi are proportional to ai, that is, they can be calculated as . If Akinator can't surely guess the thought person, output «_No solution_». Otherwise output the irreducible fraction — the minimal average number of questions Akinator needs to win the game. In the third sample Akinator has 3 attempts. It is optimal to ask the first question about the 4th person. If the answer «No» is received, ask about the 3rd person. If the answer «No» is received here as well, use the last question to choose between 1st and 2nd persons. The average number of attempts here is 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9. ## Input First line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — number of possibly thought persons and number of questions.Second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 1012). Probabilities pi are proportional to ai, that is, they can be calculated as . ## Output If Akinator can't surely guess the thought person, output «_No solution_».Otherwise output the irreducible fraction — the minimal average number of questions Akinator needs to win the game. [samples] ## Note In the third sample Akinator has 3 attempts. It is optimal to ask the first question about the 4th person. If the answer «No» is received, ask about the 3rd person. If the answer «No» is received here as well, use the last question to choose between 1st and 2nd persons.The average number of attempts here is 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9.

**Definitions** Let $ A = (a_1, a_2, \dots, a_n) $ and $ B = (b_1, b_2, \dots, b_m) $ be two sequences of integers representing the difficulty levels of problems proposed by Filiberto and Abraham, respectively. **Constraints** 1. $ 1 \leq n, m \leq 10^4 $ 2. $ 1 \leq a_i, b_j \leq 10^9 $ for all valid indices **Objective** Find the length of the longest common subsequence (LCS) between sequences $ A $ and $ B $, i.e., compute: $$ \text{LCS}(A, B) $$

API Response (JSON)

{
  "problem": {
    "name": "G. Akinator",
    "description": {
      "content": "One day hacker Dmitry found an interesting game called Akinator. The rules of the game are very simple: player thinks of some famous person and Akinator tries to guess this person in a limited number ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10221G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "One day hacker Dmitry found an interesting game called Akinator. The rules of the game are very simple: player thinks of some famous person and Akinator tries to guess this person in a limited number ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A = (a_1, a_2, \\dots, a_n) $ and $ B = (b_1, b_2, \\dots, b_m) $ be two sequences of integers representing the difficulty levels of problems proposed by Filiberto and Abraham, r...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments