LV. 16
GP 30

RE:【問題】資訊工程研究所畢業 問 都問

樓主 炸豬排 colman4232
13 -
※ 引述《e80704580 (魔王-麻塔巴巴 )》之銘言
> https://zerojudge.tw/ShowProblem?problemid=c296
> 又是這題K彈 上次不會Linkes list刻不出來
> 這是學了Linked list後特地回來刻 還是吃TLE了= =  不過程式碼的結果應該是對的

這個不是linked list還是array還是其他coding技巧的問題 這是演算法理論的問題
先跳脫程式碼的框架 想一下
你要用紙筆解這個問題 你會怎麼做?
就是像題目那樣畫一個圈圈然後慢慢數對ㄅ
但是應該隱約有感覺到 這其中有什麼數學規律 可以不用這樣數吧(有吧><)

今天爆炸頻率K=23之類的時候 你可以用手指一個一個慢慢數下次換誰被爆炸到
假如爆炸頻率K=10 你也會用手指慢慢數嗎?
應該不會吧 會直接n+10就知道下個被星爆炸的人對不對
而隔壁還在用手指慢慢數10個人的時候 你只需要一個加法就夠了 步驟數就整整快了10

好的回到程式碼
沒有 還沒回到程式碼 但是以下編號都從0號開始
先用數學一點的概念想
先假設f(n, m, k)這個數學式 能告訴我們在初始n人、爆炸頻率m人、爆炸k次的情況下 誰會是winner
接著我們這邊用f(8, 3, 5)來演練看看

0 1 2 3 4 5 6 7
f(8, 3, 5)0號同學開始拿炸彈 被炸一輪之後 變成
0 1 X 3 4 5 6 7
接著從3號同學開始拿炸彈 此時!!!此時!!! 我們來把這個座號換一下 變成
5 6 X 0 1 2 3 4
接著ㄋ 轉個角度 就發現這變成了一個f(7, 3, 4)的問題嚕
而若f(7, 3, 4)的答案是為2 那由這個座號變化圖就可以看出來 2號同學原本是5號的 2+3 = 5
而若f(7, 3, 4)的答案是為6 那由這個座號變化圖就可以看出來 6號同學原本是1號的 即(6+3)%8 = 1
這裡實際上f(7, 3, 4)是多少不重要 重要的是怎麼從已知的f(7, 3, 4)獲得f(8, 3, 5)
而從這個歸納 我們可以猜出 f(n, m, k) = ( f(n-1, m, k-1) + m ) %n

接著來應證看看
f(8, 3, 5) = ( f(7, 3, 4) + 3 ) % 8
遞迴下去 f(7, 3, 4) = ( f(6, 3, 3) + 3 ) % 7
遞迴下去 f(6, 3, 3) = ( f(5, 3, 2) + 3 ) % 6
遞迴下去 f(5, 3, 2) = ( f(4, 3, 1) + 3 ) % 5
遞迴下去 f(4, 3, 1) 而這很顯然地會炸到第2個人 並讓第3個人獲勝(0開始)
於是呢
f(4, 3, 1) = 3
f(5, 3, 2) = (3+3) % 5 = 1
f(6, 3, 3) = (1+3) % 6 = 4
f(7, 3, 4) = (4+3) % 7 = 0
f(8, 3, 5) = (0+3) % 8 = 3
於是就知道f(8, 3, 5)最後由3號同學勝出

要注意以上都是從編號0號開始 所以根據題目的要求 你求完f(n, m, k)之後要再多+1
這個遞迴很好實作 10行以內沒問題
大概長這樣吧 C語法有點忘了 錯了請見諒QQ
int boom(int n, int m, int k) {
        if(k==1) return m%n;
        else return ( boom(n-1, m, k-1) +1 ) % n;
}
int main() {
        int n, m, k = input();       //懶得打
        print(boom(n, m, k)+1 );
}
這樣時間複雜度就是O(k) 不需要linked list 不需要array
如果怕遞迴堆疊爆掉的話也可以改成loop版本
這樣如果還TLE我把巴幣全部送你(但我巴幣很少QQ)

程式碼很容易 而困難的是想到這種方法
一般這種程式競賽的題目都牽涉一些機巴演算法 重要的都是「解題想法」
而「寫程式」只是你跟解題系統溝通的工具而已
只有哈囉世界等級的題目 才會把「寫程式」當作題目重點
13
-
未登入的勇者,要加入討論嗎?
板務人員:

7517 筆精華,07/19 更新
一個月內新增 20
歡迎加入共同維護。


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】