11536 - Smallest Sub-Array

考慮有N個整數元素的序列，其元素為：

X₁ = 1

X₂ = 2

X₃ = 3

X_i = (X_i-1 + X_i-2 + X_i-3) % M + 1         for i = 4 to N

找出兩個整數 a 與 b 使得子序列 (X_a X_a+1 X_a+2 ... X_b-1 X_b) 包含所有 [1,K] 的整數。若有多組可能的解請選擇(b-a)值最小的那一組。也就是說請你從原序列中找出最小的子序列使得該子序列包含1~K。

例如N=20, M=12, K=4，可得到序列：

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

包含{1 2 3 4}的最小子序列長度為13，以藍色字型標示如下：

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

Input

輸入資料的第一列有一個整數T(T < 100)表示測試資料的組數，每組資料有三個整數：N(2 < N < 1000001)，M(0 < M < 1001)，K(1 < K < 101) 。

Output

請每組測試資料輸出資料編號與最小子序列的長度，若找不到符合要求的子序列則輸出"sequence nai"。

Sample Input                               Output for Sample Input

2 20 12 4 20 12 8

Case 1: 13 Case 2: sequence nai

---

原文出處