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.
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條直線及任何數量的橫線，且橫線必須連著相鄰的直線。配對規則為選取其中一個頂點，然後向下移動，直至遇到橫線。遇到橫線的時候需要跟著橫線行走，然後繼續向下移動，並重覆以上步驟，直至到達另一端。
試參考左側例子。
當圖中完全沒有橫線，明顯地配對結果為 {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此帖以及 預告帖方能參加比賽。