ABC337 E - Bad Juice

atcoder.jp

問題

• インタラクティブだよ
• N本のジュースがあります。1本腐ってます
  • 腐ってるものを飲むとお腹壊すよ
• 何人かの友人を呼んで、友人たちにジュースを振る舞ってね
• お腹を壊したかどうか教えてくれるから、腐ってるジュースを特定しましょう
  • 特定するために最小の人数の友達呼んでね！

成約

• $ 2 \leq N \leq 100$

思考

• インタラクティブ問題を絶対に許すな高校
• 毒入りワイン問題とかいう有名な論理パズルがあるらしい

• 「そもそも腐ってる可能性のあるジュース飲むから来て！」って声かけて集まってくれる友達なんて存在するわけがないんですよ巫山戯るな

• 例えばさ、3人の友人を呼んだとするよね。居ませんが。

  • 3人の友人のお腹を壊したパターンで、$2³=8$パターンの判定ができるね
  • $log$っぽいね
  • じゃあ、声かける友人の人数が決まったので、適切に担当ジュースを振り分けていく
  • 0_indexedと、誰もお腹壊さなかった場合のケースに注意

コード

N = int(input())
cnt = len(bin(N-1)[2:])
print(cnt)

L = [[] for i in range(cnt)]
for num in range(cnt):
    tmp = []
    for i in range(N):
        if (i >> num) & 1:
            tmp.append(i)
    print(len(tmp),*tmp)

S = input()
S = S[::-1]
ans = int(S,2)
if ans == 0:
    ans = N
print(ans)