台北市政府為了獎勵資訊能力競賽的選手,在比賽之後的午餐時間中,特別請來著名的「北政」蛋糕公司,烘焙出一種棋盤狀的蛋糕,其尺寸有大有小。但在水平及垂直格線處有凹溝,因此你可以很容易地將蛋糕一刀切成上下或左右兩塊,而吃掉其中一塊。在這次比賽中,你已經花費了很多力氣在撰寫程式,所以你已經很餓了,實在想趕快能吃一塊大一點的蛋糕來止餓。
然而,為了考驗選手的智慧,「北政」蛋糕公司精心設計了一個難題。他們在其中一格蛋糕上面塗滿了辣椒醬,不幸吃到這格蛋糕的人將會辣到一輩子難忘!
考驗時以兩個選手(A 和B)為一組,一開始有一塊很大的n*m 的矩形蛋糕,這兩個選手輪流將蛋糕切成兩塊(A 選手先切及吃),而吃掉其中不含辣椒醬的那一塊。但是到了最後,「吃了塗滿了辣椒醬的那一格蛋糕」的人就輸了這個遊戲。由於你實在是很餓了,所以你極力想要避免輸了這個遊戲,但是一開始就想吃愈大塊的蛋糕愈好。舉例來說,下圖是一塊3*6 的蛋糕,其中標示「」的格子表示該格子塗滿了辣椒醬。如果A 選手選擇走上方「過程一」的路,吃下面兩列(row)共有12 格的蛋糕,接著B 選手就會吃最左邊一欄(column)蛋糕,最後A 選手就會輸了這個遊戲。反過來說,如果A 選手選擇走中間「過程二」的路,吃左邊三欄(column)共有9 格的蛋糕,接著B 選手不管怎麼走,最後A 選手一定可以贏了這個遊戲。因此,此例子一個必勝的走法是垂直地切一刀,切在從左邊算起第3 欄及第4 欄之間,而且其第一次可吃到9 格的蛋糕。
另外一種必勝的走法是A 選手選擇走下方「過程三」的路,吃右邊一欄(column)共有3 格的蛋糕,接著B 選手不管怎麼走,最後A 選手一定可以贏了這個遊戲。因此,此「過程三」也是一個必勝的走法,即垂直地切一刀,切在從左邊算起第5欄及第6 欄之間,而且其第一次可吃到3 格的蛋糕。但是因為你想第一次就吃較多的蛋糕,因此A 選手應選擇「過程二」的走法較好。
如果你是A 選手,第一步你要如何走才能必勝而且第一步你就吃到最多的蛋糕?此題你的任務即是要找出其中一個必勝的走法而且第一步就吃到最多的蛋糕。如果沒有必勝的走法,那麼請輸出"No winning strategy."。
過程一:
過程二:
過程三:
Constraints 矩形的大小不會超過1000×1000。也就是說,1<=n<=1000,1<=m<=1000。
輸入檔可能包含多組測試資料。每筆測試資料佔一列,包含四個以空白隔開的正整數n,m,x,y。
n 為矩形的列數,m 為矩形的欄數,x 為塗滿了辣椒醬的那一格蛋糕的列座標位置,y 為塗滿了辣椒醬的那一格蛋糕的欄座標位置。
(1<=x<=n<=1000,1<=y<=m<=1000)
一律在螢幕上輸出。如果沒有必勝的走法,那麼請輸出"No winning strategy."即可。如果有必勝的走法(可能不只一種),請輸出第一步吃到最多蛋糕的一種必勝的走法即可。也就是只輸出三個資料:切蛋糕的方向d、位置k 及吃到蛋糕的格數,中間以一個空白分開。其中d=”horizontal”,表示水平地切一刀,切在第k 列及第k+1 列之間。另一種狀況d=”vertical”,表示垂直地切一刀,切在第k 欄及第k+1欄之間。
如果有多種可能的答案,那麼請以水平切向優先;若仍有多種可能,請輸出位置最小者。
原TIOJ1123 / 93北市賽(prob 4)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |