codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```