A. Set Theory

Codeforces

IDCF856A

Time1000ms

Memory256MB

Difficulty—

brute forceconstructive algorithms

English · Original

Chinese · Translation

Formal · Original

Masha and Grisha like studying sets of positive integers. One day Grisha has written a set _A_ containing _n_ different integers _a__i_ on a blackboard. Now he asks Masha to create a set _B_ containing _n_ different integers _b__j_ such that all _n_2 integers that can be obtained by summing up _a__i_ and _b__j_ for all possible pairs of _i_ and _j_ are different. Both Masha and Grisha don't like big numbers, so all numbers in _A_ are from 1 to 106, and all numbers in _B_ must also be in the same range. Help Masha to create the set _B_ that satisfies Grisha's requirement. ## Input Input data contains multiple test cases. The first line contains an integer _t_ — the number of test cases (1 ≤ _t_ ≤ 100). Each test case is described in the following way: the first line of the description contains one integer _n_ — the number of elements in _A_ (1 ≤ _n_ ≤ 100). The second line contains _n_ integers _a__i_ — the elements of _A_ (1 ≤ _a__i_ ≤ 106). ## Output For each test first print the answer: * _NO_, if Masha's task is impossible to solve, there is no way to create the required set _B_. * _YES_, if there is the way to create the required set. In this case the second line must contain _n_ different positive integers _b__j_ — elements of _B_ (1 ≤ _b__j_ ≤ 106). If there are several possible sets, output any of them. [samples]

[{"iden":"statement","content":"Masha 和 Grisha 喜欢研究正整数集合。\n\n一天，Grisha 在黑板上写了一个集合 #cf_span[A]，包含 #cf_span[n] 个不同的整数 #cf_span[ai]。现在他要求 Masha 创建一个集合 #cf_span[B]，包含 #cf_span[n] 个不同的整数 #cf_span[bj]，使得所有通过将 #cf_span[ai] 和 #cf_span[bj] 相加得到的 #cf_span[n2] 个整数（对所有可能的 #cf_span[i] 和 #cf_span[j] 组合）互不相同。\n\nMasha 和 Grisha 都不喜欢大数字，因此集合 #cf_span[A] 中的所有数字都在 #cf_span[1] 到 #cf_span[106] 范围内，集合 #cf_span[B] 中的所有数字也必须在此范围内。\n\n请帮助 Masha 创建满足 Grisha 要求的集合 #cf_span[B]。\n\n输入数据包含多个测试用例。第一行包含一个整数 #cf_span[t] —— 测试用例的数量（#cf_span[1 ≤ t ≤ 100]）。\n\n每个测试用例的描述如下：描述的第一行包含一个整数 #cf_span[n] —— 集合 #cf_span[A] 中元素的个数（#cf_span[1 ≤ n ≤ 100]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai] —— 集合 #cf_span[A] 的元素（#cf_span[1 ≤ ai ≤ 106]）。 \n\n对于每个测试用例，首先输出答案：\n\n"},{"iden":"input","content":"输入数据包含多个测试用例。第一行包含一个整数 #cf_span[t] —— 测试用例的数量（#cf_span[1 ≤ t ≤ 100]）。每个测试用例的描述如下：描述的第一行包含一个整数 #cf_span[n] —— 集合 #cf_span[A] 中元素的个数（#cf_span[1 ≤ n ≤ 100]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai] —— 集合 #cf_span[A] 的元素（#cf_span[1 ≤ ai ≤ 106]）。 "},{"iden":"output","content":"对于每个测试用例，首先输出答案：\n\n_NO_，如果 Masha 的任务无解，即无法创建所需的集合 #cf_span[B]。\n_YES_，如果存在创建所需集合的方法。此时第二行必须包含 #cf_span[n] 个不同的正整数 #cf_span[bj] —— 集合 #cf_span[B] 的元素（#cf_span[1 ≤ bj ≤ 106]）。如果有多个可能的集合，输出任意一个即可。 "}]}

Let $ A = \{a_1, a_2, \dots, a_n\} \subseteq \{1, 2, \dots, 10^6\} $ be a set of $ n $ distinct positive integers. Find a set $ B = \{b_1, b_2, \dots, b_n\} \subseteq \{1, 2, \dots, 10^6\} $ of $ n $ distinct positive integers such that all $ n^2 $ sums $ a_i + b_j $ for $ 1 \leq i, j \leq n $ are distinct.

Samples

Input #1

Output #1

YES
1 2 3 
YES
1 
YES
1 2

API Response (JSON)

{
  "problem": {
    "name": "A. Set Theory",
    "description": {
      "content": "Masha and Grisha like studying sets of positive integers. One day Grisha has written a set _A_ containing _n_ different integers _a__i_ on a blackboard. Now he asks Masha to create a set _B_ containi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF856A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Masha and Grisha like studying sets of positive integers.\n\nOne day Grisha has written a set _A_ containing _n_ different integers _a__i_ on a blackboard. Now he asks Masha to create a set _B_ containi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"Masha 和 Grisha 喜欢研究正整数集合。\\n\\n一天，Grisha 在黑板上写了一个集合 #cf_span[A]，包含 #cf_span[n] 个不同的整数 #cf_span[ai]。现在他要求 Masha 创建一个集合 #cf_span[B]，包含 #cf_span[n] 个不同的整数 #cf_span[bj]，使得所有通...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ A = \\{a_1, a_2, \\dots, a_n\\} \\subseteq \\{1, 2, \\dots, 10^6\\} $ be a set of $ n $ distinct positive integers.\n\nFind a set $ B = \\{b_1, b_2, \\dots, b_n\\} \\subseteq \\{1, 2, \\dots, 10^6\\} $ of $ n $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments