Description

在HappyStorm的衣櫥裡，有著各式各樣的襪子。
身為襪控的她，每天最快樂的事就是把玩她收藏的襪子。
有一天，她發現一件驚人的事情：有些襪子不見了！！！

兩隻同樣的襪子一起不見或許還有可能騙過HappyStorm，
但如果只有一隻不見，身為專業襪控的HappyStorm可是會為此感到難過的。

傷心欲絕的HappyStorm想請你幫忙找出不成對的襪子。
儘管你很不願意，但身為一個善良的工程師，還是幫幫可憐的HappyStorm吧。

Input

輸入的第一行有一個整數 t (0 < t <= 10) 代表以下有多少組測試資料。
每組測試資料的第一行有一個整數 n (0 < n < 1000000)，代表HappyStorm的衣櫥裡總共有幾隻襪子。
接下來的 n 行，每行包含兩個以空白分隔的字串name, size，分別代表襪子的型號以及尺寸(襪子無左右之分)。
其中：
name 為長度固定為3且只由小寫字母(a-z)所組成的字串。
size 由小到大只會出現 {"S", "M", "L", "X", "XL"} 這五種。

註：正常的襪子是沒有X的，但身為一個專業襪控，總是能收集到一些奇行種。

Output

對於每一組測試資料請輸出"Case #"，
以及那些不成對的襪子。
對於那些襪子，
請分行並按照襪子型號的字典序(由小到大)再來是襪子的尺寸(由小到大)輸出。

如果所有襪子都成對請輸出單行 "Socks fine"。

詳情請見Sample input/output



Hint: O(nlgn)會TLE

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

在心跳加速空間裡，有很多個勇者，每個勇者都能夠召喚數量不等的守護騎
士。而這些勇者因為打敗大邪神油膩膩及妖神頌五力而被國王阿拉拉可拉拉
優酪乳三世給予不同的等級，分別為等級1到等級N ，每個等級都會有一個
勇者。

不同的勇者之間會互相的溝通，當等級 i 的勇者要和等級 j 勇者溝通的時
候，若存在一個等級 k 的勇者， 介於 i, j 之間，且這個等級 k 勇者擁有比
等級 i 的勇者或等級 j 的勇者的守護騎士多的時候，這個等級 k 的勇者就會
去阻止他們的溝通。
給定各個等級勇者的守護騎士數量。請問能夠互相溝通的配對 共有幾
組。

選自NPSC2009

Input

輸入檔第一行有一個數字表示測資有幾組。
之後每組測資有 2 行，第一行有一個整數 N 代表勇者的
等級為 1~N，第二行有 N 個數字，第 i 個數字 Ai 代表等級 i 的勇者所擁有的
守護騎士的數量。
1<=N<=10⁶
0<=Ai<=2³¹-1

測資較大請使用scanf instead of cin

Output

每組測資輸出一行表示能夠互相溝通的勇者配對共有幾組。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕這學期開了一門神奇的課程，評分方式完全看個人運氣(噢終於不用寫code了!)。蛋糕準備了一疊N張上面標有整數的紙牌，編號1~N，每個人可以任意挑選兩個數字A和B(A<=B)，第A張牌到第B張牌的總和(包含A和B)就是你的得分。可是蛋糕如果直接把這個成績交給學校，他一定會被解聘QQ所以他想出了一個評分方式:大家排隊依序選好A和B之後，如果你的得分比K個以上(含)在你後面選牌的人大，那你就可以得A+，否則將會被當掉。

可能你是一個運氣很背猜拳從來沒贏過的人，在這種評分方式下有99.99999%的機率會被當;可能你是排在隊伍最後的人，不管得到多高的分數，100%會被當；可能蛋糕非常陰險讓所有人分數都一樣，這樣全班都會被當。

蛋糕很好心的想拯救大家，所以他給你們一個機會。如果你能寫出一個程式快速地告訴他全班有幾個人能夠得到A+，雖然他還是不會讓你過，但他會願意幫你簽二退單。

唉，終究還是得寫code。

Input

有多組測資，每組測資第一列為三個正整數N, Q, K。N代表牌的數量，接下來N個整數代表第1張牌到第N張牌上面的點數。
接著會有Q列，每列有兩個數字A,B，分別代表第1個學生到第Q個學生選的數字。

1<=N<=1000000
1<=Q<=1000000
1<=K<=Q
1<=A<=B<=N
-100<=牌的點數<=100

