I. Sale in GameStore

Codeforces

IDCF10051I

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

A well-known Berland online games store has announced a great sale! Buy any game today, and you can download more games for free! The only constraint is that the total price of the games downloaded for free can't exceed the price of the bought game. When Polycarp found out about the sale, he remembered that his friends promised him to cover any single purchase in GameStore. They presented their promise as a gift for Polycarp's birthday. There are n games in GameStore, the price of the i-th game is pi. What is the maximum number of games Polycarp can get today, if his friends agree to cover the expenses for any single purchase in GameStore? The first line of the input contains a single integer number n (1 ≤ n ≤ 2000) — the number of games in GameStore. The second line contains n integer numbers p1, p2, ..., pn (1 ≤ pi ≤ 105), where pi is the price of the i-th game. Print the maximum number of games Polycarp can get today. In the first example Polycarp can buy any game of price 5 or 6 and download games of prices 1 and 3 for free. So he can get at most 3 games. In the second example Polycarp can buy any game and download the other one for free. ## Input The first line of the input contains a single integer number n (1 ≤ n ≤ 2000) — the number of games in GameStore. The second line contains n integer numbers p1, p2, ..., pn (1 ≤ pi ≤ 105), where pi is the price of the i-th game. ## Output Print the maximum number of games Polycarp can get today. [samples] ## Note In the first example Polycarp can buy any game of price 5 or 6 and download games of prices 1 and 3 for free. So he can get at most 3 games.In the second example Polycarp can buy any game and download the other one for free.

**Definitions** Let $ s \in \{0,1\}^* $ be the encrypted string, with $ 8 \leq |s| \leq 8 \times 10^4 $. **Constraints** Each character of $ s $ is either $ 0 $ or $ 1 $. **Objective** Decrypt $ s $ to recover the original string. *(Note: The decryption algorithm is unspecified; formalization requires the algorithm. Without it, the objective cannot be mathematically defined.)*

API Response (JSON)

{
  "problem": {
    "name": "I. Sale in GameStore",
    "description": {
      "content": "A well-known Berland online games store has announced a great sale! Buy any game today, and you can download more games for free! The only constraint is that the total price of the games downloaded fo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A well-known Berland online games store has announced a great sale! Buy any game today, and you can download more games for free! The only constraint is that the total price of the games downloaded fo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1\\}^* $ be the encrypted string, with $ 8 \\leq |s| \\leq 8 \\times 10^4 $.\n\n**Constraints**  \nEach character of $ s $ is either $ 0 $ or $ 1 $.\n\n**Objective**  \nDecrypt...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments