C. Too Many Coins

Codeforces

IDCF10088C

Time4000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Your friend has C coins in his pocket, each coin has a value Vi, and you know that he will not need that amount of money, he will only need M. You want to help him not to carry all these coins, so you decided to tell him to take the coins of specific values, in a way that he will have at least the amount of money he needs. You will tell him that it will be enough for him if he carried coins of types X1, X2, ..., Xn. Note that if you tell him to carry coins of type Xi, he will carry all the coins with values Vi = Xi. The first line contains an integer T representing the number of test cases. Each test case consists of two lines, the first line has two integers C (1 ≤ C ≤ 1000000) and M (1 ≤ M ≤ 109), and the other line contains C integers representing the values of the coins (1 ≤ Vi ≤ 1000000). For each test case print the types of coins which your friend must carry,if there are multiple solutions, print the solution with the minimum number of types, if there are still multiple solutions print the one which makes your friend carry more money, if there are still multiple solutions print the solution with the bigger types. print the types in increasing order. If he doesn't have enough money print "Impossible" without the quotations. ## Input The first line contains an integer T representing the number of test cases. Each test case consists of two lines, the first line has two integers C (1 ≤ C ≤ 1000000) and M (1 ≤ M ≤ 109), and the other line contains C integers representing the values of the coins (1 ≤ Vi ≤ 1000000). ## Output For each test case print the types of coins which your friend must carry,if there are multiple solutions, print the solution with the minimum number of types, if there are still multiple solutions print the one which makes your friend carry more money, if there are still multiple solutions print the solution with the bigger types. print the types in increasing order. If he doesn't have enough money print "Impossible" without the quotations. [samples]

**Definitions** Let $ N, M \in \mathbb{Z}^+ $ be the dimensions of the grid, with $ 1 \leq N, M \leq 10^4 $. Let $ P \in \mathbb{Z} $ be the number of dangerous cells, with $ 0 \leq P \leq 5 \cdot 10^4 $. Let $ D \subseteq \{1, \dots, N\} \times \{1, \dots, M\} $ be the set of dangerous cells. Naruto starts at position $ (1,1) $; the target is at $ (N,M) $. **Constraints** 1. Total queries $ \leq 12P + 4(N + M) $. 2. Only valid directions: `"U"`, `"D"`, `"L"`, `"R"`. 3. Cannot move into a dangerous cell. 4. Grid boundaries are implicit; queries to invalid directions return `"no"`. **Query Types** - `query dir`: Probe direction `dir` ∈ {`"U"`, `"D"`, `"L"`, `"R"`}. - Response: `"yes"` if adjacent cell in `dir` is safe and within bounds; `"no"` otherwise. - `move dir`: Move in direction `dir`. - Response: `"yes"` if target $ (N,M) $ reached; `"no"` otherwise. **Objective** Find a path from $ (1,1) $ to $ (N,M) $ using at most $ 12P + 4(N + M) $ queries, by adaptively probing and moving, without visiting any cell in $ D $.

API Response (JSON)

{
  "problem": {
    "name": "C. Too Many Coins",
    "description": {
      "content": "Your friend has C coins in his pocket, each coin has a value Vi, and you know that he will not need that amount of money, he will only need M.  You want to help him not to carry all these coins, so y",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10088C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your friend has C coins in his pocket, each coin has a value Vi, and you know that he will not need that amount of money, he will only need M. \n\nYou want to help him not to carry all these coins, so y...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ be the dimensions of the grid, with $ 1 \\leq N, M \\leq 10^4 $.  \nLet $ P \\in \\mathbb{Z} $ be the number of dangerous cells, with $ 0 \\leq P \\leq 5 \\cdot...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments