LIAR - Truth or not

Professor Millman hates us, and worse, characterizes us as liars. We don’t care if he means it or not, but we (more professional that him!) planned to give the lower and upper bound on the number of liars in the class (so that you know what happens the next time he scolds us!)

To start with we took a survey of all students in the class. Each student gave a reply about every student saying whether that student is a liar or not. These answers are in the form of a Matrix A, where A[i][j] represents the reply given by the i-th student about the j-th student. If that character is ‘L’ – it means he/she is a liar; if it’s ‘T’ – then it means that, that student is a truth speaker.

We take the following as our definition of the terms Truth-Speaker, and Liar:
Truth-Speaker (‘T’): All his/her replies are true.
Liar (‘L’) : (S)he has made at least one false reply.

Input

T – the number of test cases; For each test case :
N – total number of students in the class
Matrix A of NxN characters, without space separation;

Output

For i-th test case output one line of the form “Class Room#i contains atleast A and atmost B liars”, where A and B are the lower and the upper bounds on the number of liars respectively. If there is a paradoxical class room, instead of the above line, print “Class Room#i is paradoxical”.

Constraints:
T<=50; Our class rooms contain at most 70 students.

Example

Sample Input:
4
2
LL
TT
3
TTT
TTT
TTT
4
TLLL
LTLL
LLTL
LLLT
5
TLTLT
TTTTT
LLTLL
LLLLL
TLTLT

Sample Output:
Class Room#1 is paradoxical
Class Room#2 contains atleast 0 and atmost 3 liars
Class Room#3 contains atleast 3 and atmost 4 liars
Class Room#4 contains atleast 4 and atmost 4 liars

 

Here a paradox occurs if a person can't be classified as a liar or a truth-speaker.


Added by:Prasanna
Date:2006-01-13
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource: ByteCode 06

hide comments
2024-08-16 03:23:27 Brian Bi
Problem description is wrong. To get AC, you have to write "atleast" instead of "at least" and "atmost" instead of "at most".
[Simes]: fixed. Thank you.

Last edit: 2024-08-18 22:48:55
2019-03-13 01:44:50
Good question
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.