День 5 — быстрый.

Предыдущие части:
День 1
День 2
День 3
День 4

Проблема первая:

От процессора поступает срочное прерывание: он застрял в лабиринте инструкций перехода, и ему нужна помощь любых программ с запасными циклами, чтобы помочь найти выход.

Сообщение включает в себя список смещений для каждого перехода. Переходы относительные: -1 переходит к предыдущей инструкции, а 2 пропускает следующую. Начните с первой инструкции в списке. Цель состоит в том, чтобы следовать за прыжками, пока один из них не окажется за пределами списка.

Кроме того, эти инструкции немного странные; после каждого перехода смещение этой инструкции увеличивается на 1. Итак, если вы встретите смещение 3, вы переместитесь на три инструкции вперед, но измените его на 4 в следующий раз, когда оно встретится.

Например, рассмотрим следующий список смещений перехода:

0
3
0
1
-3

Положительные скачки («вперед») движутся вниз; отрицательные скачки движутся вверх. Для удобочитаемости в этом примере все эти значения смещения будут записаны в одной строке, а текущая инструкция будет отмечена в круглых скобках. Прежде чем будет найден выход, необходимо предпринять следующие шаги:

(0) 3 0 1 -3 – до каких-либо действий.

(1) 3 0 1 -3 - прыгать со смещением 0 (то есть вообще не прыгать). К счастью, инструкция затем увеличивается до 1.

2 (3) 0 1 -3 - шаг вперед из-за инструкции, которую мы только что изменили. Первая инструкция снова увеличивается, теперь до 2.

2 4 0 1 (-3) - прыгнуть до конца; оставить 4 позади.

2 (4) 0 1 -2 - вернуться туда, где мы только что были; увеличить -3 до -2.

2 5 0 1 -2 - прыгнуть на 4 шагов вперед, выйдя из лабиринта.

В этом примере выход достигается за 5 шагов.

Сколько шагов нужно, чтобы добраться до выхода?

Проблема вторая:

Теперь прыжки стали еще более странными: после каждого прыжка, если смещение было три или больше, вместо этого уменьшайте его на 1. В противном случае увеличьте его на 1, как и раньше.

Используя это правило в приведенном выше примере, процесс теперь занимает 10 шагов, а значения смещения после нахождения выхода остаются равными 2 3 2 3 -1.

Сколько шагов нужно пройти, чтобы добраться до выхода?

Решение:

Увидимся завтра!

SR.