[UVA][搜索] 10506 - The Ouroboros problem
Problem GOuroboros |
This symbol appears principally among the Gnostics and is depicted as a dragon, snake or serpent biting its own tail. In the broadest sense, it is symbolic of time and the continuity of life. Similarly, we can make a "digital ouroboros" in the shape of a ring with a property: if you take M adjacent digits, they form a different permutation of M digits, without an established order, but including every legal permutation. The number is represented in a given base N.
The minimum value for N and M is 1, and the maximum value for both of them is 10. N^M should be less than 65536.
For example:
With M=2 and N=3, a possible solution is: 001122102 from which you can obtain (00, 01, 11, 12, 22, 21, 10, 02, 20) by taking the first two digits, the second and the third, and so on. The last number is built by linking the last and first digits of the string.
The Input
The input consists on a list of pairs of numbers (M, N), where M is the amount of digits we are going to deal with, and N the base of the numbers.
The Output
The output must be a string with one of the possible ouroboros.
Sample input
3 3
4 2
Sample output
000111222121102202101201002
1111000010100110
生成一個字串是 N 進制，看成首尾相接的環狀，而每 M 個相鄰的位數當作一個整數(N進制)，然後會生成所有可能 0 - (N^M-1)，因此總共會有 N^M 位。
任何一組解都可以。
題目解法：
依序窮舉，並且把當前數字當作最後一位，向前看 M 個數字計算出一個整數，如果重覆立刻退回，反之繼續搜索下一位。然而由於是環狀，最後再檢查之前的 M-1 個數字。
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int m, n, nm;
int mark[65536] = {};
int s[65536] = {}, found;
void dfs(int idx) {
int i, j, tmp;
if(found == 1) return;
if(idx == nm) {
queue<int> Q;
for(i = 0; i < m-1; i++) {
tmp = 0;
for(j = m-1; j >= 0; j--)
tmp = tmp*n + s[(i-j+nm)%nm];
if(mark[tmp]) {
while(!Q.empty()) {
i = Q.front(), Q.pop();
mark[i] = 0;
}
return;
}
mark[tmp] = 1;
Q.push(tmp);
}
for(i = 0; i < nm; i++)
printf("%d", s[i]);
puts("");
found = 1;
return;
}
for(i = 0; i < n; i++) {
tmp = 0;
s[idx] = i;
for(j = m-1; j >= 0; j--)
tmp = tmp*n + s[idx-j];
if(mark[tmp] == 1) continue;
mark[tmp] = 1;
//printf("%d %d %d\n", tmp, idx, s[idx]);
dfs(idx+1);
mark[tmp] = 0;
}
}
int main() {
int i, j, k;
while(scanf("%d %d", &m, &n) == 2) {
found = 0;
memset(mark, 0, sizeof(mark));
memset(s, 0, sizeof(s));
mark[0] = 1;
for(i = 0, nm = 1; i < m; i++)
nm *= n;
dfs(m);//000...0
}
return 0;
}