Jolly Jumpers..~

Problem Statement
     
A permutation p[0], p[1], ..., p[n-1] is a sequence containing each number from 0 to n-1 exactly once. The result of applying permutation p to an array a of length n is an array b of length n, where b[p[i]] = a[i] (0-based indices). Given an array a, find a permutation which has the effect of sorting the elements of a in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations return the lexicographically smallest one. The permutation p[0], p[1], ..., p[n-1] is considered lexicographically smaller than the permutation q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.
Definition
   
Class:
SortingWithPermutation
Method:
getPermutation
Parameters:
vector <int>
Returns:
vector <int>
Method signature:
vector <int> getPermutation(vector <int> a)
(be sure your method is public)
   
 
Constraints
-
a will contain between 1 and 50 elements, inclusive.
-
Each element of a will be between 1 and 1000, inclusive.
Examples
0)
 
   
{2, 3, 1}
Returns: {1, 2, 0 }
The element that is originally at position 0 goes to position 1. The elements originally at positions 1 and 2 go to positions 2 and 0, respectively.
1)
 
   
{2, 1, 3, 1}
Returns: {2, 0, 3, 1 }
There are two suitable permutations - {2, 0, 3, 1} and {2, 1, 3, 0}. The first one is lexicographically smaller.
2)
 
   
{4, 1, 6, 1, 3, 6, 1, 4}
Returns: {4, 0, 6, 1, 3, 7, 2, 5 }
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
A number is called square-free if it is not divisible by a perfect square which is greater than one. A perfect square is the square of an integer. Return the number of square-free numbers between min and max, inclusive.
Definition
   
Class:
SquareFreeNumbers
Method:
getCount
Parameters:
long long, long long
Returns:
int
Method signature:
int getCount(long long min, long long max)
(be sure your method is public)
   
 
Constraints
-
min will be between 1 and 1,000,000,000,000, inclusive.
-
max will be between min and (min + 1,000,000), inclusive.
Examples
0)
 
   
1
10
Returns: 7
Numbers 4, 8 and 9 are not square-free.
1)
 
   
15
15
Returns: 1
min and max can be equal.
2)
 
   
1
1000
Returns: 608
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
You wish to group a list of numbers into pairs such that the sum of each pair is prime. For example, given the numbers { 1, 4, 7, 10, 11, 12 }, you could group them as follows:
1 + 4 = 5
7 + 10 = 17
11 + 12 = 23
or:
1 + 10 = 11
4 + 7 = 11
11 + 12 = 23
Given a vector <int> numbers, return a vector <int> of all the elements in numbers that could be paired with numbers[0] successfully as part of a complete pairing, sorted in ascending order. Note that in the example above, even though 1 + 12 is prime, there would be no way to pair the remaining 4 numbers. So the answer for the example above would be { 4, 10 }.
Definition
   
Class:
PrimePairs
Method:
matches
Parameters:
vector <int>
Returns:
vector <int>
Method signature:
vector <int> matches(vector <int> numbers)
(be sure your method is public)
   
 
Notes
-
A prime number is a number divisible only by 1 and itself.
Constraints
-
numbers will contain an even number of elements, between 2 and 50, inclusive.
-
Each element of numbers will be between 1 and 1000, inclusive.
-
Each element of numbers will be distinct.
Examples
0)
 
   
{ 1, 4, 7, 10, 11, 12 }
Returns: {4, 10 }
This is the example from the problem statement.
1)
 
   
{ 11, 1, 4, 7, 10, 12 }
Returns: {12 }
The same numbers, but in a different order. In both of the 2 possible complete pairings, the 11 is paired with the 12.
2)
 
   
{ 8, 9, 1, 14 }
Returns: { }
No complete pairings are possible because none of the numbers can be paired with 1.
3)
 
   
{ 34, 39, 32, 4, 9, 35, 14, 17 }
Returns: {9, 39 }
 
4)
 
   
{ 941, 902, 873, 841, 948, 851, 945, 854, 815, 898,
  806, 826, 976, 878, 861, 919, 926, 901, 875, 864 }
Returns: {806, 926 }
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.