Output

針對每組測資輸出一個整數，代表可以得到A+的人數。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

「鹿茸是鹿耳裡的毛。」

經過媒體的宣傳之後，鹿茸的價格不斷水漲船高。
價格也飆升到難以置信的地步。

一支鹿的價值衡量是由鹿的耳朵裡有幾根毛來決定的。
由於品質控管好到一毛不差的地步。
如果一支鹿的耳朵裡有k根毛，
另外一個耳朵裡也一定會是剛好k根毛，
那麼那頭鹿的價值將會是2*k^k。

許多農場主人紛紛開始擔心自己所獲得的利益會多到難以計算，於是來找你幫忙。
儘管你很不願意，但身為一個善良的工程師，還是幫幫憂心忡忡的農場主人們吧。

Input

輸入的第一行有一個整數 t (0 < t <= 10) 代表以下有多少組測試資料。
每組測試資料的第一行有一個整數 n (0 < n <= 1000)，代表農場總共有幾頭鹿。
接下來的一行，包含 n 個以空白分隔的正整數 q_i (0 < q_i < 2147483647)，分別代表每頭鹿的品質(一個耳朵裡有幾根毛)。

Output

對於每一組測試資料請輸出"Case #"，
以及農場所能產出的價值和，即所有鹿的價值總和。

由於答案可能很大，所以你只要算出答案除以 100000007 的餘數即可。

詳情請見Sample input/output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

其實YLC是一個魔女，昨天她收到秘密任務，
前往異世界消滅怪物。
在異世界的路途上，YLC會遇到許多怪物，
而怪物必須藉由消耗一顆魔法石產生的魔法來消滅。
但由於YLC的口袋很小，只能攜帶一定顆數的石頭，
所以無法一次攜帶大量魔法石消滅全部的怪物。
好在她的夥伴蛋糕及紅線，
每隔一段時間就會傳送一顆魔法石，
而這時候YLC就可以決定是否要拿走那顆魔法石。
由於每顆魔法石的重量都不一樣，
且YLC的口袋只能容納一些魔法石
所以她的策略如下：
1. 收到蛋糕和紅線傳來魔法石時
    A. 口袋還有空間，直接帶上收到的魔法石
    B. 口袋沒空間時，如果口袋中最重的魔法石比收到的重，
         那麼就把最重的那顆丟掉，換成收到的魔法石
         (由於YLC很懶，所以如果口袋中最重的魔法石和收到的等重，
         那麼她會選擇無視收到的魔法石以省事)
2. 遭遇怪物時
    A. 口袋中還有石頭時，就用掉最重的石頭來消滅怪物。
    B. 沒有石頭時，就逃跑略過這隻怪物。
現在，按照時間順序告訴你YLC遇到的怪物及收到的魔法石順序，
並輸出詳細的過程。

Input

第一行有一個正整數T，代表測資的數目。
每組測資有三行。
第一行有三個正整數B,C,N，分別代表YLC最多可以帶著的魔法石顆數、
一開始YLC攜帶的石頭數量、沿路上發生的事件總數量。
第二行有C個正整數，每個整數代表一開始YLC口袋中石頭的重量。
第三行有N個的整數，按照順序代表遭遇的事件，
如果數字是正的，就代表是蛋糕和紅線傳來的魔法石。
如果數字是0，代表YLC遇到了怪物。

1<=C<=B<=100000
0<=N<=500000
0<=N_i<=100000

Output

對於每組測資，先輸出一行"Case #x:"，x代表第幾組測資。
之後請輸出N行，每一行輸出第N_i個事件發生時，YLC做了甚麼事。
若YLC收到魔法石並且直接拿走時，輸出"Take y"，
若YLC丟棄口袋中的魔法石與收到的魔法石做交換時，輸出"Throw z, take y"，
若YLC選擇不將收到的魔法石帶上，輸出"Ignore y"。
若YLC遇到怪物，而身上有魔法石時，輸出"Use y to defeat monster"，
若YLC遇到怪物，而身上沒有魔法石時，輸出"No stones, YLC flees"
其中y代表收到的魔法石的重量，z代表丟棄的魔法石的重量。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

