#462885 (Lua) No.355 数当てゲーム(2)

提出ソース

結果

問題	No.355 数当てゲーム(2)
ユーザー	👑 obakyan
提出日時	2020-04-11 22:51:57
言語	Lua (LuaJit 2.1.1696795921)
結果	AC
実行時間	28 ms / 2,000 ms
コード長	3,873 bytes
コンパイル時間	398 ms
コンパイル使用メモリ	5,212 KB
実行使用メモリ	24,396 KB
平均クエリ数	39.37
最終ジャッジ日時	2023-09-24 02:34:30
合計ジャッジ時間	4,669 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	28 ms 24,072 KB
testcase_01	AC	26 ms 23,424 KB
testcase_02	AC	26 ms 23,436 KB
testcase_03	AC	28 ms 23,424 KB
testcase_04	AC	27 ms 23,436 KB
testcase_05	AC	26 ms 23,868 KB
testcase_06	AC	27 ms 24,228 KB
testcase_07	AC	23 ms 24,384 KB
testcase_08	AC	25 ms 24,372 KB
testcase_09	AC	25 ms 23,436 KB
testcase_10	AC	27 ms 24,396 KB
testcase_11	AC	28 ms 23,436 KB
testcase_12	AC	28 ms 24,072 KB
testcase_13	AC	27 ms 24,360 KB
testcase_14	AC	24 ms 23,844 KB
testcase_15	AC	26 ms 23,652 KB
testcase_16	AC	25 ms 24,072 KB
testcase_17	AC	26 ms 24,012 KB
testcase_18	AC	25 ms 23,436 KB
testcase_19	AC	27 ms 23,544 KB
testcase_20	AC	25 ms 24,340 KB
testcase_21	AC	25 ms 23,848 KB
testcase_22	AC	25 ms 23,404 KB
testcase_23	AC	24 ms 24,028 KB
testcase_24	AC	25 ms 24,352 KB
testcase_25	AC	26 ms 24,352 KB
testcase_26	AC	23 ms 23,560 KB
testcase_27	AC	24 ms 23,632 KB
testcase_28	AC	23 ms 23,836 KB
testcase_29	AC	26 ms 23,428 KB
testcase_30	AC	28 ms 23,548 KB
testcase_31	AC	28 ms 23,392 KB
testcase_32	AC	24 ms 23,860 KB
testcase_33	AC	26 ms 24,256 KB
testcase_34	AC	26 ms 24,256 KB
testcase_35	AC	23 ms 23,856 KB
testcase_36	AC	24 ms 24,040 KB
testcase_37	AC	25 ms 23,848 KB
testcase_38	AC	25 ms 23,656 KB
testcase_39	AC	25 ms 24,028 KB
testcase_40	AC	26 ms 23,428 KB
testcase_41	AC	26 ms 24,364 KB
testcase_42	AC	23 ms 23,656 KB
testcase_43	AC	26 ms 23,440 KB
testcase_44	AC	27 ms 24,040 KB
testcase_45	AC	25 ms 24,052 KB
testcase_46	AC	26 ms 24,016 KB
testcase_47	AC	25 ms 24,388 KB
testcase_48	AC	25 ms 24,028 KB
testcase_49	AC	25 ms 23,680 KB
testcase_50	AC	27 ms 23,440 KB
testcase_51	AC	27 ms 24,364 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

local mfl, mce = math.floor, math.ceil
local g_cnt = 0
-- local function ask(tbl)
--   g_cnt = g_cnt + 1
--   local z = {8, 3, 5, 1}
--   local h, b = 0, 0
--   for j = 1, 4 do
--     for k = 1, 4 do
--       if tbl[j] == z[k] then
--         if j == k then h = h + 1
--         else b = b + 1
--         end
--       end
--     end
--   end
--   print("-- " .. g_cnt .. " --")
--   print("Ask is: " .. table.concat(tbl, " "))
--   print("Ans is: " .. h .. " " .. b)
--   if h == 4 then os.exit() end
--   return h + b
-- end
local function ask(tbl)
  io.write(table.concat(tbl, " "))
  io.write("\n")
  io.flush()
  local ret = io.read()
  local hit, blow = ret:match("(%d) (%d)")
  hit, blow = tonumber(hit), tonumber(blow)
  if hit == 4 then os.exit() end
  return hit + blow
