A. Perfect Squares

Codeforces

IDCF914A

Time1000ms

Memory256MB

Difficulty—

brute forceimplementationmath

English · Original

Chinese · Translation

Formal · Original

Given an array _a_1, _a_2, ..., _a__n_ of _n_ integers, find the largest number in the array that is not a perfect square. A number _x_ is said to be a perfect square if there exists an integer _y_ such that _x_ = _y_2. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 1000) — the number of elements in the array. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 106 ≤ _a__i_ ≤ 106) — the elements of the array. It is guaranteed that at least one element of the array is not a perfect square. ## Output Print the largest number in the array which is not a perfect square. It is guaranteed that an answer always exists. [samples] ## Note In the first sample case, 4 is a perfect square, so the largest number in the array that is not a perfect square is 2.

给定一个包含 $n$ 个整数的数组 $[a_1, a_2, ..., a_n]$，找出其中最大的不是完全平方数的数。一个数 $x$ 被称为完全平方数，当且仅当存在整数 $y$ 使得 $x = y^2$。第一行包含一个整数 $n$ ($1 ≤ n ≤ 1000$) —— 数组中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($-10^6 ≤ a_i ≤ 10^6$) —— 数组的元素。保证数组中至少有一个元素不是完全平方数。请输出数组中最大的不是完全平方数的数。保证答案一定存在。在第一个样例中，$4$ 是一个完全平方数，因此数组中最大的不是完全平方数的数是 $2$。 ## Input 第一行包含一个整数 $n$ ($1 ≤ n ≤ 1000$) —— 数组中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($-10^6 ≤ a_i ≤ 10^6$) —— 数组的元素。保证数组中至少有一个元素不是完全平方数。 ## Output 请输出数组中最大的不是完全平方数的数。保证答案一定存在。 [samples] ## Note 在第一个样例中，$4$ 是一个完全平方数，因此数组中最大的不是完全平方数的数是 $2$。

Let $ A = \{a_1, a_2, \dots, a_n\} \subseteq \mathbb{Z} $, with $ 1 \leq n \leq 1000 $ and $ -10^6 \leq a_i \leq 10^6 $. Define the set of perfect squares in $ A $ as: $$ S = \{ x \in A \mid \exists y \in \mathbb{Z},\ x = y^2 \} $$ Let $ T = A \setminus S $ be the set of elements in $ A $ that are not perfect squares. It is given that $ T \neq \emptyset $. Objective: Compute $$ \max(T) $$

Samples

Input #1

2
4 2

Output #1

Input #2

8
1 2 4 8 16 32 64 576

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Perfect Squares",
    "description": {
      "content": "Given an array _a_1, _a_2, ..., _a__n_ of _n_ integers, find the largest number in the array that is not a perfect square. A number _x_ is said to be a perfect square if there exists an integer _y_ s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF914A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given an array _a_1, _a_2, ..., _a__n_ of _n_ integers, find the largest number in the array that is not a perfect square.\n\nA number _x_ is said to be a perfect square if there exists an integer _y_ s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 $n$ 个整数的数组 $[a_1, a_2, ..., a_n]$，找出其中最大的不是完全平方数的数。\n\n一个数 $x$ 被称为完全平方数，当且仅当存在整数 $y$ 使得 $x = y^2$。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 1000$) —— 数组中元素的个数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($-10^6 ≤ a_i ≤...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ A = \\{a_1, a_2, \\dots, a_n\\} \\subseteq \\mathbb{Z} $, with $ 1 \\leq n \\leq 1000 $ and $ -10^6 \\leq a_i \\leq 10^6 $.\n\nDefine the set of perfect squares in $ A $ as:\n$$\nS = \\{ x \\in A \\mid \\exists ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments