c619: 胖胖電腦病毒
標籤 :
通過比率 : 100% (2 人 / 2 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-09-07 06:35

內容

有種新型的電腦病毒在A市傳播開來了!

這種病毒會迅速複製並佔據硬碟和記憶體空間,更糟糕的是,檔案名稱會全部變成「我胖胖」之類的字樣。

擅長資安技術的小W發現,只要找出病毒產生的序列中所有第 $\color{black}{10k - 9}$ 小的數字,病毒便會中止活動。

現在小W已經得知病毒產生的序列 $\color{black}{a}$ 可以用以下方式產生,且數字不會重複,

uint32_t a[1..N];
for (int i = 2 to N) {
	a[i] = a[i - 1];
	a[i] ^= a[i] << 13;
	a[i] ^= a[i] >> 17;
	a[i] ^= a[i] << 5;
}

然而小W電腦所剩的記憶體已經不足以存下 $\color{black}{N}$ 個數字,你能幫他想出好的法子嗎?

聰明的你應該知道,使用 <bits/stdc++.h> 或 <iostream> 都會使空間超過限制,更一般的說,在胖胖病毒的影響下,你得盡量減少不必要的標頭檔引入。

輸入說明

只有兩個正整數 $\color{black}{N}$ 及 $\color{black}{a_1}$,

其中 $\color{black}{1 \le N \le 10000001 \space 且 \space N \equiv 1\pmod{10}}$ ,

$\color{black}{a_1 為有效的 32 位元無號整數}$。

輸出說明

總共 $\color{black}{\frac{N+9}{10}}$ 行輸出,

第 $\color{black}{k}$ 行的輸出為序列中第 $\color{black}{10k - 9}$ 小的數字。

範例輸入
11 1
範例輸出
1
2916098932
測資資訊:
記憶體限制: 16 MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1K
公開 測資點#2 (14%): 1.0s , <1K
公開 測資點#3 (14%): 2.0s , <1K
公開 測資點#4 (14%): 2.0s , <1K
公開 測資點#5 (15%): 7.0s , <1K
公開 測資點#6 (15%): 7.0s , <1K
提示 :

範例測資中 a = {1, 270369, 67634689, 2647435461, 307599695, 2398689233, 745495504, 632435482, 435756210, 2005365029, 2916098932},最小的是1,第11小的是 2916098932。

#00: N = 5001
#01: N = 1000001
#02: N = 2000001
#03: N = 3000001
#04: N = 5000001
#05: N = 10000001
#06: N = 10000001

標籤:
出處:
[編輯:
icube (不會寫程式)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」