Hint $$$1$$$: Should we always make first digit of $$$d$$$ not equal to $$$0$$$? How can we do it?

Hint $$$2$$$: Try to choose such $$$a$$$ that $$$d$$$ will have $$$n$$$ digits.

104840922

Hint $$$1$$$: Integer have exactly $$$4$$$ divisors, if it is of form $$$pq$$$ or $$$p^3$$$ for some primes $$$p$$$ and $$$q$$$. In the first case it have divisors $$$1$$$, $$$p$$$, $$$q$$$, $$$pq$$$. In the second case it have divisors $$$1$$$, $$$p$$$, $$$p^2$$$, $$$p^3$$$.

Hint $$$2$$$: Instead of finding integer with at least $$$4$$$ divisors, find integer with exactly $$$4$$$ divisors.

Hint $$$3$$$: Let $$$p$$$ be the smallest prime factor of $$$a$$$. Then, $$$p \geq d + 1$$$.

104840809

Hint $$$1$$$: How does $$$x$$$ changes after each operation?

Hint $$$2$$$: Suppose, that you know $$$x$$$. What pairs of elements can you throw out now?

Hint $$$3$$$: Suppose, that you did some operations. Note, that if you have integer $$$b$$$ that is greater or equal to $$$x$$$ and $$$b$$$ is still in array $$$a$$$, you can't remove $$$b$$$ from $$$a$$$, thus you can't throw out all elements of $$$a$$$.

Hint $$$4$$$: You don't know $$$x$$$ only before the first operation and $$$n \leq 1000$$$.

Solution with set

Solution without set

Hint $$$1$$$: How to solve the promblem if we are not allowed to use a superabilty (in linear time)?

Hint $$$2$$$: Look at the first pile. There is only one way to remove stone from the first pile.

Hint $$$3$$$: If you swap $$$i$$$-th and $$$(i + 1)$$$-th piles of stones, nothing changes in way you remove stones from $$$1$$$-st, $$$2$$$-nd, $$$\ldots$$$, $$$(i - 2)$$$-th piles.

Hint $$$4$$$: Look at the problem from the both sides: from the beginning of $$$a$$$ and from the end of $$$a$$$.

104840665

Hint $$$1$$$: How many operations will robot make in the worst case?

Hint $$$2$$$: How many times can robot spend $$$(n - 1)^2$$$ time on $$$1$$$ operation?

Hint $$$3$$$: How many times can robot spend $$$(n - 2)^2$$$ time on $$$1$$$ operation? It is easyer to think about number of operations with time greater or equal to $$$(n - 2)^2$$$.

Hint $$$4$$$: Instead of operation from the statement we can apply the following operation to $$$q$$$ which is initially an identity permutation:

• Select $$$i$$$ such that $$$q_i = i$$$ and any $$$j$$$ and swap $$$q_i$$$ and $$$q_j$$$ in $$$(j - i) ^ 2$$$ seconds.

Then we make $$$p$$$ = $$$q$$$ and do operations in reversed order.

104840536

Can you solve this problem with a bigger $$$n$$$?

104840452