Thank you for participating in the contest! I hope you enjoyed the tasks. Here is an editorial with hints. I will upload solutions in C++ later.
1474A - Puzzle From the Future
Hint $$$1$$$ Hint $$$1$$$: Should we always make first digit of $$$d$$$ not equal to $$$0$$$? How can we do it?
Hint $$$2$$$ Hint $$$2$$$: Try to choose such $$$a$$$ that $$$d$$$ will have $$$n$$$ digits.
Solution Not available now.
1474B - Different Divisors
Hint $$$1$$$ 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$$$ Hint $$$2$$$: Instead of finding integer with at least $$$4$$$ divisors, find integer with exactly $$$4$$$ divisors.
Hint $$$3$$$ Hint $$$3$$$: Let $$$p$$$ be the smallest prime factor of $$$a$$$. Then, $$$p \geq d + 1$$$.
Solution Not available now.
1474C - Array Destruction
Hint $$$1$$$ Hint $$$1$$$: How does $$$x$$$ changes after each operation?
Hint $$$2$$$ Hint $$$2$$$: Suppose, that you know $$$x$$$. What pairs of elements can you throw out now?
Hint $$$3$$$ 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$$$ Hint $$$4$$$: You don't know $$$x$$$ only before the first operation and $$$n \leq 1000$$$.
Solution Not available now.
1474D - Cleaning
Hint $$$1$$$ Hint $$$1$$$: How to solve the promblem if we are not allowed to use a superabilty (in linear time)?
Hint $$$2$$$ Hint $$$2$$$: Look at the first pile. There is only one way to remove stone from the first pile.
Hint $$$3$$$ 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$$$ Hint $$$4$$$: Look at the problem from the both sides: from the beginning of $$$a$$$ and from the end of $$$a$$$.
Solution Not available now.
1474E - What Is It?
Hint $$$1$$$ Hint $$$1$$$: How many operations will robot make in the worst case?
Hint $$$2$$$ Hint $$$2$$$: How many times can robot spend $$$(n - 1)^2$$$ time on $$$1$$$ operation?
Hint $$$3$$$ 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$$$ 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.
Tutorial is loading...
Solution Not available now.
1474F - 1 2 3 4 ...
Bonus Can you solve this problem for a bigger $$$n$$$?
Solution Not available now.
Good luck in your future contests!
