A. Bath Temperature

Codeforces

IDCF10148A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Lately Teodoro has been working a lot, solving tons of problems. Now he thinks that he needs some well deserved rest and decided to go to a bath house to take a nice relaxing bath. Teodoro is very demanding and wants the temperature of the water to be exactly X degrees celsius. The bath house has N taps of water, each with a specific water temperature of ai degrees celsius. He can open multiple taps to get the exact temperature that he wants by controlling the proportion of water coming out of each tap. For example, imagine Teodoro opened two taps: the first tap has water at 50 degrees celsius and the second tap has water at 75 degrees celsius. He opened the taps so that there is four times more water coming out of the first tap than the second tap. The resulting temperature r can be calculated as: Notice that the resulting temperature will always be a weighted mean of the water temperatures of the open taps. The amount of money that Teodoro will pay at the bath house depends on how many different taps he opens and Teodoro doesn't have much money to spend, so he wants to know what is the minimum number of taps that he has to open to get the desired temperature. The first line of the input contains two integers N (1 ≤ N ≤ 105) and X (0 ≤ X ≤ 100), indicating respectively the number of taps and the desired temperature. The following line contains N integers ai (0 ≤ ai ≤ 100). The i-th integer indicates the temperature of the water that comes out of the i-th tap. Output the minimum number of taps that Teodoro needs to open to get his desired temperature. Output - 1 if it is not possible to get the desired temperature in any way. ## Input The first line of the input contains two integers N (1 ≤ N ≤ 105) and X (0 ≤ X ≤ 100), indicating respectively the number of taps and the desired temperature.The following line contains N integers ai (0 ≤ ai ≤ 100). The i-th integer indicates the temperature of the water that comes out of the i-th tap. ## Output Output the minimum number of taps that Teodoro needs to open to get his desired temperature. Output - 1 if it is not possible to get the desired temperature in any way. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of taps, and $ X \in [0, 100] $ the desired temperature. Let $ A = \{a_1, a_2, \dots, a_N\} \subseteq [0, 100] $ be the set of water temperatures from the taps. **Constraints** $ 1 \leq N \leq 10^5 $, $ 0 \leq X \leq 100 $, $ 0 \leq a_i \leq 100 $ for all $ i $. **Objective** Find the minimum $ k \in \mathbb{Z}^+ $ such that $ X $ is a convex combination of $ k $ elements from $ A $, i.e., there exist $ k $ indices $ i_1, \dots, i_k $ and weights $ \lambda_1, \dots, \lambda_k \geq 0 $, $ \sum_{j=1}^k \lambda_j = 1 $, satisfying: $$ \sum_{j=1}^k \lambda_j a_{i_j} = X $$ If no such $ k $ exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "A. Bath Temperature",
    "description": {
      "content": "Lately Teodoro has been working a lot, solving tons of problems. Now he thinks that he needs some well deserved rest and decided to go to a bath house to take a nice relaxing bath.  Teodoro is very d",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10148A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Lately Teodoro has been working a lot, solving tons of problems. Now he thinks that he needs some well deserved rest and decided to go to a bath house to take a nice relaxing bath. \n\nTeodoro is very d...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of taps, and $ X \\in [0, 100] $ the desired temperature.  \nLet $ A = \\{a_1, a_2, \\dots, a_N\\} \\subseteq [0, 100] $ be the set of water temper...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments