시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

"Drat!" cursed Charles.  "This stupid carry bar is not working in my Engine!  I just tried to calculate the square of a number, but it's wrong; all of the carries are lost."

"Hmm," mused Ada, "arithmetic without carries!  I wonder if I can figure out what your original input was, based on the result I see on the Engine."

Carryless addition, denoted by $\oplus$, is the same as normal addition, except any carries are ignored (in base $10$). Thus, $37 \oplus 48$ is $75$, not $85$.

Carryless multiplication, denoted by $\otimes$, is performed using the schoolboy algorithm for multiplication, column by column, but the intermediate additions are calculated using carryless addition. More formally, Let $a_m a_{m-1} \ldots a_1 a_0$ be the digits of $a$, where $a_0$ is its least significant digit. Similarly define $b_n b_{n-1} \ldots b_1 b_0$ be the digits of $b$. The digits of $c = a \otimes b$ are given by the following equation: \[ c_k = \left( a_0 b_k \oplus a_1 b_{k-1} \oplus \cdots \oplus a_{k-1} b_1 \oplus a_k b_0 \right) \bmod{10}, \] where any $a_i$ or $b_j$ is considered zero if $i > m$ or $j > n$. For example, $9 \otimes 1\,234$ is $9\,876$, $90 \otimes 1\,234$ is $98\,760$, and $99 \otimes 1\,234$ is $97\,536$.

Given $N$, find the smallest positive integer $a$ such that $a \otimes a = N$.

입력

The input consists of a single line with a positive integer $N$, with at most $25$ digits and no leading zeros.

출력

Print, on a single line, the least positive number $a$ such that $a \otimes a = N$. If there is no such $a$, print '-1' instead.

예제 입력 1

6

예제 출력 1

4

예제 입력 2

149

예제 출력 2

17

예제 입력 3

123476544

예제 출력 3

11112

예제 입력 4

15

예제 출력 4

-1

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2019 C번

  • 문제를 만든 사람: Tomas Rokicki