2011年10月8日 星期六

11536 - Smallest Sub-Array

考慮有N個整數元素的序列,其元素為:
X1 = 1
X2 = 2
X3 = 3
Xi = (Xi-1 + Xi-2 + Xi-3) % M + 1         for i = 4 to N

找出兩個整數 a 與 b 使得子序列 (Xa Xa+1 Xa+2 ... Xb-1 Xb) 包含所有 [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

原文出處

沒有留言:

張貼留言