A. Gaby And Addition

Codeforces

IDCF10146A

Time6000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps: it means when adding two numbers we will get something like this: Unfortunately as Gaby is too young she doesn't know what the third step means so she just omitted this step using her own standard algorithm (Gaby's addition algorithm). When adding two numbers without carrying when necessary she gets something like the following: Gaby loves playing with numbers so she wants to practice the algorithm she has just learned (in the way she learned it) with a list of numbers adding every possible pair looking for the pair which generates the largest value and the smallest one. She needs to check if she is doing it correctly so she asks for your help to find the largest and the smallest value generated from the list of numbers using Gaby's addition algorithm. The input starts with an integer n (2 ≤ n ≤ 106) indicating the number of integers Gaby will be playing with. The next line contains n numbers ni (0 ≤ ni ≤ 1018) separated by a single space. Output the smallest and the largest number you can get from adding two numbers from the list using Gaby's addition algorithm. In the first sample input this is how you get the minimum and the maximum value ## Input The input starts with an integer n (2 ≤ n ≤ 106) indicating the number of integers Gaby will be playing with. The next line contains n numbers ni (0 ≤ ni ≤ 1018) separated by a single space. ## Output Output the smallest and the largest number you can get from adding two numbers from the list using Gaby's addition algorithm. [samples] ## Note In the first sample input this is how you get the minimum and the maximum value

**Definitions** Let $ n \in \mathbb{Z} $ be the number of integers, with $ 2 \leq n \leq 10^6 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ 0 \leq a_i \leq 10^{18} $ for all $ i $. Define **Gaby's addition** $ \oplus $: for two non-negative integers $ x, y $, $$ x \oplus y = \sum_{k=0}^{\infty} \left( (d_k(x) + d_k(y)) \mod 10 \right) \cdot 10^k $$ where $ d_k(z) $ is the $ k $-th digit (from right, 0-indexed) of $ z $, and $ d_k(z) = 0 $ if $ z $ has no $ k $-th digit. **Constraints** 1. $ 2 \leq n \leq 10^6 $ 2. $ 0 \leq a_i \leq 10^{18} $ for all $ i \in \{1, \dots, n\} $ **Objective** Find: $$ \min_{1 \leq i < j \leq n} (a_i \oplus a_j), \quad \max_{1 \leq i < j \leq n} (a_i \oplus a_j) $$

API Response (JSON)

{
  "problem": {
    "name": "A. Gaby And Addition",
    "description": {
      "content": "Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps: it means when adding two numbe",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10146A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps:\n\nit means when adding two numbe...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of integers, with $ 2 \\leq n \\leq 10^6 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ 0 \\leq a_i \\leq 10^{18} $ for...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments