Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1447
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. NM 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. 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. Output The output must be a string with one of the possible ouroboros.
Sample Input 3 3 4 2
Sample Output 000111222121102202101201002 1111000010100110
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// euler circuit
// De Bruijn path len = n^m+m-1
// circuit len = n^m
int m,n;
int len;
bool dfs(string& cur,unordered_set < string>& visited){
if(cur.size() == len){
vector<string> revert;
for(int i=1;i < m;i++){
string nxt = cur.substr(cur.size()-m+i) + cur.substr(0,i);
if(!visited.count(nxt)){
visited.insert(nxt);
revert.push_back(nxt);
} else {
for(auto& s : revert) visited.erase(s);
return false;
}
}
cout << cur << endl;
return true;
}
string prev = cur.substr(cur.length()-m+1);
for(int i=0;i<n;i++){
string nxt = prev + (char)('0'+i);
if(!visited.count(nxt)){
visited.insert(nxt);
cur += (char)('0'+i);
if(dfs(cur,visited)) return true;
cur.pop_back();
visited.erase(nxt);
}
}
return false;
}
int main()
{
while(cin >> m){
cin >> n;
len = pow(n,m>;
unordered_set < string> visited;
string cur(m-1,'0');
dfs(cur,visited);
}
} Input
4 2
Output
1111000010100110
Demonstration
UVA Online Judge solution - 10506-The Ouroboros problem - UVA Online Judge solution in C,C++,java