I have been attempting this British Informatics Olympiad question for many weeks now. I tried creating all plans but this would time out very easily (and take too much memory in some cases). I tried finding first plan and then counting up but this too would time out. I checked the sample tests and the biggest numbers they had were around 2^43, so I am not sure if they want a solution much better than that. Any help would be much appreciated.↵
[cut]↵
↵
A spy, currently working their way through an enemy compound, has been given a false plan. The plan is↵
an ordered list of letters. In order to make the plan look realistic, the number of adjacent identical letters↵
in the plan has been limited.↵
For example, suppose that the plan contains four letters, each of which is an A or a B, and that there are↵
never more than two adjacent identical letters. There are 10 possible plans:↵
AABA↵
AABB↵
ABAA↵
ABAB↵
ABBA↵
BAAB↵
BABA↵
BABB↵
BBAA↵
BBAB↵
These have been listed in alphabetical order.↵
↵
Write a program to determine the nth possible plan.↵
Your program should input a line containing three integers p, q, r (1 ≤ p, q, r ≤ 12)↵
indicating (in order) that the first p letters of the alphabet can be used, no more than↵
q adjacent identical letters are permitted and that the plan should contain exactly r↵
letters. You should then input a line containing a single number n (1 ≤ n < 2^63).↵
You will only be given input where n is no greater than the number of possible plans.↵
You should output the nth possible plan. ↵
↵
(Time limit = 1 second per test).↵
↵
Sample run↵
INPUT:↵
2 2 4↵
7↵
↵
OUTPUT:↵
BABA↵
↵
[cut]↵
↵
A spy, currently working their way through an enemy compound, has been given a false plan. The plan is↵
an ordered list of letters. In order to make the plan look realistic, the number of adjacent identical letters↵
in the plan has been limited.↵
For example, suppose that the plan contains four letters, each of which is an A or a B, and that there are↵
never more than two adjacent identical letters. There are 10 possible plans:↵
AABA↵
AABB↵
ABAA↵
ABAB↵
ABBA↵
BAAB↵
BABA↵
BABB↵
BBAA↵
BBAB↵
These have been listed in alphabetical order.↵
↵
Write a program to determine the nth possible plan.↵
Your program should input a line containing three integers p, q, r (1 ≤ p, q, r ≤ 12)↵
indicating (in order) that the first p letters of the alphabet can be used, no more than↵
q adjacent identical letters are permitted and that the plan should contain exactly r↵
letters. You should then input a line containing a single number n (1 ≤ n < 2^63).↵
You will only be given input where n is no greater than the number of possible plans.↵
You should output the nth possible plan. ↵
↵
(Time limit = 1 second per test).↵
↵
Sample run↵
INPUT:↵
2 2 4↵
7↵
↵
OUTPUT:↵
BABA↵
↵
