結果

問題 No.688 E869120 and Constructing Array 2
ユーザー 👑 obakyanobakyan
提出日時 2019-04-09 15:09:14
言語 Lua
(LuaJit 2.1.1696795921)
結果
WA  
実行時間 -
コード長 750 bytes
コンパイル時間 85 ms
コンパイル使用メモリ 6,940 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 23:00:59
合計ジャッジ時間 2,615 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

function find_a(x)
  --find a where a(a-1) = x
  b = 1 + math.ceil(math.sqrt(x))
  cand = b * (b - 1)
  while(x <= cand) do
    if(x == cand) then return true, b end
    b = b - 1
    cand = b * (b - 1)
  end
  return false, 0
end

k = io.read("*n")
k = k * 2
-- find n, a where k = a(a-1) * 2^(n-a)
c, cpow = 1, 0 -- c = 2^(n-a), cpow = n - a
while(c < 2 * k) do
  if(k % c ~= 0) then c, cpow = c / 2, cpow - 1 break end
  c, cpow = c * 2, cpow + 1
end
found, a = false, 0
-- search from large 2^(n-a)
for i_c = cpow, 0, -1 do
  rem = k / c
  found, a = find_a(rem)
  if(found) then cpow = i_c break end
  c = c / 2
end
if(found) then
  io.write("1")
  for i = 2, a do io.write(" 1") end
  for i = 1, cpow do io.write(" 0") end
  io.write("\n")
end
0