### PROBLEM LINK:

**Author:** Kamil Debowski

**Primary Tester:** Misha Chorniy

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

None

### PROBLEM:

Problem is very long to describe here, kindly check contest/practice links.

### Explanation

In this editorial I will describe the amazing library Kamil was able to build using a very simple function. Having this library coded would make solving the problem a matter of implementation and calling functions, because it allows various solutions to be applicable.

Our function is:

f(a , b) = (a + b)\%mod \ \ ;\ a \neq 0

f(a , b) = (mod-b)\%mod \ \ ;\ a = 0

**Copy Function:** Copies a value val to a cell in our array tar

f(val , 0 , tar)

**Substraction function:** **Sub(a,b) :: a = (a-b)%mod**

It’s equivalent to performing **f(a,mod-1)** exactly **b** times

**Addition function**: **Add(a,b) :: a = (a+b)%mod**

It’s equivalent to f(sub(a,b),f(b,b))

That’s because our function f doesn’t perform addition when a=0

Let’s define:

fhalf= \lfloor{\frac{mod}{2}} \rfloor

chalf=\lceil {\frac{mod}{2}} \rceil

**Decrement function:** **Dec(a) :: a = max(a - 1 , 0)**

It’s equivalent to Add( f(a,fhalf) , fhalf)

That’s correct because f(0,fhalf) = chalf

**Sign Function** returns 1 if the number is greater than zero, or zero otherwise

It’s equivalent to:

Sub( f(a,chalf) , sub(a,chalf) )

**Case a = 0:**

f(a,chalf) = fhalf , sub(a,chalf) = fhalf , that means **sign(0) = 0**

**Case a > 0:**

f(a,chalf) = a-fhalf , sub(a,chalf) = a - chalf

sign(a) = a - fhalf - a + chalf = 1

**NOT Function** :: **Not(a) = (opposite of the sign)**

sub(1,sign(a))

**And Function** :: **And(a,b)** returns 1 if both numbers are **greater** than 0

dec(add(sign(a),sign(b)))

**OR Function** :: **OR(a,b)** returns 1 if at least one number is greater than 0

Not(And(Not(a),Not(b)))

You can implement operators < , > using loops. decrementing both numbers by 1 and returning the corresponding boolean value according to the sign at the time one of them is equal to 0.

Now we can implement a program that multiplies two numbers in the same way we do it by our bare hands. We may copy the first digit of the second number along with the first number and multiply our digit with the first number using some extra cells of our memory. After that we may add the result to our answer cells. The same applies to the second digit. Of course we must perform multiplication by repeated addition.

Repeated addition can be easily done by running a loop that terminates when our second multiplied number reaches zero, adding the first number to the answer by each iteration.

Using these functions we are able to perform any arithmetic operation and of course binary operators. Also we can easily make our simulator run into loops and stop it whenever we would like to. Coding this library would make us able to solve the way we would like to.

You can check Kamil’s solution if we would like to

**AUTHOR’s solution**: Can be found here