Computer geeks! Show off your skills and claim the job of your dreams! RecruitCoders.com

SPOJ Problem Set (classical)

7190. Guess the Number

Problem code: GUESSTHE

You are playing the funny game “Guess the number” with a friend. In this game, one of the
players choose a positive integer and the other has to guess it by using the clues that are
revealed. The i-th clue is either “Y” or “N” indicating whether the hidden number is a multiple
of i or not, respectively. For instance, if the clues so far are “YYNYY” it means that the number
is a multiple of 1, 2, 4 and 5, but it is not a multiple of 3. Given the clues of the game so
far, you have to guess the minimum possible number according to them, or call your friend a
cheater if there is no number such that the clues were correctly given.

Input

The input contains several test cases. Each test case is described in a single line that contains
a non-empty string of at most 20 characters. The string is formed entirely of uppercase letters
“Y” and “N”, and represents the clues given so far, in order from left to right. The last line of
the input contains a single asterisk and should not be processed as a test case.

Output

For each test case output a single line with the minimum positive integer that satisfies all the
clues, or −1 if there is no such a number.

Example

Input:
YYNYY
YYYNNN
*

Output:
20
-1

Added by:	Pablo Ariel Heiber
Date:	2010-08-19
Time limit:	3s
Source limit:	50000B
Languages:	All except: PERL 6
Resource:	FCEyN UBA ICPC Selection 2008

hide comments



2012-05-09 16:45:35 Jared Deckard My AC gets 232792560 for YYYYYYYYYYYYYYYYYYYY, using int.
2012-01-03 09:19:26 Jitesh Can nyone post some more test cases.....I don't know why m I getting a WA even sfter using long long int.....
2011-10-10 17:57:51 accept simple problem
2011-09-25 20:51:22 RAJDEEP GUPTA Use long long int(for the answer) in C. I got WA for using int. Got AC after using long long int.
2010-09-01 02:27:01 Patrick Klitzke I also agree that 1s is just fine. My C++ solution runs in 0.03 seconds and I do not think that java is more than thirty times slower than C++. You just have to think about a fast algorithm
2010-09-01 02:27:01 Mitch Schwartz 1s was fine for Java. I'm glad my original solution got rejected for TLE (now AC at 1.17 s) because it forced me to find a better way and not be too lazy. :)
2010-09-01 02:27:01 Pablo Ariel Heiber I just submitted a java translation of my C++ solution and passed in 0.91. I raised the limit to 3s to give more margin, but I think it wasn't THAT low.