CODEWITHSUNDEEP
algorithm
Ronzii
Ronzii

Reputation: 277

I need help solving a problem on codechef

Statement

Consider a string of length N consisting only of lowercase alphabets a-z. Let s[i] be the character at the i-th position in the string (1-based). The string is a K-string if there are EXACTLY K values of i (1 <= i < N) such that s[i+1]<s[i] (we assume 'a'<'b'<'c'<...<'z'). Given K, find the shortest K-string. If there are multiple solutions, find the lexicographically earliest K-string.

Input

The first line contains the number of test cases T (1<= T <= 100). Each test case contains an integer K (≤ 100). Output

Output

T lines, one for each test case, containing the required string. Use only lower-case letters a-z.

What i cant understand is the case of 27 to 100. I can simply use char array to compute the the problem This isnt the whole algo. I am still trying......

#include<iostream>
using namespace std;
int main()
{
char s[]={'0','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    int k;
    cin>>k;
    for(int i=k;i>=1;i--)
    {
      //cout<<s[i+1]<<">"<<s[i];
      if(s[i+1]>s[i])
       cout<<s[i];

    }
    system("pause");
    return 0;
}

Upvotes: 1

Views: 454

Answers (2)

Lo&#239;c F&#233;vrier
Lo&#239;c F&#233;vrier

Reputation: 7750

Shortest then lexicographically earliest.

So the solutions will be :

  • ba : K = 1, length = 2
  • cba : K = 2, length = 3
  • dbca : : K = 3, length = 4
  • zyx....a : K = 25, length = 26
  • bazyx....a : K = 26, length = 28
  • bcazyx....a : K = 27, length = 29
  • ....

Upvotes: 1

Ssancho
Ssancho

Reputation: 149

For 26, you can do:

a, b, ... z, a, b

But I think the optimal solution is:

a, b, a, b, ... z

In general, I think you need to do a 'small' run first, then all the full runs.

Upvotes: 0

Related Questions