eolymp
bolt
Try our new interface for solving problems
Məsələlər

Полные квадраты

Полные квадраты

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, ... , 0 + 1 + 3 + .. + (2n - 1), ... , составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, ..., n^2, ....

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, ... , k + 1 + 3 + ... + (2n - 1), ... . В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности, либо выясняет, что в ней вообще не встречается полных квадратов.

Giriş verilənləri

Одно целое число k - начальное число в последовательности (-10^12k10^12).

Çıxış verilənləri

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите "none".

Nümunə

Giriş verilənləri #1
0
Çıxış verilənləri #1
0
Giriş verilənləri #2
-5
Çıxış verilənləri #2
2
Giriş verilənləri #3
2
Çıxış verilənləri #3
none

Qeyd

В первом примере каждое число последовательности является полным квадратом. Минимальный из них - 0, 0^2 = 0.

Во втором примере последовательность начинается так: -5, -4, -1, 4, 11, 20, ... . Минимальное неотрицательное целое число, квадрат которого встречается в последовательности - 2, 2^2 = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, ... . В ней нет квадратов целых чисел.

Mənbə 2018 Всероссийская олимпиада школьников по информатике, Региональный этап, день 1, Москва, 26 января 2019, Задача B