美琴是一位中學生. 她很喜歡硬幣, 硬幣不但可以用來買東西, 可以打人, 還可以玩遊戲. 美琴在無聊之虞發明了一種翻硬幣的單人遊戲. 遊戲的玩法如下:
(1)每個硬幣分正反兩面, 玩家剛開始放置N枚正面朝上的硬幣在某個圓周上的N個等分點(在此, 我們規定第i+1枚硬幣是第i枚硬幣在圓周上順時針方向的相鄰硬幣, 而且第i+N枚硬幣等價於第i枚硬幣).
(2)玩家要將硬幣翻轉, 但不可以移動硬幣, 最後將N枚硬幣翻成指定的目標(例如: 第1個正面, 第2個反面, …, 第N個朝反面, etc).
(3)玩家有一種固定的翻硬幣模式, 這個模式可以用一個整數M和一個長度為M的0-1序列S[0..M-1]描述. 玩家在這個模式下, 可以任選一個硬幣j開始,
對於所有0 <= i <= M-1,
若S[i]=0, 則將第j + i枚硬幣維持不動;
若S[i]=1, 則將第j + i枚硬幣反轉.
舉例而言, 若M=1, 且S = (0), 則任何目標都無法達成, 除非目標是正面全部朝上; 若M=N, 且S = (1, 1, …, 1), 則只有全部(正面/反面)朝上兩種目標能達成.
美琴很好奇自己能不能在某個給定的模式將這N枚硬幣翻成想要的樣子, 她跑來向你求助. 身為紳士的你怎麼能不幫助她呢?
每筆資料的第1行有兩個整數N, M(3 ≤ N ≤ 2,000 , 1 ≤ M ≤ N), N, M如上文所述.
接下來有N行, 第k行有一個數字, 描述目標狀態的第k個硬幣正面或反面朝上(0為正面, 1為反面).
接下來有M行, 第k+1行有一個數字S[k].
本題有多筆測試資料, 當N=M=0時代表結束.
對每筆資料, 若指定的目標能在規定的翻硬幣模式下達成, 輸出YES, 否則輸出NO.
6 3 1 0 1 0 1 0 1 0 1 6 3 1 0 1 1 0 1 1 0 1 3 1 1 1 1 1 0 0
NO YES YES
Migrated from old NTUJ.
劉士瑋 TOI 2011
| No. | Testdata Range | Score |
|---|