All submissions for this problem are available.
Ram and Arun are playing a guessing game. According to the game, Arun must pick an arbitrary positive integer n(1<=n<=109) and should give Ram exactly k hints about the value of n. It is Ram's turn to guess the value of n, based on the k hints given by Arun. Ram often had a serious problem guessing the correct value of n, and he started to suspect that Arun may be cheating, that is, he may be providing him incorrect hints. After the last game, Ram says Arun with the utmost certainty that in the last game he has lied to him at least *** times. So, how many times at least did Arun lie to Ram? Try to determine this, knowing only the hints Arun gave to Ram.
The first line of input contains t, the number of test cases (about 20). Exactly t test cases must be given after that. Each test case starts with a line containing a single integer k, the number of hints given by Arun (1<=k<=100000). Each of the next k lines contains exactly one hint each. The i-th hint is of the form:
operator li logical_value
operator denotes one of the symbols < , > , or =;
li is an integer (1<=li<=109),
while logical_value is one of the words: Yes or No.
The hint is considered correct if logical_value is the correct reply to the question: "Does the relation: n operator li hold?", and is considered to be false (a lie) otherwise.
For each test case output a line containing a single integer, equal to the minimal possible number of Arun's lies during the game..
Input: 3 2 < 100 No > 100 No 3 < 2 Yes > 4 Yes = 3 No 6 < 2 Yes > 1 Yes = 1 Yes = 1 Yes > 1 Yes = 1 Yes Output: 0 1 2
For the respective test cases, the number picked by Arun could have been e.g. n=100, n=5, and n=1.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.