TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

50.0% (7/14)

Tags

Description

每年的四月四日是兒童節,幾乎所有的社福機構都會在兒童節前後幫小朋友們辦類似露營烤肉的活動,而且還會發禮物。當然今年也不例外。貼心的梯歐埃旅行社提供了十四天兩次大烤的露營活動,當然,在烤完的最後一天還會在營區大合照留作紀念。

不過這些並不是重點,眾人們期待的其實是點心、鬥塔和更多更多的點心、鬥塔、桌球和逃避現實沉浸在歡樂氣氛的一切。

每一年梯歐埃旅行社都會為大家準備一些小點心,例如:"Fundamental Data Structure in C++"、"Introduction to Algorithm"或者是旅社特別邀請各地名廚所帶來的有趣小品。不過因為經費拮据的關係,今年梯歐埃旅行社只能夠提供三種小點心,而且每人最後只能吃到一種。這三種點心分別是『墨哥哥脆餅』、『克西西領帶糖』以及『埃及及金字塔慕斯,內含木乃伊』,為了方便起見我們以a,b,c來表示它們。

這可苦了帶領營隊的輔導員們了,每個人都有心中想要的點心,但是如果一起把點心發給大家,可能有些人會因為『為什麼我拿得和別人一樣』而覺得很沒有鑑別度。因此輔導員決定叫大家站成一排,每次發給相鄰的兩個人點心,並且遵守『每次發給兩個人的點心是不同的』。可是這樣引發了另一個問題:有些人反而拿不到自己想要的點心,所以輔導長想出了一套給糖的規則:

  1. 每次把兩種不同的點心發給相鄰並且手上都沒有點心的人。

  2. 每次挑兩個相鄰的人,並且他們其中一個人已經拿了點心X,另一個人沒有點心。這個時候輔導員可以把原本手上有點心X的人手上的點心拿走,而且給這兩個人除了點心X以外的另外兩種點心。

給你站成一排的眾人們所希望得到的點心,請問根據這套規則是否有可能達成大家的願望呢?

Input Format

第一列有一個正整數 T (1<=T<=10),代表梯歐埃旅行社所舉辦的露營次數。

第二列開始,每兩列代表一個露營資料。會有一個正整數 N (1<=N<=100,000) 代表參加露營的人數。
接下來會有一個長度為 N 的字串,由小寫字母 a,b,c組成,代表排成一列的眾人們心中所想要得到的點心代碼。

Output Format

對於每一次的露營資料,如果輔導員們可以滿足眾人們的需求,請輸出"YES",否則請輸出"NO"(均不含引號)。

Sample Input 1

2
4
aaab
6
aaabbb

Sample Output 1

YES
NO

Hints

第一筆範例輸入當中,假設我們以小寫字母o代表手上沒有點心的人,那麼他們取得點心的順序將會是:

oooo => aboo => aaco => aaab

在VCOJ的評分測試中,
至少佔總分30%以上的測試資料滿足 n<=100
至少佔總分50%以上的測試資料滿足 n<=1000

Problem Source

原TIOJ1520 / 2009宵夜盃練習賽I。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11