BIO question 3, help needed
Difference between en2 and en3, changed 2 character(s)
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↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English PinkPandaPresident 2020-08-11 16:48:56 2 Tiny change: '.\n[cut]\nA spy, c' -> '.\n[cut]\n\nA spy, c'
en2 English PinkPandaPresident 2020-08-11 16:48:29 0 (published)
en1 English PinkPandaPresident 2020-08-11 16:47:56 1642 Initial revision (saved to drafts)