見縫插針

發布時間: July 10, 2022, 2:56 p.m.   最後更新時間: Sept. 14, 2023, 10:18 p.m.   時間限制: 1000ms   記憶體限制: 128M

陳枇最近生活諸事不順,屋漏偏逢連夜雨,這回又被班導師找上了(幫QQ)。不過,這次並不是他哪裡闖禍了,而是要找他勸說(X)監督(O)他最好的朋友:小剛的戀愛情況。老師希望小剛以課(ㄐㄧㄣˇ )業(ㄧㄢˊ )為(ㄕㄣˋ)重(ㄒㄧㄥˊ ),減少約會的頻率。陳枇雖然表示自己無能為力,但老師仍然要求陳枇想辦法解決,兩個禮拜以後繳交改善報告(陳枇:哭啊)。

陳枇雖然嘴巴上接受了,但也心知肚明小剛這人的約會癮簡直更甚於毒癮,勒戒所都未比有效的成癮者豈有口服之可能?苦惱的陳枇無可奈何,只能來找Noter提出幫助,但Noter站著說話不腰疼,只道清官難斷家務事。過不了多久,報應來了,Noter也被找上了。雖然Noter還想辯解自己是Notry不是Noter不想接這個case,但不知是Noter自己也覺得這個理由很瞎,或者他良(ㄕㄡˋ )心(ㄉㄠˋ )發(ㄨㄟ)現(ㄒㄧㄝˊ )所以還是接受了。

在心不甘情不願地瀏覽過改善報告範本後,Noter突然打通任督二脈決定發揮200%的Notry精神,你可以簡單理解成躺平。不過Noter不能真的躺平,不過可以利用文字遊戲讓帳面數值是零。是的,反正Noter已經仁(ㄎㄞ)至(ㄕˇ )義(ㄅㄞˇ )盡(ㄌㄢˋ )了。

具體要如何實施呢?首先Noter注意到小剛約會時會隨機地選擇兩條最短路徑$A(r=0)$、$B(r=1)$,且這兩路徑從小剛的起點出發恰是兩個相反的方向,因此Noter決定用函數的形式來描述小剛約會的情況,至於原因,你肯定能明白。另一方面,由於小剛是用課間下課時間約會,是以小剛每次的約會時長 $\Delta t$ 必定介於$0$和$10$分鐘之間(廢話)。於是乎Noter定義小剛的約會函數值為約會時長 $\Delta t$ 佔整節下課時間的萬分比例,方向則跟行經之$A$、$B$路徑有關,如果選擇路徑$A$,其值為正;選擇路徑$B$,其值為負,數學式表達為:

$$\Huge{{D}(t) = (-1)^r {t \over T} \times 10000}$$

現在萬事俱備,只欠東風。只要小剛隨機地走$A$、$B$兩路徑,就有機會使小剛約會函數值之和為零,數學式表達為:

$$\Huge{\sum_{k=i}^f {{D_k}(\Delta t)} = 0}$$

而Noter便可見縫插針,宣稱自己勸說有效,使得小剛在$i$~$f$區間沒有約會。不過現在還有個問題:就是陳枇蒐集了很多筆數據,這樣龐大的資料用手算肯定會算到眼睛脫窗(複雜度:$O(n^2)$),所以陳枇想請各位幫他寫一個電腦程式處理這些數據,以便向上面交差。

PS:你會願意幫他對吧,如果不願意的話,你成為下一個Noter的機會是102%,而且你不能宣稱自己叫Notry,因為這老梗有人用過了。

第一行有一個數$N$,代表陳枇蒐集了$N$筆數據($1 \leq N \leq 5 \times 10^5, N \in \mathbb{N}$)。
接下來有$N$個數$A_1, A_2, ... , A_N$,($-10000 \leq A_i \leq 10000, A_i \in \mathbb{N}$),代表小剛第 $i$ 次約會的紀錄。

如果能在數列$\{A\}$中找到一組子序列$\{N\}$使$N$之各項和為零,請輸出「Found a subarray with 0 sum」(不含引號),代表Noter得救了。
如果找不到任何一組各項和為零的子序列請輸出「No Such Sub Array Exists!」(不含引號),代表Noter慘了。喔不對是小剛沒救了。

複製範例
9
4 6 -7 5 -2 1 0 3 1
Found a subarray with 0 sum

本故事全是Noter瞎扯的,大家應該看得出來線上上課已經讓Noter瘋掉了

prefix sum

竹中軟研37th第二次競賽(社內賽)