TopCoder problem "ColorfulCards" used in SRM 495 (Division I Level One , Division II Level Two)



Problem Statement

    Rabbit Hanako has N cards numbered 1 through N. Each card's number is written on its front side. The back side of each card is colored red if the number is prime, and blue if it is not prime.



Cat Taro has chosen a subset of these cards and arranged them face down in a row. The cards are sorted in increasing order from left to right. He wants Hanako to guess the numbers written on the cards. Hanako can only see the colored back side of each card. You are given a String colors, where the i-th character is 'R' if the i-th card from the left is red, and 'B' if it is blue.



Return a int[] containing exactly K elements, where K is the number of characters in colors. The i-th element of the return must be the number written on the i-th card if it can be uniquely determined. Otherwise, the i-th element must be -1. It is guaranteed that there exists at least one sequence that matches colors.
 

Definition

    
Class:ColorfulCards
Method:theCards
Parameters:int, String
Returns:int[]
Method signature:int[] theCards(int N, String colors)
(be sure your method is public)
    
 

Notes

-A positive integer number is called prime if it has exactly two divisors, 1 and itself. By convention, 1 is not considered to be a prime number.
 

Constraints

-N will be between 1 and 1,000, inclusive.
-colors will contain between 1 and 50 characters, inclusive.
-Each character in colors will be 'R' or 'B'.
-There will exist at least one sequence that matches colors.
 

Examples

0)
    
5
"RRR"
Returns: {2, 3, 5 }
The numbers written on these cards are primes less than or equal to 5, so the only possibility is {2, 3, 5}.
1)
    
7
"BBB"
Returns: {1, 4, 6 }
The numbers written on these cards are not primes less than or equal to 7, so the only possibility is {1, 4, 6}.
2)
    
6
"RBR"
Returns: {-1, 4, 5 }
There are two possibilities:

{2, 4, 5}

{3, 4, 5}

3)
    
58
"RBRRBRBBRBRRBBRRBBBRRBBBRR"
Returns: 
{-1, -1, -1, -1, -1, -1, -1, -1, 17, 18, 19, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 47, 53 }
4)
    
495
"RBRRBRBBRBRRBBRRBBBRRBBBRR"
Returns: 
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11302

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14424&pm=11302

Writer:

rng_58

Testers:

PabloGilberto , ivan_metelsky , soul-net

Problem categories:

Greedy