結果

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

テストケース

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

ソースコード

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
  print(a + cpow)
  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