D. Double it

Codeforces

IDCF10146D

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can't figure out how to do it. Your task is to find a way to use the machines to get exactly n coins. The input consists of a single line containing n (1 ≤ n ≤ 109). For each one output a string of A's and B's giving the order in which the machines are used. ## Input The input consists of a single line containing n (1 ≤ n ≤ 109). ## Output For each one output a string of A's and B's giving the order in which the machines are used. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 10^9 $. Define two operations: - Operation $ A $: $ x \mapsto 2x + 1 $ - Operation $ B $: $ x \mapsto 2x + 2 $ **Constraints** Start from $ x = 0 $. Apply a sequence of operations $ A $ and $ B $ to reach exactly $ n $. **Objective** Find a string $ s \in \{A, B\}^* $ such that applying the operations in order from left to right to initial value $ 0 $ yields $ n $.

API Response (JSON)

{
  "problem": {
    "name": "D. Double it",
    "description": {
      "content": "Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to bu",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10146D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to bu...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^9 $.  \nDefine two operations:  \n- Operation $ A $: $ x \\mapsto 2x + 1 $  \n- Operation $ B $: $ x \\mapsto 2x + 2 $  \n\n**Constraints** ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments