73 lines
1.2 KiB
C++
73 lines
1.2 KiB
C++
|
#include <cstdio>
|
||
|
|
#include <iostream>
|
||
|
|
#include <cstring>
|
||
|
|
|
||
|
|
|
||
|
|
bool is_impossible(int letters[], int no_chars, int leftoff) {
|
||
|
|
for (int j = 0; j < 26; j++) {
|
||
|
|
if (letters[j] > ((no_chars+1) / 2)) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main(int argc, char const *argv[])
|
||
|
|
{
|
||
|
|
int T;
|
||
|
|
std::cin >> T;
|
||
|
|
for (int i = 0; i < T; ++i)
|
||
|
|
{
|
||
|
|
int letters[26];
|
||
|
|
for(int j = 0; j < 26; j++) {
|
||
|
|
letters[j] = 0;
|
||
|
|
}
|
||
|
|
// inlezen
|
||
|
|
char c = getchar();
|
||
|
|
int no_chars = 0;
|
||
|
|
// count
|
||
|
|
if (c == '\n') c = getchar();
|
||
|
|
while(c != '\n') {
|
||
|
|
letters[c - 'a']++;
|
||
|
|
no_chars++;
|
||
|
|
c = getchar();
|
||
|
|
}
|
||
|
|
|
||
|
|
if (is_impossible(letters, no_chars, -1)) {
|
||
|
|
printf("IMPOSSIBLE\n");
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
char last = -1;
|
||
|
|
while(no_chars > 0) {
|
||
|
|
bool printed = false;
|
||
|
|
for (int j = 0; j < 26; j++) {
|
||
|
|
if (letters[j] > ((no_chars) / 2)) {
|
||
|
|
last = j;
|
||
|
|
letters[j]--;
|
||
|
|
putchar(j+'a');
|
||
|
|
printed = true;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (printed) {
|
||
|
|
no_chars--;
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
for(int j = 0; j < 26; j++) {
|
||
|
|
if (letters[j] && last != j) {
|
||
|
|
last = j;
|
||
|
|
letters[j]--;
|
||
|
|
putchar(j+'a');
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
//printf("no more letters?!\n");
|
||
|
|
//return -1;
|
||
|
|
no_chars--;
|
||
|
|
}
|
||
|
|
|
||
|
|
putchar('\n');
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|