Quiz
https://atcoder.jp/contests/code-thanks-festival-2017-open/tasks/code_thanks_festival_2017_e
Submit
https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/4723793
解法
- 1回のクエリで5袋の審議判定をする
- それぞれ1, 10, 100, 1000, 10000枚で頼む
- 返ってきた値 ans の1桁目が、
- 9なら本物コイン。ans -= 9
- 1なら本物コイン。ans -= 11
- 8なら偽物コイン。ans -= 8
- 0なら偽物コイン。ans -= 10
- 2なら偽物コイン。ans -= 12
- 次は10枚で頼んだ袋の審議判定をする
- ans /= 10
- として、また1桁目を同様に見ていけばいい
editorial
- editorialではコインの種類が5種類なので5進数を使っていた
- 解説では1, 5, 25, 125, 625枚で頼んでいる
- この場合は625 * 5 = 3125枚も使うことで1度のクエリで6袋を判定できる