For this problem we are indebted to kindness of our colleague Clive Fraser aka CSFPython!
At a children's party the children all have an opportunity to choose a present before going home. The host of
the party thought up a novel way of allowing the children to choose their presents. The presents were arranged
on a circular carousel that allowed the children to see the presents one at a time as the carousel rotated.
Behind each present was an alphabetic letter to mark the position of the present on the carousel. When the
carousel rotates, present A is shown first, followed by presents B, C , D and so on. There are the same
number of presents as children.
During the party the carousel is rotated several times so that the children can see the presents and their
position on the carousel. Naturally each child decides which present they are going to choose and remembers
the letter denoting its position on the carousel. Towards the end of the party the host draws lots (secretly)
to determine the order in which the children will choose their presents. One by one they are brought into the
room with the carousel to choose a present but they do not know how many children have chosen before them. They
are told that the carousel will rotate once, starting at present A (if it is still there). The child must
choose a present before the end of the rotation is reached, otherwise they will have no present to take home.
Each child hopes that their chosen present is still there. When the corresponding letter is reached they exitedly grab their present, if it is still available. If their chosen present has already gone the child begins to panic. They were so intent on getting their chosen present that they hadn't decided what to do if it wasn't there. Knowing that they could end up without a present, they take the very next present that is still available. There is always the possibility of being able to swap it with another child after the party. We will assume that every child applies this same strategy in choosing a present. We will also assume that every child is able to choose a present before the carousel stops. (It wouldn't be nice to leave any little children without a present!)
Consider a party with 5 children. Imagine that the presents are taken in the order B, E, C, A and D,
so the first child to choose takes present B and the fifth child takes present D. Imagine that the presents
which the children had hoped to choose were B, E, B, A and B (with the children listed in the same
order). We will refer to this set of presents as a wishlist and will write it without commas for convenience.
So this wishlist is BEBAB. It is easy to see how this wishlist gives rise to the actual presents taken.
1st child wants to choose present B and is successful since no presents have yet been chosen.2nd child wants present E and is also successful.3rd child wants present B but this has already gone. The child takes the next available, which is C.4th child wants present A and is successful.5th child wants present B, which has been taken. The next available present is D (as C has also been taken).There are 5 children and each could hope to choose any of the 5 presents. This means that there are 5^5 = 3125
possible wishlists. It is easy to generate these and to verify that only 8 of them would give rise to the
presents which were taken by the children. In lexicographic order, these are:
BEBAA, BEBAB, BEBAC, BEBAD, BECAA, BECAB, BECAC and BECAD
If we number these from 1 to 8 we can see that BECAB is number 6.
The first line of the problem gives the number N of sets of data.
N lines follow. Each of these has a string followed by a position. The string is the list (in order)
of presents taken by the children. The number of letters (hence presents) is the same as the number of children.
You have to find the wishlist at the given position in the lexicographic order of all wishlists which match the
list of presents taken. For example, when the presents taken are ABCDFE, the 40th wishlist is AABDFE. Give the answers, separated by spaces, as a single string.
Example:
input:
10
ABCDFE 40
EBHCDFGAI 1219
JDCGEBHFIKA 2189
DKGLEFMHNICJAB 26809
LIHDBFCAJKMNGOPE 626490
RKCODEJGHIFAPLMBNQ 10956203
LMNQEKRDOASBCTIPFGHJ 52491336
NGBLAJMOEPIRQHVKCSTUDF 338251306
DSKXEFITJNMLUHOPQRVGWABC 13131481866
QEWXRGZTYKJHILAMFNOPSUBVCD 106068782044
answer (long line wrapped):
AABDFE EBHCCDEAD JDCGEBHDDJA DKGKEELHNECGAA LIHDBFCAHIKJGFME RKCODDJGGICAPEHAGI
LMLQEKRDLAQACTIOCDFF NGBLAJMMEOIRPGVGCNKUBD DSKXEEITJNMIUHJJIMUGNABC QEWWQGZTXKJGIKAGFIIJFUAGAD