By Mhammad1, history, 8 years ago,

Given the letters a, b and c , you're only allowed to use these letters.

First combinations that can be made from these letters are: (a) , (b) , (c) , (aa) , (ab) , (ac) , (ba) ....

What is the nth combination that is after the combination x ?

If two combinations have different length, the combination with smallest length comes first, and if they have the same length ** the smallest in alphabetical order comes first**.

Input:

x and n where (|x| <= 1000) and (n <= 10^9)

Examples:

a 2: means given the combination (a) what is the combination that is (2) steps after the combination (a)? Answer is (c)

aa 3: means given the combination (aa) what is the combination that is (3) steps after the combination (aa)? Answer is (ba)

Input:

a 2
b 3
c 1


Output:

c
ab
aa


I had posted this blog before, but I deleted it accidentally, sorry for this.

• +11

 » 8 years ago, # |   0 Well, you also had the solution in your last blog. Therefore, this blog makes no sense.
•  » » 8 years ago, # ^ |   0 No it wasn't the correct one , here the length is |x| <= 1000 so 3^1000 will not work
•  » » » 8 years ago, # ^ |   0 What is the problem with 31000 ?
•  » » » » 8 years ago, # ^ |   0 -_-
 » 8 years ago, # | ← Rev. 2 →   +1 You can review your input string as a decimal number. So, answer will be your string as number + input number. Base is 3, not 10.
•  » » 8 years ago, # ^ |   0 Can't understand your idea, could you explain more?
•  » » » 8 years ago, # ^ |   0 He meant that you can represent string aabc as number in base 3:aabc ~ (0012)3After that your problem is just some arithmetics in base 3
•  » » » 8 years ago, # ^ |   +4 It's some sort of natural numeric system yes, but not quite. imagine you are writing numbers in base 3, but your digits aren't 0, 1, 2 but 1, 2, 3 (you can represent all positive integers this way, uniquely). Lets call this base _3. If you can transform any number from base 10 to base _3 (it's easy in this case with n ≤ 109), and you can add up two numbers in base _3 (ad-hoc code, a simple for cycle with rules :) ) then you can solve your problem...
•  » » » » 8 years ago, # ^ |   0 I understand your idea, but suppose we have something like this: aa 5What is the number that represents the combination (aa) in base _3 and what is the representation of 5 in the base _3?
•  » » » » » 8 years ago, # ^ |   +4 aa in base _3 is 1 * 31 + 1 * 30 = 45 = 1 * 31 + 2 * 30, so it is abThe tricky example is 6:6 = 2 * 31 + 0 * 30, but we cant represent that (cos we have no zero digit, that's why I said is not quite a numeric system), instead we use 6 = 1 * 31 + 3 * 30 (that is ac).
 » 8 years ago, # |   +1 The answer to the problem as follow (this solution works even for |x| <= 10^6 and n <= 10^18):if |x| < 1001 then add (char('a' - 1)) to the beginning of x until we get |x| == 1001 .char ('a' - 1) means the character that is before the letter 'a' .Now we will use simple math:Suppose the index of the last letter of x is j ( j = 1000 ) ; Moving x[j] forward by one will cost (1) . Moving x[j-1] forward by one will cost (3) .so moving any letter x[i] forward one step will cost 3^(j-i). So the problem now is easy: for(i=1000; i>=0; i--) { while (n > 0 && x[i] != 'c') { if ( 1000-i <= 20 && n >= power(3, 1000-i)) { x[i]++; n-= power(3, 1000-1); } else { //break the two loops we can't go further } } if (x[i] == 'c') x[i-1]++; } i++; while (i <= 1000) { x[i] = 'a'; while (n > 0) { if (1000-i <= 20 && n >= power(3, 1000-i)) { x[i]++; n-=power(3, 1000-1); } else { break; } } i++; } //print x without leading ('a'-1) characters The reason behind (1000-i) <= 20 because (10^9 <= 3^20)Simple modification on the code above you can solve the problem for (|x| <= 10^6) Please notify me if you see something wrong or I've missed something .