主題

ZeroJudge - f479: 質數成長 解題心得

Not In My Back Yard | 2020-12-14 00:00:04 | 巴幣 0 | 人氣 57

題目連結:


題目大意:
有一個植物有很多節,每一節可能會用「A」、「B」或是「C」表示。而第一天時,節的數目為 1 ,而每從第 n 天到第 n + 1 天時,該植物會新長出一些節,其數目恰好為第 n 個質數。而且那些新長出的節會以 ABCABC…… 交錯的規律生出新的字元。

也就是說,
第一天植物的節之內容為 A
第二天植物的節之內容為 AAB
第三天植物的節之內容為 AABABC
第四天植物的節之內容為 AABABCABCAB
第五天植物的節之內容為 AABABCABCABABCABCA
……
以此類推。

輸入有多列,每列給定兩正整數 N 、 K(1 ≦ N ≦ 10000,1 ≦ K ≦ 1000000000),代表現在是第 N 天,試問植物從左到右數來的第 K 節之字元為何?若 K 值超過第 N 天植物的節數從輸出「#」。



範例輸入:
1 1
4 3
6 17
2 5


範例輸出:
A
B
C
#


解題思維:
先找出前 9999 個質數(可以利用埃式篩法,如這題),然後求出第 1 天到第 10000 天的每一天植物之節數。

然後對於每個給定的 K 值判斷植物是在哪一天長到至少 K 節長(因為剛剛有依序建表,因此這部分可以使用二分搜尋法(Binary Search)快速地找到)。

現在假設是第 i 天(注意 i 不得超過 N,超過的話就輸出「#」),則代表植物在第 i 天到來時新長出了等同「第 i 個質數」之值的節數。因為節上的字元是每 3 個一循環,所以直接求
(第 i 個質數 - 1) % 3
其中「%」代表取餘之操作。

當上式的結果為 0 時代表循環才剛開始,所以代表著 A 、結果為 1 時代表著 B ,結果為 2 時其代表 C 。而此即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作