蛋糕最近非常愛玩2048這個遊戲。
這個遊戲的目標是藉由按下鍵盤上的上下左右鍵，
來移動畫面中4x4棋盤的方塊組合出2048。
現在，他給你4x4棋盤中每個方塊的數字，
請你寫一個模擬器，告訴他按下了某個方向鍵後，
棋盤會變成甚麼樣子。

而移動時，每個方塊中的數字會一直沿著輸入的方向移動，
直到不能再移動為止。(見圖1-1,1-2)

而當兩個相同的數字碰觸時，
那麼他們就會合併並且相加。
(見圖2-1中的64及32經過操作後合併為2-2中的128及64)

而一些特殊狀況的規則說明如下，
1.如果有三個相同數字被擠到同一個邊上時，
則只有最靠邊的兩個數字會合併。(見圖3-1中的16)

2.如果有四個相同的數字被擠到同一個邊上，
那麼他們會分為兩組分別合併。(見圖4-1中的2)

Input

第一行會有一個正整數T，代表測資的數量。
每組測資有5行，前4行中每一行會有4個數字，
用來表示棋盤目前的情況。
數字只會有0,2,4,8,16,32,64,128,256,512,1024這11種。
其中0代表該格子是空的(即沒有數字佔據該格)
第5行則有'v','<','^','>'其中一個符號，表示蛋糕按下了哪一個方向鍵。
(v,<,^,>分別代表下,左,上,右)

Output

對於每一組測資輸出18行。
第一行輸出"Case #x:"，x代表測資數量。
之後請按照sample output的格式輸出數字。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你N個正整數, x[1]~x[N], 你可以做以下操作
操作 : 選出一組(x[i],x[j]) {i != j && x[i]>x[j]}, 然後令x[i] = x[i]-x[j];
目標 : 使最後的總合x[1]+x[2]+…x[N]越小越好!
操作的次數沒有限制!
Sorce : codeforces #228

Input

輸入有多筆測資.
每筆測資第一行為正整數N (1<=N<=1000)
接下來一行則會有N個正整數, 分別代表x[1]…x[N](1<=x[i]<=1000)

Output

每筆測資輸出一行一個數字 : 最小可能的總和.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

給你一張圖以及一面鏡子, 你能輸出鏡中的影像嗎?
鏡子會用*表示, 並且保證鏡子一定是垂直放置的!

Ex1 :
輸入一張圖片以及鏡子 :
2222 *
   2 *
   2 *
2222 *
2    *
2    *
2222 *

輸出相對應的倒影 :

2222 * 2222
   2 * 2
   2 * 2
2222 * 2222
2    *    2
2    *    2
2222 * 2222


Ex2 :
輸入 :
1234 *
     *
5678 *

輸出 :
1234 * 4321
     *
5678 * 8765

Input

輸入有多筆測資, 每筆測資間用換行隔開.
每筆測資的字串長度最多100, 並且不會超過100行.
影像只會包含以下字元 : [a-z,A-Z,0-9,space]
因此*字元只會出現在鏡子上!

Output

輸出時, 測資間也請用換行隔開.
並請不要輸出結尾空白!!!
Ex : (空白用_代替)
輸入 :
_2__*
_2__*

輸出 : (正確)
_2__*__2
_2__*__2

輸出 : (錯誤)
_2__*__2_
_2__*__2_

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

一群螞蟻走在一條長度為 L 公分的繩子上，每隻螞蟻的速度為 1 cm/sec。當一隻螞蟻走到繩子的盡頭時，它馬上掉下繩子（再也爬不起來了）。當兩隻螞蟻在繩子上相遇時，馬上掉頭往另一個方向走去。我們知道每隻螞蟻在繩子上的位置，但不幸的是，我們並不知道每隻螞蟻開始時走的方向。

你的任務是算出最快和最慢可能需要多少時間，所有的螞蟻都掉出繩子外。

Input

輸入的第一列有一個整數，代表以下有多少組測試資料。
每組測試資料以2個整數 L, n 開始，L 代表繩子的長度（單位：cm），n 代表一開始時繩子上有多少隻螞蟻。接下來有 n 個整數代表這些螞蟻一開始在繩子上的位置（從繩子的左端算起），且這些位置並沒有一定順序。所有的這些數都不會超過 10000。

請參考Sample Input。

Output

對每組測試資料輸出一列，包含2個整數代表最快和最慢可能需要多少時間（秒），所有的螞蟻都掉出繩子外。

Sample Input  Download

Sample Output  Download

Tags

Discuss