E. Epic Fail of a Genie

Codeforces

IDCF10068E

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Aladdin had found a new shiny lamp and has started polishing it with his hands. Suddenly a mysterious genie appeared from within and offered Aladdin to fulfill any of his three wishes. Genie had a very subtle humor that made Aladdin very sceptical about him. Aladdin didn't believe that genie was so powerful that could do anything he had wished and asked him to become a mouse. The genie did that without hesitation. Then Aladdin asked genie to become a mouse pad. Genie didn't like this kind of wish but had to submit. Finally Aladdin tested genie's abilities in math: he had to choose a nonempty subset giving the maximum product from the given set of numbers. Genie was shocked. Math was his Achilles' heel, however he was able to contact anyone on earth to help him. You are a secret weapon of the genie — help him solve the test and avoid this epic fail. This is the last chance for the genie: he'll be forever jailed in the lamp if his new master doesn't trust him. The first line of input contains an integer N (2 ≤ N ≤ 104) — the cardinality of a set of numbers. The second line of input contains N floating-point numbers with absolute value not more than 106. The fractional part of each number does not contain more than two digits. The first line of the output should contain a single integer M — the total number of numbers that genie should choose from the set. The second line of output should contain 1-based indexes of these numbers. Indexes must be sorted in ascending order. If multiple solutions exist please output the one with the minimal subset cardinality. If there are still several suitable solutions output any of them. ## Input The first line of input contains an integer N (2 ≤ N ≤ 104) — the cardinality of a set of numbers.The second line of input contains N floating-point numbers with absolute value not more than 106. The fractional part of each number does not contain more than two digits. ## Output The first line of the output should contain a single integer M — the total number of numbers that genie should choose from the set.The second line of output should contain 1-based indexes of these numbers. Indexes must be sorted in ascending order. If multiple solutions exist please output the one with the minimal subset cardinality. If there are still several suitable solutions output any of them. [samples]

**Definitions** Let $ N \in \mathbb{Z} $, $ 2 \leq N \leq 10^4 $, be the cardinality of the set. Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of real numbers, where $ |a_i| \leq 10^6 $ and each $ a_i $ has at most two fractional digits. **Constraints** 1. $ N \in [2, 10^4] $ 2. $ a_i \in \mathbb{R} $, $ |a_i| \leq 10^6 $, and fractional part of $ a_i $ has at most two digits. **Objective** Find a nonempty subset $ S \subseteq \{1, 2, \dots, N\} $ such that the product $ \prod_{i \in S} a_i $ is maximized. Among all such subsets, choose the one with minimal cardinality. If multiple subsets with minimal cardinality exist, output any. Output: - $ M = |S| $ - The 1-based indices of elements in $ S $, sorted in ascending order.

API Response (JSON)

{
  "problem": {
    "name": "E. Epic Fail of a Genie",
    "description": {
      "content": "Aladdin had found a new shiny lamp and has started polishing it with his hands. Suddenly a mysterious genie appeared from within and offered Aladdin to fulfill any of his three wishes. Genie had a ver",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10068E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Aladdin had found a new shiny lamp and has started polishing it with his hands. Suddenly a mysterious genie appeared from within and offered Aladdin to fulfill any of his three wishes. Genie had a ver...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ 2 \\leq N \\leq 10^4 $, be the cardinality of the set.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of real numbers, where $ |a_i| \\leq 10^6 $ and eac...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments