Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Mhammad1's blog

New Math Problem?
By Mhammad1, history, 9 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, you also had the solution in your last blog. Therefore, this blog makes no sense.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't understand your idea, could you explain more?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He meant that you can represent string aabc as number in base 3:

      aabc ~ (0012)3

      After that your problem is just some arithmetics in base 3

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understand your idea, but suppose we have something like this:

        aa 5

        What is the number that represents the combination (aa) in base _3 and what is the representation of 5 in the base _3?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          aa in base _3 is 1 * 31 + 1 * 30 = 4

          5 = 1 * 31 + 2 * 30, so it is ab

          The 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).

          → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 .

→ Reply