GuessTheNumberGame
TCO11 Round 2 · 2011-05-07 · by soul-net
Problem Statement
You are playing the funny game "Guess the number" with a friend. In this game, one of the players chooses 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.
Note that some sequences of clues are invalid. For instance, the sequence "NYYY" is invalid because all integers are multiples of 1, and therefore the starting element cannot be an "N". Also, a sequence like "YNNY" is invalid because the answer cannot be a multiple of 4, but not a multiple of 2.
You will be given an
Notes
- Returning the answer modulo 1000000007 means returning the remainder of dividing the answer by 1000000007.
Constraints
- n will be between 1 and 1000000 (10^6), inclusive.
5 Returns: 12
The possible clues are: YNNNN YNNNY YNYNN YNYNY YYNNN YYNNY YYNYN YYNYY YYYNN YYYNY YYYYN YYYYY
16 Returns: 240
1 Returns: 1
1000000 Returns: 677298706
2 Returns: 2
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GuessTheNumberGame with a public method int possibleClues(int n) · 107 test cases · 2 s / 256 MB per case