G. Dreamoon and NightMarket

Codeforces

IDCF10123G

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

After moving to Taipei, Dreamoon always goes to dinner at Jinmei Night Market. There are N kinds of food sold at Jinmei Night Market. These foods are numbered from 1 to N. The price of one piece of i-th food is pi. Every night, Dreamoon will choose a non-empty set of foods and eat one piece of each food in this set. Dreamoon likes new things. So he won't choose the same set in two different nights. Besides this, because Dreamoon is a poor boy, each night, he will choose the cheapest food set that he didn't choose before. Now, you are given a positive integer K. Can you tell Dreamoon which set of foods he will choose on K-th day? You only have to tell him how much he will spent on this day. The input consists of two lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. Output one number indicating how much Dreamoon will spend on food on K-th day. ## Input The input consists of two lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. 2 ≤ N ≤ 2 × 105 1 ≤ K ≤ min(106, 2N - 1) 1 ≤ pi ≤ 108 ## Output Output one number indicating how much Dreamoon will spend on food on K-th day. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of food types. Let $ P = (p_1, p_2, \dots, p_N) \in \mathbb{Z}^N $ be the price vector, with $ p_i > 0 $. Let $ \mathcal{S} $ be the set of all non-empty subsets of $ \{1, 2, \dots, N\} $, ordered by increasing total price, and lexicographically for ties. **Constraints** 1. $ 1 \leq N \leq 20 $ 2. $ 1 \leq p_i \leq 10^8 $ 3. $ 1 \leq K \leq \min(2^N - 1, 10^5) $ **Objective** Find the total price of the $ K $-th smallest non-empty subset of $ P $, where subset sums are ordered increasingly.

API Response (JSON)

{
  "problem": {
    "name": "G. Dreamoon and NightMarket",
    "description": {
      "content": "After moving to Taipei, Dreamoon always goes to dinner at Jinmei Night Market. There are N kinds of food sold at Jinmei Night Market. These foods are numbered from 1 to N. The price of one piece of i-",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10123G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After moving to Taipei, Dreamoon always goes to dinner at Jinmei Night Market. There are N kinds of food sold at Jinmei Night Market. These foods are numbered from 1 to N. The price of one piece of i-...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of food types.  \nLet $ P = (p_1, p_2, \\dots, p_N) \\in \\mathbb{Z}^N $ be the price vector, with $ p_i > 0 $.  \n\nLet $ \\mathcal{S} $ be the set...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments