Codeforces Round 154 (Div. 2) |
---|
Закончено |
Нехотя, тыкая пальцами в кнопки на клавиатуре, Вася выдавливает из себя скудные мысли по поводу того, о чем же думал Андрей Болконский, глядя на небо Аустерлица... Ну как объяснить учительнице по литературе, что Вася не собирается становиться писателем, а хочет стать программистом. Поэтому программу он напишет с удовольствием, а вот сочинение дается ему с трудом.
Пока Вася думал о том, как выудить из себя очередное предложение, ему в голову пришел неожиданный вопрос: а какое наименьшее количество нажатий на кнопки ему нужно сделать, чтобы переместить курсор из одной позиции в другую?
Опишем его вопрос более формально: для набора текста Вася использует текстовый редактор. Он уже написал n строчек, в i-й строке написано ai символов (включая пробелы). Если в некоторой строке записано k символов, то всего в этой строке существует (k + 1) позиция, в которой может находиться курсор: перед каким-то символом или после всех символов (в конце строки). Таким образом, положение курсора задается парой чисел (r, c), где r — номер строки, а c — позиция курсора в ней (позиции нумеруются с единицы от начала строки).
Для перемещения курсора Вася не использует мышь. Он использует клавиши «Вверх», «Вниз», «Вправо» и «Влево». При нажатии на каждую из этих клавиш курсор перемещается следующим образом. Пусть до нажатия соответствующей клавиши курсор находился в позиции (r, c), тогда после нажатия клавиши:
Вам задано количество строк в текстовом файле и количество символов, записанное в каждой строке этого файла. Найдите наименьшее количество нажатий описанных выше клавиш, требуемое для того, чтобы переместить курсор из положения (r1, c1) в положение (r2, c2).
В первой строке входных данных записано целое число n (1 ≤ n ≤ 100) — количество строк в файле. Во второй строке записано n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 105), разделенных одиночными пробелами. В третьей строке записано четыре целых числа r1, c1, r2, c2 (1 ≤ r1, r2 ≤ n, 1 ≤ c1 ≤ ar1 + 1, 1 ≤ c2 ≤ ar2 + 1).
Выведите единственное число — наименьшее количество нажатий, требуемое для того, чтобы переместить курсор из положения (r1, c1) в положение (r2, c2).
4
2 1 6 4
3 4 4 2
3
4
10 5 6 4
1 11 4 2
6
3
10 1 10
1 10 1 1
3
В первом примере в редакторе записаны четыре строки. Обозначим цифрами возможные позиции курсора в строке. Буквой s обозначим начальную позицию курсора, буквой t — конечную. Тогда все возможные положения курсора в текстовом редакторе описываются следующей таблицей.
123
12
123s567
1t345
Один из возможных ответов в данном примере: «Влево», «Вниз», «Влево».
Название |
---|