b793. I最後的饗宴
標籤 :
通過比率 : 26人/49人 ( 53% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-02-22 00:07

內容

 

Day 1
(跳過劇情 請找標籤 <主要題敘>)
"你將會進入一個不屬於你的世界,但僅有三天,每天的白天和夜晚,你將接受到一個新的挑戰......"
海牛早上醒來時,發現自己不在自己家裡,而是一個陌生卻又熟悉的環境,他正想搔搔頭搞清楚這是什麼情況時,感覺到的不是自己的雙手,而是....蹄! 他看看鏡中的自己,不知為何他變成Pony了!!
還好他之前有到JKC家學習一下Pony的生態,所以海牛很快地融入這個環境之中。
不久,原本想四處參觀的海牛卻被Bat Pony守衛攔下,對海牛喝道:「Any mature stallion is supposed to join the army during the war!」 不知現在是尛情況的海牛,在守衛喝斥完之後又很不幸地被抓住押往一座城堡。
海牛抵達城堡後,進入了一間類似王座廳的寬敞空間中;奇怪的是,守衛此時卻鬆綁海牛,紛紛離開這裡。昏昏沉沉的海牛懵然抬頭一看,發現坐在王座上的居然是Woona!
「Holy crap...我是穿越二次元了是不...」海牛心理OS道。
此時Woona走向他,向海牛解釋這一切發生的情況:
現在陽焰帝國(Solar Empire)和新月共和國(New Lunar Republic,abbr.=NLR)的戰火正處於水深火熱之中,而新月共和國是類似反抗軍的陣營,工程師等專人士急遽短缺,而Pony懂coding的大多留在帝國軍那邊,於是Woona費了許大力氣使用了"Programmer Summon",好死不死把海牛硬生生抓到這裡;由於Woona提供的薪資福利不錯以及不幫助她海牛也沒辦法回家的狀況下,海牛便欣然接下這個任務。

<主要題敘>

在打點好海牛在這裡的生活所需後,Woona便指派給海牛第一項任務:打點盛宴(原來programmer還兼任打雜)。
由於不久後新月共和國打算做出一次重大突襲,所以她想請各位臣子們參與她所舉辦的盛宴。而為了彰顯她的氣度,她決定當場如果有n位來賓,便請御廚準備n道菜色;而餐桌為圓桌,這些餐點會依照順序由1~n擺放在圓桌上。接受任務的海牛去調查受邀的來賓,發現他們都有以下共通點:

1.為了感謝Woona的好意,所以他們每項餐點都會吃。
2.每位來賓看過菜單總表後,都有一個"優先食用佇列",意思是:來賓都會想先吃自己比較喜歡的菜色,再吃次個喜歡的菜色,這些次序排下來便是這個佇列。
舉例來說:某位來賓最喜歡吃編號3的菜,其次是1、4、2,那他會先拿3號菜,再拿1、4、2,而這為來賓的優先食用佇列便是 : 3 1 4 2 。
3.每位來賓都很有風度,所以只會拿眼前那道菜色,看是不是現在最想吃的菜色再決定要不要拿。

你將這件事報告給Woona後,她便發現了一項問題:
餐桌是圓桌,並且是圓桌是順時針轉動的,現在假設餐桌上有編號 1 2 3 三道菜,轉動逐次轉動圓桌就變為:
(1,2,3) -> (2,3,1) -> (3,1,2) -> (1,2,3)......
而每位來賓都希望快點吃到每樣菜色、而又要遵守自己優先食用佇列,如果不按照一定順序轉圓桌取餐的話,這樣會杯盤狼藉的!
所以Woona想請你想出編號1的菜色最初應該在第幾位來賓面前,在逐次轉動下,讓圓桌轉動次數最少,並且能讓每位來賓都能依照自己的優先食用佇列吃完每道菜色。

以第一筆範例測資來說:
編號1來賓的優先食用佇列為: 1 2 3
編號2來賓的優先食用佇列為: 2 3 1
編號3來賓的優先食用佇列為: 3 1 2
如果一開始編號1的菜放在編號1的來賓面前,則
來賓(1,2,3)->菜(1,2,3) 來賓1拿菜1 來賓2拿菜2 來賓3拿菜3
轉一次後 來賓(1,2,3)->菜(2,3,1) 來賓1拿菜2 來賓2拿菜3 來賓3拿菜1
再轉一次後 來賓(1,2,3)->菜(3,1,2) 來賓1拿菜3 來賓2拿菜1 來賓3拿菜2
只需轉2次圓桌

喔,對了!如果有一樣餐點被吃完了,NLR的服務生會以迅雷不及掩耳的速度將那個被吃光的餐點再端上來替換。所以不用擔心餐點被拿完的情況!

輸入說明

第一行會有一個正整數 T ,表示測試資料的數量。
對於每筆測試資料第一行會有一個整數 N ,表示來賓的數量,接著會有 N 行,每行為一個 1 到 N 的排列,第 K 行表示編號 K 的來賓的優先食用佇列。

(30%分數) 1 <= T <=10 , 1<= N <= 30
(30%分數) 1 <= T <=10 , 1<= N <= 100
(40%分數) 1 <= T <=10 , 1<= N <= 1000

輸出說明

輸出最少的轉動次數讓來賓們都有機會按自己的優先食用佇列吃到每一道菜。

範例輸入 #1
2
3
1 2 3
2 3 1
3 1 2
3
1 2 3
1 2 3
1 2 3
範例輸出 #1
2
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 1.0s , <1K
公開 測資點#2 (17%): 1.0s , <1K
公開 測資點#3 (17%): 1.0s , <1M
公開 測資點#4 (17%): 1.0s , <1M
公開 測資點#5 (17%): 2.0s , <50M
提示 :
標籤:
出處:
[管理者: cthbst (吳宗達) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
36677 r1cky (hehe) b793
題解
94 2023-08-01 22:26