Chef and Sign Sequences
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef found a strange string yesterday - a string of signs s, where each sign is either a '<', '=' or a '>'. Let N be the length of this string. Chef wants to insert N + 1 positive integers into this sequence and make it valid. A valid sequence is a sequence where every sign is preceded and followed by an integer, and the signs are correct. That is, if a sign '<' is preceded by the integer a and followed by an integer b, then a should be less than b. Likewise for the other two signs as well.
Chef can take some positive integers in the range [1, P] and use a number in the range as many times as he wants.
Help Chef find the minimum possible P with which he can create a valid sequence.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains the string of signs s, where each sign is either '<', '=' or a '>'.
For each test case, output a single line containing an integer corresponding to the minimum possible P.
- 1 ≤ T, |s| ≤ 105
- 1 ≤ Sum of |s| over all test cases in a single test file ≤ 106
Subtask #1 (30 points)
- 1 ≤ T, |s| ≤ 103
- 1 ≤ Sum of |s| over all test cases in a single test file ≤ 104
Subtask #2 (70 points)
- Original constraints
Input: 4 <<< <>< <=> <=< Output: 4 2 2 3
Here are some possible valid sequences which can be formed with the minimum P for each of the test cases:
1 < 2 < 3 < 4 1 < 2 > 1 < 2 1 < 2 = 2 > 1 1 < 2 = 2 < 3
|Tags||ad-hoc, berezin, cakewalk, greedy, july17|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.