[UVA] 1209 - Wordfish
You have been tasked to infiltrate a tight-lipped society for fun and profit: the ACM ICPC regional judges. Through the PC2 ``submission" software, you know that classified information is accessible through the log-ins of the judges tasked to a particular ``regional site". However, you are not certain that any particular judge has access to all the relevant information, so several log-ins will be required. You have been handed down a list of usernames, and the passwords used can be derived from these usernames, as follows:
Input
The input will only have capital letters (denoting the usernames) and carriage returns. Each line (thus each username) will not be longer than twenty characters, and there will not be more than 12 ``judges" whose log-ins you will need to infiltrate. Strangely, no username uses any letter more than once.
Output
For each username, you must produce a line containing the password which that username uses. The password for a given username is determined from the twenty-one lexicographically consecutive permutations of the username, the eleventh (middle) of which is the username itself. For example, if the username is WORDFISH, the lexicographic permutations of WORDFISH contain, in order:
..., WOISHRFD, WOISRDFH, WOISRDHF, WOISRFDH, WOISRFHD, WOISRHDF,
WOISRHFD, WORDFHIS, WORDFHSI, WORDFIHS, WORDFISH, WORDFSHI, WORDFSIH,
WORDHFIS, WORDHFSI, WORDHIFS, WORDHISF, WORDHSFI, WORDHSIF, WORDIFHS,
WORDIFSH, ...
The password is then the permutation among the twenty-one
lexicographically consecutive permutations of the username which has the
largest minimum absolute distance between consecutive letters (and the
first amongst the lexicographically ordered, if several permutations
have the largest minimum absolute distance), followed by that minimum
absolute distance. For the username WORDFISH, the password is WORDHSFI31 .
1 Disclaimer:
The above story is completely fictional, and in no way represents any
fact, regarding ACM regional judges, their passwords or world
domination.
Sample Input
WORDFISH
Sample Output
WORDHSFI3
翻譯已經放上不幸狗
http://unfortunatedog.blogspot.tw/2013/07/1209-wordfish.html
這裡提供一個不用內建找前後的字典順序的寫法。
接著就是模擬找一個字典順序最小的差。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s[128], cnt[128], pwd[128], path[128];
int pcnt, first, ret, n;
void next(int nd) {
if(pcnt == 10) return;
int i;
if(nd == n) {
if(first == 0) {
first = 1;
return;
}
pcnt++;
path[nd] = '\0';
int mn = 0xffffff;
for(i = 1; i < n; i++)
mn = min(mn, abs(path[i]-path[i-1]));
if(mn > ret) {
strcpy(pwd, path);
ret = mn;
}
return;
}
for(i = 'A'; i <= 'Z'; i++) {
if(first == 0)
i = s[nd];
if(cnt[i]) {
cnt[i]--;
path[nd] = i;
next(nd+1);
cnt[i]++;
}
}
}
void prev(int nd) {
if(pcnt == 10) return;
int i;
if(nd == n) {
if(first == 0) {
first = 1;
return;
}
pcnt++;
path[nd] = '\0';
int mn = 0xffffff;
for(i = 1; i < n; i++)
mn = min(mn, abs(path[i]-path[i-1]));
if(mn >= ret) {
strcpy(pwd, path);
ret = mn;
}
return;
}
for(i = 'Z'; i >= 'A'; i--) {
if(first == 0)
i = s[nd];
if(cnt[i]) {
cnt[i]--;
path[nd] = i;
prev(nd+1);
cnt[i]++;
}
}
}
int main() {
int i;
while(scanf("%s", s) == 1) {
memset(cnt, 0, sizeof(cnt));
n = strlen(s);
for(i = 0; s[i]; i++)
cnt[s[i]]++;
ret = 0xffffff;
for(i = 1; i < n; i++)
ret = min(ret, abs(s[i]-s[i-1]));
strcpy(pwd, s);
first = 0, pcnt = 0;
next(0);
first = 0, pcnt = 0;
prev(0);
printf("%s%d\n", pwd, ret);
}
return 0;
}