Welcome to the Mathematics × Programming Competition #3

For Chinese version please scroll to the bottom. 中文版請見文末。

----

Question

**Ghost Leg** (aka Amidakuji) is a tiny game which is used to create random pairings between two arrays. This is commonly used in lucky draws. A ghost leg consists of vertical lines and horizontal lines. If there are *N* elements in an array, there would be *N* vertical lines and any number of horizontal lines. Horizontal lines should be touching two adjacent vertical lines. The rule of matching is by picking a vertical line at the top, and go downwards until you hit a horizontal line. Whenever you hit a horizontal line, travel along that horizontal line. Then continue to go downwards and repeat this process until you reach the other end.

https://steemitimages.com/DQmZ66uFYP1nvMHkjX91YbmrPaHqchhcbupPFyo2qZ5N6Tr/Untitled.png

Consider this example on the left.

Obviously when there are no horizontal lines at all, the matched pairs would be {A,1}, {B,2} and {C,3}.

With the horizontal lines added, the matched pairs become {A,3}, {B,2} and {C,1}.

Make sure you understand this example before proceeding to the main question :)

Here comes the question. Consider the case *N* = 10. Given that when there are no horizontal lines, the matching pairs are {A,1}, {B,2}, {C,3}, {D,4}, {E,5}, {F,6}, {G,7}, {H,8}, {I,9}, {J,10}. What is the minimum number of horizontal lines to be added such that the final outcome would be {A,7}, {B,4}, {C,3}, {D,9}, {E,2}, {F,8}, {G,1}, {H,6}, {I,10}, {J,5}? ---

Answer submission

Please submit your answer through this link. ---

Rules

- This competition will last for 24 hours. After that no more submission would be accepted. - Participants who submit the answer as a comment below this post will be **disqualified**. - Participants can submit for unlimited number of times, however only the latest answer will be considered. - You have to upvote this post AND the announcement post in order to be eligible for the competition. ---

Prizes

- The final SBD payout of the announcement post would be the prize pool. - The first and second participant who gave the correct numerical answer will get 30% and 20% of the prize pool respectively. 5 other participants who provided the correct answer will be randomly drawn regardless of their submission time and each of them will get 10% of the prize pool. - Those who resteemed this post or the announcement post will have 400% higher chance to win in the lucky draw! - If not all prizes are given out, they will be accumulated for the next competition. - @kenchung reserve all the rights to disqualify any suspected cheating players and decide the distribution of prize among the winner(s). ---- ----

歡迎參加數學 × 程式編寫比賽 (第三回)

---

問題

**畫鬼腳** 是一個用以將兩個序列配對的小遊戲。畫鬼腳被經常應用在抽獎之中。鬼腳圖由直線及橫線組成。若一序列有*N*個項目，該鬼腳圖則共有*N*條直線及任何數量的橫線，且橫線必須連著相鄰的直線。配對規則為選取其中一個頂點，然後向下移動，直至遇到橫線。遇到橫線的時候需要跟著橫線行走，然後繼續向下移動，並重覆以上步驟，直至到達另一端。

https://steemitimages.com/DQmZ66uFYP1nvMHkjX91YbmrPaHqchhcbupPFyo2qZ5N6Tr/Untitled.png

試參考左側例子。

當圖中完全沒有橫線，明顯地配對結果為 {A,1}、{B,2}及{C,3}。

加上橫線後，配對結果便變成 {A,3}、{B,2}及{C,1}。

繼續閱讀問題前請確保你已完全明白這個例子 :)

現在終於來到問題部分了。考慮*N* = 10。已知當鬼腳圖中完全沒有橫線，配對結果為 {A,1}, {B,2}, {C,3}, {D,4}, {E,5}, {F,6}, {G,7}, {H,8}, {I,9}, {J,10}。求最少需要加上的橫線數目使得配對結果為 {A,7}, {B,4}, {C,3}, {D,9}, {E,2}, {F,8}, {G,1}, {H,6}, {I,10}, {J,5}。 ---

答案提交

請經此連結提交答案。 ---

規則

- 此比賽將進行24小時，其後將不會再接受新答案。 - 嚴禁在回覆公開答案，否則將被取消資格。 - 參加者可以重覆提交答案，但比賽終結時只會考慮最後提交的答案。 - 你必須upvote此帖以及預告帖方能參加比賽。 ---

獎品

- 預告帖所獲的SBD獎勵將會用作是次比賽的獎池。 - 第一及第二名最快給出正確數字答案的參賽者將分別獲得獎池的30％及20％。其他提交了正確數字答案的參與者之中將隨機抽出5名，他們每人可獲10％的獎池。 - Resteem此帖文或預告帖者將有額外400％的得獎機會！ - 若有獎金未被發放，將累積至下一次比賽的獎池。本人保留一切最終權利，包括但不限於取消任何疑似作弊者的資格並決定獲獎者的獎勵分配。

schneidor