GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Thursday 19 May 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 2104 that produces the given list t, or tell that no such array exists.

Input

The first line contains two integers n and m (1n1031m109) — the length of the array t and the constraint for integers in pairs.

The second line contains n integers t1,t2,,tn (1tim) — the elements of the array t.

Output
  • If the answer does not exist, output 1.
  • If the answer exists, in the first line output k (1k2104) — 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 ai and bi (1ai,biA) — the i-th pair in p.

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

No comments:

Post a Comment