A. Strange Base

Codeforces

IDCF10238A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

On Planet E, people counts in base $phi.alt$! We are all familiar with decimal representations. In decimal representation, each digit $x_i$ satisfies $0 <= x_i <= 9$ and $overline(x_q x_{q -1} x_{q -2} \\dots x_0. x_{-1} x_{-2} \\dots x_p)$ represents $$ \sum_{i = p}^q x_i 10^i = x_q 10^q + x_{q - 1} 10^{q - 1} + \ldots + x_p 10^p. $$ This can be naturally extended to any integer base $b >= 2$. In base $b$, each digit $x_i$ satisfies $0 <= x_i <= b -1$ and $overline(x_q x_(q -1) x_(q -2) \\dots x_0. x_(-1) x_(-2) \\dots x_p)$ represents $$ \sum_{i = p}^q x_i b^i = x_q b^q + x_{q - 1} b^{q - 1} + \ldots + x_p b^p. $$ Now it comes to non-integral bases! Let $phi.alt = (1 + sqrt(5)) \/ 2$ be the golden ratio. It can be shown that every positive integer $n$ can be represented in $$ n = \sum_{i = p}^q x_i \phi^i = x_q \phi^q + x_{q - 1} \phi^{q - 1} + \ldots + x_p \phi^p, $$ where each digit $x_i$ is either $0$ or $1$, and any adjacent digits $x_i$ and $x_(i + 1)$ are not both $1$. This representation is unique and is called the base $phi.alt$ representation. Can you help the people on Planet E to convert a positive number in base $phi.alt$? The first line contains a positive integer $T$ ($T <= 10$), the number of testcases. Each testcase contains a positive integer $n$ ($n <= 100000$). For each testcase, output a single line consisting of the representation of $n$ in base $phi.alt$. ## Input The first line contains a positive integer $T$ ($T <= 10$), the number of testcases.Each testcase contains a positive integer $n$ ($n <= 100000$). ## Output For each testcase, output a single line consisting of the representation of $n$ in base $phi.alt$. [samples]

**Definitions** Let $\phi = \frac{1 + \sqrt{5}}{2}$ be the golden ratio. Let $T \in \mathbb{Z}^+$ be the number of test cases. For each test case $k \in \{1, \dots, T\}$, let $n_k \in \mathbb{Z}^+$ be the input integer. **Constraints** 1. $1 \le T \le 10$ 2. $1 \le n_k \le 100000$ for all $k \in \{1, \dots, T\}$ **Objective** For each $n_k$, find the unique representation $$ n_k = \sum_{i = p}^q x_i \phi^i $$ where $x_i \in \{0, 1\}$ for all $i$, and $x_i \cdot x_{i+1} = 0$ for all $i$ (no two adjacent digits are 1). Output the digit sequence $x_q x_{q-1} \dots x_p$ in order of decreasing $i$.

API Response (JSON)

{
  "problem": {
    "name": "A. Strange Base",
    "description": {
      "content": "On Planet E, people counts in base $phi.alt$! We are all familiar with decimal representations. In decimal representation, each digit $x_i$ satisfies $0 <= x_i <= 9$ and $overline(x_q x_{q -1} x_{q -",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10238A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On Planet E, people counts in base $phi.alt$!\n\nWe are all familiar with decimal representations. In decimal representation, each digit $x_i$ satisfies $0 <= x_i <= 9$ and $overline(x_q x_{q -1} x_{q -...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $\\phi = \\frac{1 + \\sqrt{5}}{2}$ be the golden ratio.  \nLet $T \\in \\mathbb{Z}^+$ be the number of test cases.  \nFor each test case $k \\in \\{1, \\dots, T\\}$, let $n_k \\in \\mathbb{Z}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments