[Solution] Sequence of Comparisons solution codeforces | Kotlin Heroes: Episode 8

Sequence of Comparisons solution codeforces


Once upon a time, Petya had an array of integers aa of length nn. But over time, the array itself was lost, and only n1n−1 results of comparisons of neighboring array elements remained. In other words, for every ii from 11 to n1n−1, Petya knows exactly one of these three facts:

  • ai<ai+1ai<ai+1;
  • ai=ai+1ai=ai+1;
  • ai>ai+1ai>ai+1.

Petya wonders if it is possible to uniquely determine the result of comparing a1a1 and anan.

You have to help Petya determine the result of comparing a1a1 and anan or report that the result cannot be determined unambiguously.

Sequence of Comparisons solution codeforces Input

The first line contains a single integer tt (1t5001≤t≤500) — the number of test cases.

The only line of the test case contains the string ss (1|s|1001≤|s|≤100), where sisi is:

  • <, if ai<ai+1ai<ai+1;
  • >, if ai>ai+1ai>ai+1;
  • =, if ai=ai+1ai=ai+1.

Sequence of Comparisons solution codeforcesOutput

For each test case, print a single string equal to:

  • <, if a1<ana1<an;
  • >, if a1>ana1>an;
  • =, if a1=ana1=an;
  • ?, if it is impossible to uniquely determine the result of the comparison.

Sequence of Comparisons solution codeforces Example

input

Copy
4
>>>
<><=<
=
<<==
output

Copy
>
?
=
<

Sequence of Comparisons solution codeforces Note

Consider the test cases of the example:

  • in the first test case, it’s easy to see that a1>a4a1>a4 since a1>a2>a3>a4a1>a2>a3>a4;
  • in the second test case, both sequences [1,2,0,10,10,15][1,2,0,10,10,15] and [10,11,1,2,2,5][10,11,1,2,2,5] meet the constraints; in the first one, a1<a6a1<a6, and in the second one, a1>a6a1>a6, so it’s impossible to compare a1a1 and a6a6;
  • in the third test case, we already know that a1=a2a1=a2;
  • in the fourth test case, it’s easy to see that a3=a4=a5a3=a4=a5, and a1<a2<a3a1<a2<a3, so a1<a5a1<a5.

Sequence of Comparisons solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment