301353: CF253C. Text Editor

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Text Editor

题意翻译

小v正在使用文本编辑器。 他已经写了$n$行,第$i$行包含$a_i$个字符(包括空格). 如果每行包含$k$个字符,那这一行有$k+1$个光标可以达到的位置:在每个字符之前或者行末。因此,光标的位置有一对整数$(r,c)$确定,代表在第$r$行第$c$个位置。(这些位置从行的开始处开始索引。) 小v不用鼠标,他按上下左右键来控制光标。 如果光标在第一行,按上没用。 如果光标在最后一行,按下没用。 如果光标在行首,按左没用。 如果光标在行末,按右没用。 如果鼠标的位置比上一行的行末位置大,如果按上的话,移到上一行的行末。 如果鼠标的位置比下一行的行末位置大,如果按下的话,移到下一行的行末。 现在要求出$(r1,c1)$到$(r2,c2)$光标移动的最少距离。 translated by $\color{red}\texttt{2020严誉沣}$

题目描述

Vasya is pressing the keys on the keyboard reluctantly, squeezing out his ideas on the classical epos depicted in Homer's Odysseus... How can he explain to his literature teacher that he isn't going to become a writer? In fact, he is going to become a programmer. So, he would take great pleasure in writing a program, but none — in writing a composition. As Vasya was fishing for a sentence in the dark pond of his imagination, he suddenly wondered: what is the least number of times he should push a key to shift the cursor from one position to another one? Let's describe his question more formally: to type a text, Vasya is using the text editor. He has already written $ n $ lines, the $ i $ -th line contains $ a_{i} $ characters (including spaces). If some line contains $ k $ characters, then this line overall contains $ (k+1) $ positions where the cursor can stand: before some character or after all characters (at the end of the line). Thus, the cursor's position is determined by a pair of integers $ (r,c) $ , where $ r $ is the number of the line and $ c $ is the cursor's position in the line (the positions are indexed starting from one from the beginning of the line). Vasya doesn't use the mouse to move the cursor. He uses keys "Up", "Down", "Right" and "Left". When he pushes each of these keys, the cursor shifts in the needed direction. Let's assume that before the corresponding key is pressed, the cursor was located in the position $ (r,c) $ , then Vasya pushed key: - "Up": if the cursor was located in the first line ( $ r=1 $ ), then it does not move. Otherwise, it moves to the previous line (with number $ r-1 $ ), to the same position. At that, if the previous line was short, that is, the cursor couldn't occupy position $ c $ there, the cursor moves to the last position of the line with number $ r-1 $ ; - "Down": if the cursor was located in the last line ( $ r=n $ ), then it does not move. Otherwise, it moves to the next line (with number $ r+1 $ ), to the same position. At that, if the next line was short, that is, the cursor couldn't occupy position $ c $ there, the cursor moves to the last position of the line with number $ r+1 $ ; - "Right": if the cursor can move to the right in this line ( $ c<a_{r}+1 $ ), then it moves to the right (to position $ c+1 $ ). Otherwise, it is located at the end of the line and doesn't move anywhere when Vasya presses the "Right" key; - "Left": if the cursor can move to the left in this line ( $ c>1 $ ), then it moves to the left (to position $ c-1 $ ). Otherwise, it is located at the beginning of the line and doesn't move anywhere when Vasya presses the "Left" key. You've got the number of lines in the text file and the number of characters, written in each line of this file. Find the least number of times Vasya should push the keys, described above, to shift the cursor from position $ (r_{1},c_{1}) $ to position $ (r_{2},c_{2}) $ .

输入输出格式

输入格式


The first line of the input contains an integer $ n $ ( $ 1<=n<=100 $ ) — the number of lines in the file. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=10^{5} $ ), separated by single spaces. The third line contains four integers $ r_{1},c_{1},r_{2},c_{2} $ ( $ 1<=r_{1},r_{2}<=n,1<=c_{1}<=a_{r1}+1,1<=c_{2}<=a_{r2}+1 $ ).

输出格式


Print a single integer — the minimum number of times Vasya should push a key to move the cursor from position $ (r_{1},c_{1}) $ to position $ (r_{2},c_{2}) $ .

输入输出样例

输入样例 #1

4
2 1 6 4
3 4 4 2

输出样例 #1

3

输入样例 #2

4
10 5 6 4
1 11 4 2

输出样例 #2

6

输入样例 #3

3
10 1 10
1 10 1 1

输出样例 #3

3

说明

In the first sample the editor contains four lines. Let's represent the cursor's possible positions in the line as numbers. Letter $ s $ represents the cursor's initial position, letter $ t $ represents the last one. Then all possible positions of the cursor in the text editor are described by the following table. 123 12 123s567 1t345 One of the possible answers in the given sample is: "Left", "Down", "Left".

Input

题意翻译

小v正在使用文本编辑器。 他已经写了$n$行,第$i$行包含$a_i$个字符(包括空格). 如果每行包含$k$个字符,那这一行有$k+1$个光标可以达到的位置:在每个字符之前或者行末。因此,光标的位置有一对整数$(r,c)$确定,代表在第$r$行第$c$个位置。(这些位置从行的开始处开始索引。) 小v不用鼠标,他按上下左右键来控制光标。 如果光标在第一行,按上没用。 如果光标在最后一行,按下没用。 如果光标在行首,按左没用。 如果光标在行末,按右没用。 如果鼠标的位置比上一行的行末位置大,如果按上的话,移到上一行的行末。 如果鼠标的位置比下一行的行末位置大,如果按下的话,移到下一行的行末。 现在要求出$(r1,c1)$到$(r2,c2)$光标移动的最少距离。 translated by $\color{red}\texttt{2020严誉沣}$

加入题单

上一题 下一题 算法标签: