Problem Of The Week (4/10/2009)

Popular Friend

Problem Statement

You want to find the most popular person in a social network (orkut, for example). To do this, you will count the number of "M-friends" that each person has. Person A is called an M-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of M-friends. (There might be more than one if multiple people all have the maximal number of M-friends).

Input

The first line in input will contain an integer T. T test cases follow. In each test case first line consists of an integer S, denoting the size of the social network. Then S lines follow, each containing S characters (making a complete SxS matrix, call it friends[][]). Each character is either 'N' or 'Y'.

If the ith character of the jth line is 'Y' this means i and j are friends (hence jth character of ith line will also be 'Y').

Output

Output a single integer P for each case representing the number of M-friends of the most popular person in this social network.




Constraints

• 1<=S<=50

Sample

Input

5
3
NNN
NNN
NNN
3
NYY
YNY
YYN
5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN
10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN
15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

Output
 

0
2
4
8
6

Explanations:

1. Here, there are 3 people and none of them are friends, so everybody has zero M-friends.
2. Each person has two M-friends.
3. Persons 0 and 4 have two M-friends, persons 1 and 3 have three M-friends. Person 2 is the most popular one - four M-friends.

Mooshak Clarifications

1. You have to register using your h200XXXX or f200XXXX id as username
and h200XXXX@bits-pilani.ac.in email-id only.
(Email to external email services not working, and
IDs except BITS ID will not be excepted).

2. You have to read from Standard Input and write to Standard Output. For example:

In C: 
...

int input input_integer, output_integer;
...
scanf("%d",&input_integer);
//for integer input
//see Input section in Problem Statement for
//input description.
...
...
printf("%d\n",output_integer);
...

In C++:
...
char input_character, output_character;
std::cin.get(input_character);
//read indivisual charecters and then integrate them.
//there are better ways too.
...
...
std::cout.put(output_character);
...

In Java:
...
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));

String input_line;
input_line=r.readLine();
//might have to be executed iteratively using r.read(char [], 0, 1) till
//white_space or end_of_line or end_of_file.
...
...
System.out.println(output_value);
...

In Python:
...
input_variable=raw_input()
...
print output_variable
...

Testing on your own pc:
Now, to test the cases in your own system, you'll have to generate a testcase file (simply copy the sample input). Let's assume it is input.txt.
Also, you want to save output in a file output.txt.
Use input output redirection. Example:

gcc mycode.c
./a.out< input >output.txt

g++ mycode.cpp
./a.outoutput.txt


javac mycode.java
java mycode output.txt

python mycode.py output.txt

Please note that commands and convensions will change according to OS used.

Mooshak Started!

The online compiler, mooshak has started working!
Check-it-out!

http://172.17.9.144/~mooshak/

it'll be up all night tonight!
from tomorrow, i'll follow the timings mentioned in the previous post.

How to login?

You'll have to first register,
on the login page,
1. Go to http://172.17.9.144/~mooshak/ (Add to proxy exception list first)
and click login.


2.Then, Click Register:



3. Then in the name section, fill your bits id (h2008.... or f2008... etc).
in email section, fill your bits-email-id.
then in groups select BITS (Important).
then click submit.



4. Check email, use the password to login.

Important Notes & Rules for the contest:-

0.The program should read from standard input and give output to standard output. Format of INPUT is given in all problems specifically.

1.Top 10 correct Entries will be Published for each PTW on every Friday 10 PM. Entries BEFORE Friday 5PM will be ACCEPTED as valid. Every Friday 11 PM a new problem will come for that week.

**2.Special prize for Top 5 Rankers…J

3.Any ME_CS_BITS @googlegroups group Member,Except the Coordinators of DSAR
can participate.

4. Participation will be through mooshak server. see above post for details.

5.Programming Languages allowed -- C,C++, Java, Python.

7.Rules of the contest is subject to change depending upon circumstances.

8.For details go to ---> http://www.ds-ar.blogspot.com/

9.If you have any doubts/suggestions please shoot a mail to dsa[dot]bits[at]gmail[dot]com. This is important for us.

P.S:-

** This is applicable for "Problem of the week"-1 as of now.

Problem of The Week (18/09/2009)

QuickSums

Problem Statement

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual.

For example, consider the string "12" (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03".

You can do this because leading zeros do not change the result.

If this is impossible, return -1.

Input

First line contains a single integer T. T number of cases follow. Each case consists of a string of digits S and the target integer R.

Output

Output must contain T lines, corresponding to each test case, each line K must contain an integer P corresponding to the minimum number of additions required in the string S, of the Kth input, to equal integer R, of the Kth input.

Constraints
1 <= Number of characters in S <= 10
0 <= R <= 100

Sample

Input

6
99999 45
1110 3
0123456789 45
99999 100
382834 100
9230560001 71

Output

4
3
8
-1
2
4

Notes:

Case 1) In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions.
Case 2) Be careful with zeros. 1+1+1+0=3 and requires 3 additions.
Case 4) When sum not possible, output should be -1
Case 5) There are 3 ways to get 100. They are 38+28+34, 3+8+2+83+4 and 3+82+8+3+4. The minimum required is 2.