Решение задачи Столбы с Codeforces
Без пояснения   Просмотров: 70
Перед вами стоят в ряд n столбов, пронумерованных от 1 до n.
Изначально на каждый столб надет ровно один диск. Радиус диска, надетого на i-й столб, равен ai.
Вы можете перемещать диски с одних столбов на другие. Вы можете взять диск со столба i и надеть его на столб j, если все следующие условия выполняются:
между столбами i и j нет других столбов. Формально, это означает, что |i−j|=1;
на столб i надет ровно один диск;
либо столб j пуст (на нем нет дисков), либо радиус самого верхнего диска на столбе j строго больше радиуса того диска, который вы перемещаете.
Когда вы надеваете диск на столб, на котором уже есть другие диски, вы располагаете новый диск поверх всех предыдущих, и если вы попытаетесь позже надеть еще один диск на этот столб, именно радиус последнего надетого диска будет сравниваться с радиусом диска, который вы перемещаете, в третьем условии.
Вы можете перемещать диски столько раз, сколько вам нужно, при условии, что все три условия выполняются при каждом вашем действии. Теперь вы хотите узнать, можно ли все n дисков надеть на один и тот же столб?
Изначально на каждый столб надет ровно один диск. Радиус диска, надетого на i-й столб, равен ai.
Вы можете перемещать диски с одних столбов на другие. Вы можете взять диск со столба i и надеть его на столб j, если все следующие условия выполняются:
между столбами i и j нет других столбов. Формально, это означает, что |i−j|=1;
на столб i надет ровно один диск;
либо столб j пуст (на нем нет дисков), либо радиус самого верхнего диска на столбе j строго больше радиуса того диска, который вы перемещаете.
Когда вы надеваете диск на столб, на котором уже есть другие диски, вы располагаете новый диск поверх всех предыдущих, и если вы попытаетесь позже надеть еще один диск на этот столб, именно радиус последнего надетого диска будет сравниваться с радиусом диска, который вы перемещаете, в третьем условии.
Вы можете перемещать диски столько раз, сколько вам нужно, при условии, что все три условия выполняются при каждом вашем действии. Теперь вы хотите узнать, можно ли все n дисков надеть на один и тот же столб?