Hint $$$1$$$: Следует ли всегда делать первую цифру $$$d$$$ не равной $$$0$$$? Как это можно сделать?

Hint $$$2$$$: Попробуйте выбрать такое $$$a$$$, что $$$d$$$ будет состоять ровно из $$$n$$$ цифр.

104840922

Hint $$$1$$$: Число имеет $$$4$$$ делителей, если оно равно $$$pq$$$ или $$$p^3$$$ для некоторых простых $$$p$$$ и $$$q$$$. В первом случае его делители равны $$$1$$$, $$$p$$$, $$$q$$$, $$$pq$$$. Во втором случае его делителями являются $$$1$$$, $$$p$$$, $$$p^2$$$, $$$p^3$$$.

Hint $$$2$$$: Вместо поиска числа с хотя бы $$$4$$$ делителями, попробуйте найти число с ровно $$$4$$$ делителями.

Hint $$$3$$$: Пусть $$$p$$$ — наименьший простой делитель $$$a$$$. Тогда, $$$p \geq d + 1$$$ выполняется.

104840809

Hint $$$1$$$: Как $$$x$$$ меняется после каждой операции?

Hint $$$2$$$: Пусть Вы знаете $$$x$$$. Какие элементы можно сейчас выкинуть?

Hint $$$3$$$: Пусть Вы сделали несколько операций. Заметьте, что если есть число $$$b$$$, большее или равное $$$x$$$ и $$$b$$$ всё ещё в $$$a$$$, Вы не можете удалить $$$b$$$ из $$$a$$$, а значит Вы не можете выкинуть все элементы $$$a$$$.

Hint $$$4$$$: Вы не знаете $$$x$$$ только перед первой операцией и $$$n \leq 1000$$$.

Solution with set

Solution without set

Hint $$$1$$$: Как решить задачу, если нам нельзя использовать суперспособность (за линейное время)?

Hint $$$2$$$: Посмотрите на первую кучку. Есть лишь один способ убрать камни оттуда.

Hint $$$3$$$: Если Вы поменяете $$$i$$$-th и $$$(i + 1)$$$-th кучки камней, ничего не меняется в способе, которым Вы убираете камни из $$$1$$$-й, $$$2$$$-й, $$$\ldots$$$, $$$(i - 2)$$$-й кучек.

Hint $$$4$$$: Посмотрите на задачу с двух сторон: с начала $$$a$$$ и с конца $$$a$$$.

104840665

Hint $$$1$$$: Сколько операций робот сделает в худшем случае?

Hint $$$2$$$: Сколько раз робот может потратить $$$(n - 1)^2$$$ секунд на $$$1$$$ операцию?

Hint $$$3$$$: Сколько раз робот может потратить $$$(n - 2)^2$$$ секунд на $$$1$$$ операцию? Проще думать про количество операций со временем больше или равным $$$(n - 2)^2$$$.

Hint $$$4$$$: Вместо операций из условия мы можем применять следующую операцию к перестановке $$$q$$$, которая изначально тождественная:

• Выбрать $$$i$$$ такое, что $$$q_i = i$$$ и любое $$$j$$$ и поменять местами $$$q_i$$$ и $$$q_j$$$ за $$$(j - i) ^ 2$$$ секунд.

Затем мы можем сделать $$$p$$$ = $$$q$$$ и делать операции в обратном порядке.

104840536

Можете ли Вы решить задачу с большим $$$n$$$?

104840452