結果
問題 |
No.3 ビットすごろく
|
ユーザー |
👑 |
提出日時 | 2019-04-22 07:42:39 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 765 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 6,944 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 09:18:33 |
合計ジャッジ時間 | 1,193 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
local n = io.read("*n") task = {} done = 0 tasknum = 1 table.insert(task, 1) local function getbit(x) local cnt = 0 while(0 < x) do if(x % 2 == 1) then cnt = cnt + 1 end x = math.floor(x / 2) end return cnt end local len = {} for i = 1, n do len[i] = -1 end len[1] = 1 while(done < tasknum) do done = done + 1 local curidx = task[done] local b = getbit(curidx) if(0 < curidx - b) then if(len[curidx - b] == -1) then len[curidx - b] = len[curidx] + 1 tasknum = tasknum + 1 table.insert(task, curidx - b) end end if(curidx + b <= n) then if(len[curidx + b] == -1) then len[curidx + b] = len[curidx] + 1 tasknum = tasknum + 1 table.insert(task, curidx + b) end end end print(len[n])