Jolly Jumpers..~

Problem Statement
     
John is obsessed with security. Recently he bought a new electronic lock. It is protected by a password containing n digits, where each digit is either zero or one. John decides to change the password every day. On the first day, the password is all zeroes. On each day that follows, he will select one or more digits that all have the same value and change their values (so zeroes become ones, and ones become zeroes). He must select the digits according to the following rules:
During the first 2^n days, he must never use the same password twice.
Each new password must come as early as possible alphabetically while not violating rule 1.
For example, if n is 2, the password on the first day is "00". The next day, he can change one or both 0's to get "01", "10" or "11". Of these possibilities, "01" comes earliest alphabetically. The next day, he can change either the 0 or the 1 to get "11" or "00". He can't choose "00" because it was already used, so he chooses "11". The next day, he can change one or both 1's to get "10", "01" or "00". He has already used "01" and "00", so he must choose "10".
Given ints n and k, return the password that comes latest alphabetically during the first k days.
Definition
   
Class:
TheLockDivOne
Method:
password
Parameters:
int, long long
Returns:
string
Method signature:
string password(int n, long long k)
(be sure your method is public)
   
 
Notes
-
If A and B are two strings of the same length, then A comes earlier alphabetically than B if it contains a smaller character at the first position where the strings differ.
Constraints
-
n will be between 1 and 50, inclusive.
-
k will be between 1 and 2^n, inclusive.
Examples
0)
 
   
2
4
Returns: "11"
This is the example from the statement. The password sequence is the following - "00", "01", "11", "10".
1)
 
   
3
8
Returns: "111"
"000", "001", "011", "010", "110", "100", "101", "111".
2)
 
   
4
6
Returns: "0110"
 
3)
 
   
10
1
Returns: "0000000000"
 
4)
 
   
7
100
Returns: "1111110"
 
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
     
John is obsessed with security. He is writing a letter to his friend Brus and he wants nobody else to be able to read it. He uses a simple substitution cipher to encode his message. Each letter in the message is replaced with its corresponding letter in a substitution alphabet. A substitution alphabet is a permutation of all the letters in the original alphabet. In this problem, the alphabet will consist of only lowercase and uppercase letters ('a'-'z', 'A'-'Z').
John wants to be sure that his encryption is safe, so he will not choose a cipher where a letter is encoded to either itself or to its lowercase or uppercase equivalent. For example, he will not choose a cipher where the letter 'j' is encoded to either 'j' or 'J'.
Given the original message msg and encoded message encMsg, determine the number of simple substitution ciphers that fit John's requirements and encode msg to encMsg. Return this number modulo 1234567891.
Definition
   
Class:
TheEncryptionDivOne
Method:
count
Parameters:
string, string
Returns:
int
Method signature:
int count(string msg, string encMsg)
(be sure your method is public)
   
 
Constraints
-
msg will contain between 1 and 50 characters, inclusive.
-
msg and encMsg will contain the same number of characters.
-
msg and encMsg both will contain only lowercase and uppercase letters ('a' - 'z', 'A' - 'Z').
Examples
0)
 
   
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: 2
Here we have to choose how to encode to letters 'Y' and 'Z' with two letters 'a' and 'b'. There are two ways to do it.
1)
 
   
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY"
Returns: 1
And here John needs to encode 'Y', 'Z' with 'Z' and 'a'. He cannot map 'Z' to itself, so there is only one possible encoding.
2)
 
   
"topcoder"
"TOPCODER"
Returns: 0
 
3)
 
   
"thisisaveryhardproblem"
"nobodywillsolveittoday"
Returns: 0
 
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.