[中譯] PuzzleUp 2009 (12) Ascending Letters

看板puzzle作者 (渴望一份好工作)時間16年前 (2009/10/07 19:28), 編輯推噓18(18019)
留言37則, 9人參與, 最新討論串1/1
首頁:http://www.puzzleup.com/2009/?home 時限:2009/10/08(四)19:00~10/14(二)18:59 答案可上傳次,但每改1次扣20(基本分為100分) 在比賽期間內可隨時回答,但只有在時限內回答者有額外加分 ◆Ascending Letters 將 a~z 26個英文字母的次序打亂,重新排列出一條字串。然後再由前往後或由後往前, 從其中一個字母開始,挑出接下來字母次序遞升者,形成另一個新字串。就這樣反覆嘗試 ,挑出其中最長的字串。 請問這條次序遞升且最長的新字串,最小的長度是多少? 以下舉兩個7個字母(A、B、C、D、E、F、G)的例子: 若重新排列過後的字串為:BGEDFCA 那麼其中次序遞升字串,最長者為 GEDCA(方向是由後往前找,從字母A開始) BGEDFCA ←方向 若重新排列過後的字串為:DBCAGEF 那麼其中次序遞升字串,最長者為 BCEF(方向是由前往後找,從字母B開始) 方向→ DBCAGEF -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.247.146 ※ 編輯: puzzlez 來自: 123.194.247.146 (10/07 19:37)

10/07 19:41, , 1F
這次的題目真是麻煩=.="
10/07 19:41, 1F

10/07 22:51, , 2F
這竟然是 Longest Increasing Subsequence...@_@|||||
10/07 22:51, 2F

10/07 23:34, , 3F
太好了 樓上偷偷告訴我答案...我懶得算了-.-"
10/07 23:34, 3F

10/07 23:46, , 4F
帕索好自私喲!o(〒﹏〒)o
10/07 23:46, 4F

10/08 01:58, , 5F
啊, 我只是把這個題目重講一遍而已 XD
10/08 01:58, 5F

10/08 01:58, , 6F
帕索大果然厲害, 這樣就可以悟出答案 XDDDD
10/08 01:58, 6F

10/08 04:49, , 7F
我對這題的解讀是:讓你任意排列26字母,如何使得最長遞升
10/08 04:49, 7F

10/08 04:49, , 8F
字串最小?
10/08 04:49, 8F

10/08 04:50, , 9F
所以LIS的演算法應該是不相關的
10/08 04:50, 9F

10/08 04:52, , 10F
我的答案反而是去找一個特定結構,盡量讓遞升狀況最少化
10/08 04:52, 10F

10/08 05:04, , 11F
剛用程式驗證過了,程式網路上就有 http://ppt.cc/jVCC
10/08 05:04, 11F

10/08 05:08, , 12F
如果我的想法沒錯的話,字母數=26這點很微妙 :p
10/08 05:08, 12F

10/08 12:31, , 13F
我發現一件很奇妙的事情!!
10/08 12:31, 13F

10/08 12:45, , 14F
這題在離散數學中很有名.但證明從來沒看懂過(攤)
10/08 12:45, 14F

10/08 13:02, , 15F
幹嘛要出這種題目啊◢▆▅▄▃崩╰(〒皿〒)╯潰▃▄▅▇◣
10/08 13:02, 15F

10/08 13:21, , 16F
PuzzleUp才出到第24題啊...知道其他題目的作法orz
10/08 13:21, 16F

10/08 13:22, , 17F
好想
10/08 13:22, 17F

10/08 13:24, , 18F
我想把 NumberGame轉到MATH版給大家討論.啪所同意嗎
10/08 13:24, 18F

10/08 13:56, , 19F
嗯,OK呀....
10/08 13:56, 19F

10/08 19:08, , 20F
感覺跟鴿籠原理有關
10/08 19:08, 20F

10/08 19:10, , 21F
數學板有討論到這一篇 可是當時沒把編號記下
10/08 19:10, 21F

10/08 19:11, , 22F
現在回頭去找 卻找不到了...好像是這兩個月內的文章
10/08 19:11, 22F

10/08 19:19, , 23F
這比賽我好早就放棄了(崩潰)
10/08 19:19, 23F

10/09 03:13, , 24F
u大說得沒錯 (Math) #1ADqDBUY 鴿籠原理真好用
10/09 03:13, 24F

10/09 10:43, , 25F
看不懂證明+1 不過隱約可以感受到它的原理.....
10/09 10:43, 25F

10/09 12:40, , 26F
http://tinyurl.com/ylqqdd 謝教授的網頁
10/09 12:40, 26F

10/09 12:41, , 27F
其中1.4. 十人中之高矮次序有證明,還蠻好懂的
10/09 12:41, 27F

10/09 12:43, , 28F
不過其中的ain <= ain+1 應該是ain >= ain+1
10/09 12:43, 28F

10/09 15:54, , 29F
那個網頁我之前有找到 也是看不懂啊>"<
10/09 15:54, 29F

10/09 17:44, , 30F
謝教授寫得沒錯 應該是ain <= ain+1
10/09 17:44, 30F

10/09 17:49, , 31F
噢...如果你說的是最後1行的那一個 那的確是筆誤
10/09 17:49, 31F

10/09 18:10, , 32F
a大提到26,26是唯一在平方數(25)和立方數(27)之間的數字
10/09 18:10, 32F

10/09 18:25, , 33F
上次那個硬幣問題 轉到數學板去 馬上被秒殺了
10/09 18:25, 33F

10/09 18:26, , 34F
結果我們還跑了半天的程式 算出來還是錯的答案
10/09 18:26, 34F

10/09 18:26, , 35F
只能說 我們太嫩了
10/09 18:26, 35F

10/09 19:55, , 36F
"我們"應該不包括帕索大...帕索都裝嫩>"<
10/09 19:55, 36F

10/09 20:16, , 37F
咦?u大你硬幣問題也算出最佳解了吧,有錯嗎?@@a
10/09 20:16, 37F
文章代碼(AID): #1Ap7jCAC (puzzle)