d195. 11495 - Bubbles and Buckets
標籤 :
通過比率 : 189人/262人 ( 72% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-04-23 18:00

內容

Andrea, Carlos 和 Marcelo 是好朋友,他們游泳池畔度過他們的週末。 當 Andrea 在做日光浴時,其他兩人在玩 Bubbles。Andrea 是個很聰明的電腦工程師,她實在不明白人為什麼他們花那麼多時間在玩如此簡單的遊戲。

他們用她的電腦產生一個隨機整數 N 及一個由 1, 2, ..., N 的隨機排列所產生的數列。

遊戲隨之開始。兩人輪流各走一步,每次都是由 Marcelo 先開始。

輪到的人要選擇兩個相鄰且順序不對的數字並把它們互換。以數列 1, 5, 3, 4, 2 為例,玩家可以把 5 和 3 或 4 和 2 互換,但是不能把 3 和 4 (順序正確) 或 5 和 2 (不相鄰) 互換。如果玩家決定要換 5 和 3,新的數列會變成 1, 3, 5, 4, 2。

這個數列早晚會被完全排序,沒步可走的玩家就算輸了。Andrea 很不屑地說還不如玩奇偶數還比較快。如果你願意,給你一個排列 P,請你判斷誰會贏這局。

輸入說明

輸入含有好幾組測試資料,每組一行,其中所的整數都以一個空白隔開。每行開始有一個整數  N (2 ≤ N ≤ 105),接下來為 N 個相異整數的排列 P = (X1, X2, ...,XN),1 ≤ Xi ≤ N。

只含一個 0 的一行表示輸入的結束。

輸出說明

對於輸入的每組資料,你的程式要輸出一行,該行含有贏家的名字:  Carlos 或 Marcelo。

範例輸入 #1
5 1 5 3 4 2
5 5 1 3 4 2
5 1 2 3 4 5
6 3 5 2 1 4 6
5 5 4 3 2 1
6 6 5 4 3 2 1
0

範例輸出 #1
Marcelo
Carlos
Carlos
Carlos
Carlos
Marcelo

測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <10M
提示 :
UVa 原題
標籤:
出處:
UVa11495 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
30465 dfd8282@gmai ... (fishhh) d195
逆序數對
585 2022-05-23 11:28