# UVa 10040 - Ouroboros Snake

• Solution
• ## Background

Ouroboros was a mythical snake in Ancient Egypt. It has its tail inside its mouth and continuously devours itself.

## Problem

Ouroboros numbers are binary numbers of 2n bits that have the property of generating the whole set of numbers from 0 to 2n-1 as follows: To produce all of them we place the 2n bits wrapped in a circle so that the last bit goes before the first one. Then we can denote all 2n different strings with n bits starting each time with the next bit in the circle.

For example, for n=2 there are only four Ouroboros numbers. These are 0011, 0110, 1100 and 1001. For 0011, the following diagram and table depicts the process of finding all the bitstrings:

Your program will compute the function o(n,k), where n > 0 and $0 \leq k < 2^n$. This function calculates the k-th number inside the smallest Ouroboros number of size n-bits.

## Input

The input starts with a line containing the number of test cases. For each test case you will be given a line with two integers n (0 < n <22) and k ( 0 <= k < 2^n).

## Output

For every test case your output must evaluate the function o(n,k) and print the result on a line by itself.

# Solution

題目描述：

有一個 2^n 個 bits 的環，而這個環恰好任取連續 n 個會湊滿 [0, 2^n - 1]，現在找一個字典順序最小的環，接著詢問這個環的某一個位置開始的數值。

題目解法：

當詢問 n bits 的結果時，可以把圖建成 2^(n-1) 個節點，每一個節點有兩條邊，邊上分別為 0, 1，也就是說只要繞過所有的邊，相當於產生所有 2^n 個數字。

由於每一個點的 indegree = outdegree 一定存在尤拉迴路，接著在有向圖中找到一條尤拉迴路即可。

至於找字典順序最小環，使用 周源最小表示法 來找，如果可以的話希望能在搜尋時順便找到字典順序最小的。這裡就沒有系不去探究了。

以下是一個最簡單的版本，但這個版本在生成尤拉迴路時會遭遇到 stackoverflow。

由於上述程式在走訪尤拉迴路時，由於深度過深而造成 stackoverflow 因此需要局部改寫成手動的 stack。通常主機只支持 10 萬到 20 萬之間的深度，這題最慘會到 100 萬。

並且將答案預建出來，如果沒有預建表會導致 Time limit，我以為只有少數幾筆，真是大錯特錯了。