hotpepsiの練習帳

SRM 672

20:31

https://competitiveprogramming.info/topcoder/srm/round/16552/div/1

Div1 Easy (250) Procrastination

問題

• Hugeソフトウェアには無限の従業員がいる
• 従業員には2から連番の従業員番号がついている
• 最初、従業員xにはタスクxが割り当てられる
• 時間tに、2以上の整数Kについて、従業員K×tと従業員K×t+1がタスクを交換する
• 最終的にタスクNが割り当てられる従業員を求める

方針

• (終了後)
• 色々な解き方ができるっぽい
• sqrt(N)までは普通にシミュレーションして交換する
• sqrt(N)からは数が大きくなるので、y=sqrt(N)として、yを1ずつ減らしながら、N÷yをチェックしていく
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_672/Procrastination.cpp

結果

--- 0pt 168th/332 rating 1274 -> 1270 (-4)

従業員Xが最終的に割り当てられるタスクをYとすると、従業員YのタスクはXになるようだ。

なので、問題は「タスクNが割り当てられる従業員」だが、「従業員Nが最後に割り当てられるタスク」でも答えが同じになる。

(例: 従業員8はタスク11が割り当てられ、従業員11はタスク8が割り当てられる。)

http://togetter.com/li/889599