2169B.md (2245B)
1 Source: https://codeforces.com/problemset/problem/2169/B 2 3 B. Drifting Away 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There's a river flowing in front of Monocarp's house, which can be represented as a strip of cells. In some cells, there is a strong current, while in others, there is no current. It can be represented as a string $s$, consisting of the following characters: 22 23 * the "less-than" sign ('<') — leftward current; 24 * the "greater-than" sign ('>') — rightward current; 25 * an asterisk ('*') — no current. 26 27 At first, Monocarp chooses the cell to start his journey along the river at. 28 29 If there is a current in the cell, where Monocarp is at the moment, he is carried to the neighboring cell in the direction of the current. If there is no neighboring cell (i. e., a leftward current in cell $1$ or a rightward current in cell $n$), Monocarp ends up on the shore. Each move takes one minute. 30 31 If there is no current in the cell, where Monocarp is at the moment, he rows to the neighboring cell on the left or to the neighboring cell on the right. If there is no neighboring cell in the direction where Monocarp decides to row to, he ends up on the shore. Each move also takes one minute. 32 33 Monocarp wants to sail along the river for as long as possible. If Monocarp can sail infinitely, print $-1$. Otherwise, print the maximum time Monocarp can sail along the river before ending up on the shore. 34 35 Input 36 37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 38 39 The only line of each test case contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting only of characters '<' (leftward current), '>' (rightward current), '*' (no current). The ASCII codes are $60$, $62$, and $42$, respectively. 40 41 An additional constraint on the input: the total length of strings $s$ over all test cases does not exceed $3 \cdot 10^5$. 42 43 Output 44 45 For each test case, output a single integer: 46 47 * $-1$, if Monocarp can sail along the river infinitely; 48 * the maximum time Monocarp can sail along the river before ending up on the shore, otherwise. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 ***** 58 59 <<<> 60 61 >*< 62 63 * 64 ``` 65 66 Output 67 68 ``` 69 -1 70 71 3 72 73 -1 74 75 1 76 ```