Question Name:Grovyle String

#include<stdio.h>
#include<string.h>
#define MAX_LEN 1002
 
int partition(char string[], int low, int high) {
char pivot = string[high];
int i = low - 1;
int j;
for (j = low; j <= high - 1; j++) {
if (string[j] >= pivot) {
i++;
char temp = string[j];
string[j] = string[i];
string[i] = temp;
}
}
char temp = string[i + 1];
string[i + 1] = string[high];
string[high] = temp;
return (i + 1);
}
void quickSort(char string[], int low, int high) {
if (low < high) {
int point = partition(string, low, high);
quickSort(string, low, point - 1);
quickSort(string, point + 1, high);
}
}
int main() {
int testCase;
scanf("%d", &testCase);
int t;
for (t = 0; t < testCase; t++) {
char string[MAX_LEN];
scanf("%s", string);
quickSort(string, 0, strlen(string) - 1);
//Printing Result...
char result[strlen(string)];
int mid = strlen(string) / 2;
int low = mid - 1;
int high = mid + 1;
int pointer = 0;
result[mid] = string[pointer++];
while (high < strlen(string) && low >= 0) {
result[high++] = string[pointer++];
result[low--] = string[pointer++];
}
int i;
for (i = 0; i < strlen(string); i++) {
printf("%c", result[i]);
}
printf("\n");
}
return 0;
}

Problem Description

Trico is trying to impress a girl. But the girl is not showing any sign of interest to him. So his best friend suggested him to gift one Grovyle string to her. Grovlye string is a odd length string consisting of only lowercase alphabets arranged in such a way that a number X associated with it is smallest as possible.

X is calculated as : First take absolute distance of each character’s position from the center of the string i.e., (string length/2) and then multiply the distance with its ASCII value. Similarly find all the values and add them.

Example : Given string : aaa

Here only one unique permutation is possible : aaa

distances are : for first a, d1 = 1, second a, d2 =0, third a, d3 = 1;

so X = 1 X 97 + 0 X 97 + 1 X 97 = 194;

So given a string of odd length consisting of only lowercase alphabets, find one permutation of the given string such that X is smallest as possible. And if there are many such strings then print the lexicographically smallest one.

Input: First line contains T, the number of test cases that follow. Next T lines, each contains one odd length string consisting of only lowercase alphabets.

Output: For each test case, print the desired result in separate lines.

Constraints:
1 <= T <= 1000
0 <= String Length <= 1001

  • Test Case 1

    Input (stdin)

    2
    aaa
    abc
    

    Expected Output

    aaa
    acb
  • Test Case 2

    Input (stdin)

    3
    aaa
    abc
    ccb
    

    Expected Output

    aaa
    acb
    bcc

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro