c876. 107北二3.馬步求勝遊戲
標籤 :
通過比率 : 48人/57人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-11-18 15:02

內容

給定一個 10000x10000 的棋盤,兩個玩家玩一個走馬步的遊戲。在一般象棋遊戲中,馬有 8 個方向可以走。但在本題中,這個馬被限制只能往左上方向的 2 個位置走。遊戲規則如下:

  • 一開始輸入 x 及 y 座標,表示「馬」這顆旗子放在 (x, y) 位置。其中 x 是水平座標,y 是垂直座標。棋盤左上角位置是 (1, 1),最右下角位置是 (10000, 10000)。
  • 這兩個玩家輪流走馬步,從 (x, y) 位置可以往左上方向跳到以下 2 個位置其中之一:(x-2, y-1)、(x-1, y-2),但不能跳出棋盤外面。
  • 如果某個玩家沒路可走,則輸了這一盤棋。

下圖是一個例子。一開始「馬」這顆棋子放在 (x, y) = (8, 6) 位置。先手的玩家有 (6, 5)、(7, 4) 這 2 個位置可以走。先手的玩家如果走到下方路徑的 (6, 5),則後手的玩家可以走到 (4, 4),接下來先手的玩家不管走到 (3, 2) 或 (2, 3),都會讓後手的玩家走到 (1, 1),而使得先手的玩家無路可走,因此先手方就輸了這個遊戲,而雙方總共走了 4 步。

反之,若先手的玩家一開始走到上方路徑的 (7, 4),則後手的玩家不管走到 (5, 3) 或 (6, 2),都會讓先手的玩家走到 (4, 1),而使得後手的玩家無路可走,因此先手方就贏了這個遊戲,而雙方總共走了 3 步。

雙方最佳攻防策略可定義如下:如果某一方必勝的話,則他會想用越少的步數獲勝越好。反之,另一方即使必輸,也仍會想盡力拖延越多步越好。
本題目想請你求出在雙方最佳攻防策略之下,雙方會下的總步數。以此例而言,先手方在 3 步之內必可取勝。因此在雙方最佳攻防策略之下,總步數為 3。

現在要請你寫一個程式來幫忙求出先手方是必勝或必敗,以及雙方會走的總步數。

 

 

輸入說明

測試資料只有一行,有兩個數字 x 及 y,
表示一開始「馬」這顆旗子放在 (x, y)位置,其中 1 ≤ x ≤ 10000,1 ≤ y ≤ 10000。
這兩個數字之間用空格(white space)隔開。

輸出說明

輸出資料只有一行,含有一個英文字及一個表示雙方會走的總步數的整數。
這一個英文字若為"Win",表示先手方必勝。
這一個英文字若為"Lose",則表示先手方必敗。

範例輸入 #1
範例輸入一:
6 8

範例輸入二:
4 7
範例輸出 #1
範例輸出一:
Win 3

範例輸出二:
Lose 2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (4%): 1.0s , <1K
公開 測資點#1 (4%): 1.0s , <1K
公開 測資點#2 (4%): 1.0s , <1K
公開 測資點#3 (4%): 1.0s , <1K
公開 測資點#4 (4%): 1.0s , <1K
公開 測資點#5 (4%): 1.0s , <1K
公開 測資點#6 (4%): 1.0s , <1K
公開 測資點#7 (4%): 1.0s , <1K
公開 測資點#8 (4%): 1.0s , <1K
公開 測資點#9 (4%): 1.0s , <1K
公開 測資點#10 (4%): 1.0s , <1K
公開 測資點#11 (4%): 1.0s , <1K
公開 測資點#12 (4%): 1.0s , <1K
公開 測資點#13 (4%): 1.0s , <1K
公開 測資點#14 (4%): 1.0s , <1K
公開 測資點#15 (4%): 1.0s , <1K
公開 測資點#16 (4%): 1.0s , <1K
公開 測資點#17 (4%): 1.0s , <1K
公開 測資點#18 (4%): 1.0s , <1K
公開 測資點#19 (4%): 1.0s , <1K
公開 測資點#20 (4%): 1.0s , <1K
公開 測資點#21 (4%): 1.0s , <1K
公開 測資點#22 (4%): 1.0s , <1K
公開 測資點#23 (4%): 1.0s , <1K
公開 測資點#24 (4%): 1.0s , <1K
提示 :
標籤:
出處:
107北二區桃竹苗資訊學科能力複賽 [管理者: mushroom.cs9 ... (mushroom) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
16084 k034006 (Sine Wu) c876
想法
1061 2018-11-18 14:29