A. Potion of Immortality

Codeforces

IDCF10018A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The world famous scientist Innokentiy has just synthesized the potion of immortality. Unfortunately, he put the flask with this potion on the shelf where most dangerous poisons of all time were kept. Now there are n flasks on this shelf, and the scientist has no idea which of them contains the potion of immortality. Fortunately, Innokentiy has an infinite amount of rabbits. But the scientist doesn't know how exactly these potions affect rabbits. There is the only thing he knows for sure. If rabbit tastes exactly k potions from the flasks on the shelf, it will survive if there was the immortality potion among them and die otherwise. If rabbit tastes the number of potions different from k, the result will be absolutely unpredictable, so the scientist won't make such experiments no matter what. The scientist intends to minimize the amount of lost rabbits while searching for the potion of immortality. You should determine how many rabbits he has to sacrifice in the worst case. The only line contains two integers separated by space — n and k (1 ≤ n ≤ 2000, 1 ≤ k ≤ n) — the number of flasks on the Innokentiy's shelf and the number of potions Innokentiy will give to a single rabbit to taste. If the scientist cannot determine which flusk contains the potion of immortality, output «_-1_». Otherwise, output a single integer — the minimal number of rabbits that Innokentiy will sacrifice in the worst case while searching for the potion of immortality. ## Input The only line contains two integers separated by space — n and k (1 ≤ n ≤ 2000, 1 ≤ k ≤ n) — the number of flasks on the Innokentiy's shelf and the number of potions Innokentiy will give to a single rabbit to taste. ## Output If the scientist cannot determine which flusk contains the potion of immortality, output «_-1_». Otherwise, output a single integer — the minimal number of rabbits that Innokentiy will sacrifice in the worst case while searching for the potion of immortality. [samples]

Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n $. Define the set of flasks $ F = \{1, 2, \dots, n\} $, exactly one of which contains the immortality potion. A rabbit is administered exactly $ k $ flasks' contents. It survives if and only if the immortality potion is among those $ k $ flasks; it dies otherwise. The scientist may design multiple non-overlapping or overlapping tests (each using exactly $ k $ flasks), and observes the survival/death outcome of each rabbit. Let $ m $ be the minimal number of rabbits (tests) required in the worst case to uniquely identify the single flask containing the immortality potion. If no such identification is possible under the constraint that each test uses exactly $ k $ flasks, output $ -1 $. Otherwise, output $ m $. **Constraints:** - $ 1 \leq n \leq 2000 $ - $ 1 \leq k \leq n $ **Objective:** Determine the minimal $ m \in \mathbb{N} $ such that there exists a family of $ m $ subsets $ T_1, T_2, \dots, T_m \subseteq F $, each of size $ |T_i| = k $, and the mapping $ f: F \to \{0,1\}^m $ defined by $$ f(j) = ( \mathbf{1}_{j \in T_1}, \mathbf{1}_{j \in T_2}, \dots, \mathbf{1}_{j \in T_m} ) $$ is injective. If no such family exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "A. Potion of Immortality",
    "description": {
      "content": "The world famous scientist Innokentiy has just synthesized the potion of immortality. Unfortunately, he put the flask with this potion on the shelf where most dangerous poisons of all time were kept. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The world famous scientist Innokentiy has just synthesized the potion of immortality. Unfortunately, he put the flask with this potion on the shelf where most dangerous poisons of all time were kept. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n $.\n\nDefine the set of flasks $ F = \\{1, 2, \\dots, n\\} $, exactly one of which contains the immortality potion.\n\nA rabbit is administered exactly $ k ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments