Euclid Guess Codeforces Solution | Codeforces Problem Solution 2022

Euclid Guess Codeforces Solution | Codeforces Problem Solution 2022

G. Euclid Guess

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's consider Euclid's algorithm for finding the greatest common divisor, where 𝑡$t$ is a list:

function Euclid(a, b):
    if a < b:
        swap(a, b)

    if b == 0:
        return a

    r = reminder from dividing a by b
    if r > 0:
        append r to the back of t

    return Euclid(b, r)

There is an array 𝑝$p$ of pairs of positive integers that are not greater than 𝑚$m$. Initially, the list 𝑡$t$ is empty. Then

Solution Click Below:-  CLICK HERE

 the function is run on each pair in 𝑝$p$. After that the list 𝑡$t$ is shuffled and given to you.

You have to find an array 𝑝$p$ of any size not greater than 2⋅104$2\cdot {10}^4$ that produces the given list 𝑡$t$, or tell that no such array exists.

Input

The first line contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤103$1\le n\le {10}^3$, 1≤𝑚≤109$1\le m\le {10}^9$) — the length of the array 𝑡$t$ and the constraint for integers in pairs.

Digit Minimization Codeforces Solution

Z mod X = C Codeforces Solution

Column Swapping Codeforces Solution

Traps Codeforces Solution

MEX vs DIFF Codeforces Solution

Diverse Segments Codeforces Solution

Euclid Guess Codeforces Solution

Hard Cut Codeforces Solution

The second line contains 𝑛$n$ integers 𝑡1,𝑡2,…,𝑡𝑛$t_1,t_2,\dots ,t_n$ (1≤𝑡𝑖≤𝑚$1\le t_i\le m$) — the elements of the array 𝑡$t$.

Output

• If the answer does not exist, output −1$-1$.
• If the answer exists, in the first line output 𝑘$k$ (1≤𝑘≤2⋅104$1\le k\le 2\cdot {10}^4$) — the size of your array 𝑝$p$, i. e. the number of pairs in the answer.

  The 𝑖$i$-th of the next 𝑘$k$ lines should contain two integers 𝑎𝑖$a_i$ and 𝑏𝑖$b_i$ (1≤𝑎𝑖,𝑏𝑖≤𝐴$1\le a_i,b_i\le A$) — the 𝑖$i$-th pair in 𝑝$p$.

If there are multiple valid answers you can output any of them.