GUESSTHE - Guess the Number

no tags 

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

hide comments
vikke: 2016-04-01 07:04:21

nice problem finally gcd function give ac

pvsmpraveen: 2016-01-30 07:39:37

AC 0.00 Easy one! ;)

Last edit: 2016-01-30 07:40:06
newbie: 2015-11-13 23:30:02

ac in 0.01 with long long
be careful if u use unsigned long long
-1 will also be there in some cases
consider
YYYYNN
-1
YYYYYYYYYY... 20 TIMES
232792560

Shashank Tiwari: 2015-10-31 11:33:03

So, here's the tip :

1. INT wont work here. Answer is Bigger than that. Use Unsigned Long Long.
2. I dont knw who said that string length can be more than 20 , but 20 is sufficient. It works completely fine. Ya, in case In C use size 21 for '\0'.
3. Check for this test case : YNNY , answer should be -1.

Last edit: 2015-10-31 11:33:38
RADHE SHYAM LODHI: 2015-09-01 13:35:01

use ULL

dwij28: 2015-08-28 18:35:46

Take care of the case when the string consists of only 'Y' repeatedly or only 'N' repeatedly. Cost me 2 NZEC and 15 mins.

Dushyant Singh: 2015-07-18 12:38:58

@headfirstcoder: There are at max 20 characters only. Problem may arise if you are not considering \0 in character array.
@ Harshit : It depends how user calculates the answer. In one case there will be overflow and in the other there will be no overflow.

[Mayank Pratap]: 2015-06-18 05:44:45

Completed Double century by some guess work ... :P

Harshit: 2015-06-13 16:10:35

No use of long long int..

---@@@----: 2015-05-30 17:40:57

AC after lot of WA's cause of silly mistake..
Otherwise its easy one..


Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:2.950s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS objc PERL 6 VB.net
Resource:FCEyN UBA ICPC Selection 2008