安全破解澳大利亞信息奧林匹克2009中級

-3

嗨，最近我正在嘗試從AIO 2009中級的問題。安全破解澳大利亞信息奧林匹克2009中級

問題（改寫）爲：

有正整數的序列，其中的每一個已經通過一個非負常數k（加密通過在序列中添加k以每個值，且k具有沒有邊界，只要下面的a和b的邊界保持），給出一個整數列表a。我們得到的原始未加密列表，B的一小部分，使得2 < = LEN（b）中< = 30和2 < = LEN（a）中< = 100000。給定兩個列表a和b，編寫一個返回原始未加密整數列表的函數（a和b中的所有整數滿足1 < a，b < 1000000）。確信只有一種獨特的解決方案。

，我考慮的一些想法是：

蠻力所有可能的B的組合，直到我們找到一個的一個子集。（雖然（O（n^2）），但我的解決方案的時間複雜度太高，如果某人可以編碼O（n）解決方案，它將起作用）

找出b和a之間的數字之間的差異，然後找到一個匹配的子集。然後我們用它來找出b [0]對應的索引，然後得出密鑰k。（此作品除了有拐角的情況下，我是無法解決）

我想知道如果任何人都可以使用代碼這兩種方法在Python 3.X解決這個。此外，你是否也可以解釋哪種方法更好，更高效，爲什麼？

感謝

來源

2017-08-25 Russell Ng

這對加密意味着什麼？異或？ k和原始整數的界限是什麼？如果可能有多種解決方案，該怎麼辦？ – kfx

@kfx我編輯了這個問題，感謝您指出了這一點！ –

讓我們假設你被賦予的「加密」整數以下列表：

E1 = [200,450,100,75,275,500,600,400,300]

和解密後的子表。類似如下：

L1 = [25,225,450,550,350]

變換L1到一個新的數組，L2，使得每個元件本身和上一個元素之間的差異。這是L2[i] = L1[i] - L1[i-1]。對於L2 [0]，讓它爲零。

L2 = [0,200,225,100,-200]

下降的第一個元素（）

L2 = [200,225,100,-200]

現在，做同樣的正常化將加密列表：

E2 = [250,-350,-25,200,225,100,-200,-100]

現在做歸一化列出了經典的子字符串搜索找到E2在E2開始的匹配索引。

def findStartIndex(needle, haystack): 
    j = 0 
    while len(needle) < len(haystack[j:]) 
     if (needle == haystack[j:j+len(needle)] 
      return j 
     j = j + 1 
    return -1 

index = findStartIndex(L2, E2)

如果上面的搜索返回一個整數值：index（在這種情況下3）：

那麼關鍵k很簡單：E1[index] - L1[0]

在這個例子中，k是50

來源

2017-08-25 16:30:00 selbie

我想我在示例數組中有一個或兩個錯字。當我今晚有更多時間時我會糾正的。 – selbie

已更新和驗證。 – selbie

安全破解澳大利亞信息奧林匹克2009中級

回答

相關問題