end

local function combination_get_map(n)
  local combmap = {}
  for i = 1, n do
    combmap[i] = {}
    local ret = 1
    for j = 1, i do
      ret = mfl(ret * (i + 1 - j) / j)
      combmap[i][j] = ret
    end
  end
  return combmap
end
local function combination_get_count(combmap, n, k)
  if k < 0 then return 0
  elseif n < k then return 0
  elseif k == 0 then return 1
  else return combmap[n][k]
  end
end

local function combination_get_array(combmap, n, k, idx)
  local rem = k
  local retary = {}
  for i = 1, n do
    local useCnt = combination_get_count(combmap, n - i, rem - 1)
    local unuseCnt = combination_get_count(combmap, n - i, rem)
    if idx <= useCnt then
      rem = rem - 1
      table.insert(retary, i)
    else
      idx = idx - useCnt
    end
  end
  return retary
end

local function getpattern(n, patall, idx)
  local used = {}
  local retary = {}
  local div = patall
  for i = 1, n do used[i] = false end
  for i = n, 1, -1 do
    div = mfl(div / i)
    local v_idx = mfl(idx / div)
    idx = idx % div
    local tmp_idx = 0
    for j = 1, n do
      if not used[j] then
        if tmp_idx == v_idx then
          table.insert(retary, j)
          used[j] = true
          break
        else
          tmp_idx = tmp_idx + 1
        end
      end
    end
  end
  return retary
end

local function solve(cand)
  local last4 = {}
  local cmap = combination_get_map(#cand)
  local tot = combination_get_count(cmap, #cand, 4)
  for i = 1, tot do
    local ary = combination_get_array(cmap, #cand, 4, i)
    local askary = {}
    for j = 1, 4 do
      askary[j] = cand[ary[j]]
    end
    local z = ask(askary)
    if z == 4 then
      for j = 1, 4 do last4[j] = askary[j] end
      break
    end
  end
  for ip = 0, 23 do
    local idxary = getpattern(4, 24, ip)
    local z = {}
    for j = 1, 4 do
      z[j] = last4[idxary[j]]
    end
    ask(z)
  end
end

local a0123 = ask({0, 1, 2, 3})
local a4567 = ask({4, 5, 6, 7})

if a0123 == 0 then
  solve({4, 5, 6, 7, 8, 9})
elseif a4567 == 0 then
  solve({0, 1, 2, 3, 8, 9})
elseif a0123 + a4567 == 4 then
  solve({0, 1, 2, 3, 4, 5, 6, 7})
elseif a0123 + a4567 == 2 then
  -- a0123 == 1 and a4567 = 1
  for i = 0, 15 do
    local f1 = i % 4
    local f2 = 4 + mfl(i / 4)
    local z = ask({f1, f2, 8, 9})
    if z == 4 then
      solve({f1, f2, 8, 9})
      break
    end
  end
elseif a0123 == 1 then
  -- a4567 = 2
  local p1 = {4, 4, 4, 5, 5, 6}
  local p2 = {5, 6, 7, 6, 7, 7}
  for i = 0, 47 do
    local f0123 = i % 4
    local rem = mfl(i / 4)
    local f89 = 8 + (rem % 2)
    rem = 1 + mfl(rem / 2)
    local z = ask({f0123, p1[rem], p2[rem], f89})
    if z == 4 then
      solve({f0123, p1[rem], p2[rem], f89})
      break
    end
  end
else -- a0123 = 2, a4567 == 1
  local p1 = {0, 0, 0, 1, 1, 2}
  local p2 = {1, 2, 3, 2, 3, 3}
  for i = 0, 47 do
    local f4567 = 4 + (i % 4)
    local rem = mfl(i / 4)
    local f89 = 8 + (rem % 2)
    rem = 1 + mfl(rem / 2)
    local z = ask({p1[rem], p2[rem], f4567, f89})
    if z == 4 then
      solve({p1[rem], p2[rem], f4567, f89})
      break
    end
  end
end

yukicoder

結果

テストケース

ソースコード