a561: [經典題] 約瑟夫問題
標籤 : data structure treap 數學 資料結構
通過比率 : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2025-01-02 11:56

內容

給你$N$個人圍成一圈,編號是0, 1, 2...n-1。編號相差1的人相鄰(編號0與編號$N-1$相鄰),一開始由編號0開始報數(接著是編號1,依此類推),報到$k$的人要被淘汰,然後從被淘汰的下一人開始下一輪報數,直到只剩下一人,請問最後剩下的人的編號是多少?

例如 N=3 k=2,則會先淘汰掉編號1接著淘汰編號0,最後剩下的便是編號2。

輸入說明

第一行會輸入$N$跟$k$。

對於8%的測資,滿足$1\le k \le N \le 100$

對於27%的測資,滿足$1\le k \le N \le 5000$

對於30%的測資,滿足$1\le k \le N \le 2 \times 10^5$

對於35%的測資,滿足$1\le k \le N \le 2 \times 10^7$

輸出說明

輸出最後剩下的人的編號

範例輸入 #1
3 2
範例輸出 #1
2
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (2%): 1.0s , <1K
不公開 測資點#1 (2%): 1.0s , <1K
不公開 測資點#2 (2%): 1.0s , <1K
不公開 測資點#3 (2%): 1.0s , <1K
不公開 測資點#4 (9%): 1.0s , <1K
不公開 測資點#5 (9%): 1.0s , <1K
不公開 測資點#6 (9%): 1.0s , <1K
不公開 測資點#7 (6%): 1.0s , <1K
不公開 測資點#8 (6%): 1.0s , <1K
不公開 測資點#9 (6%): 1.0s , <1K
不公開 測資點#10 (6%): 1.0s , <1K
不公開 測資點#11 (6%): 1.0s , <1K
不公開 測資點#12 (7%): 1.0s , <1K
不公開 測資點#13 (7%): 1.0s , <1K
不公開 測資點#14 (7%): 1.0s , <1K
不公開 測資點#15 (7%): 1.0s , <1K
不公開 測資點#16 (7%): 1.0s , <1K
提示 :

成為數學家

標籤:
data structure treap 數學 資料結構
出處:
[管理者:
haha (大學長)
]


編號 身分 題目 主題 人氣 發表日期
160
211075@stu.c... (c++豪難)
a561
100%
16 2025-01-28 12:18