Remote Training on Programming

На реке имеется N островков, пронумерованных от 1 до N слева направо поперек реки. Жители должны пересечь реку, начиная с ее левого берега, используя некоторые островки для достижения правого берега. Левый берег расположен на одну позицию левее первого островка, а правый берег расположен на одну позицию правее островка с номером N. В момент времени t житель находится на левом берегу реки и имеет целью добраться до правого берега за минимальное время. В каждый момент времени каждый из островков поднят или опущен и житель стоит на островке или на берегу. Житель может стоять на островке только тогда, когда он поднят. Такой островок называется доступным. В начальный момент времени каждый островок опущен, затем островок поднят в течение A моментов времени, затем опущен в течение B моментов времени, поднят A моментов, опущен B и т.д. Константы A и B задаются отдельно для каждого островка. Например, островок C с A_c = 2 и B_c = 3 опущен в момент времени 0, поднят в моменты времени 1 и 2, опущен в моменты времени 3, 4 и 5 и т.д. В момент времени t + 1 житель может выбрать островок или берег в пределах 5 ближайших с каждой стороны от его местоположения в момент времени t позиций или остаться на месте (если соответствующий островок не уходит под воду в момент t + 1).

Необходимо вычислить минимальный момент достижения правого берега, или установить, что это невозможно.