IOI17 Coins

Abridged Problem Statement

Problem statement

มีคนสองคนและตารางขนาด $8 \times 8$ โดยแต่ละช่องของตารางจะมีเหรียญอยู่ช่องละ 1 เหรียญ และแต่ละเหรียญจะมีชื่อตั้งแต่ $0$ ถึง $63$ โดยเรียงตามลำดับจากซ้ายไปขวา และจากบนลงล่าง

โดยในตอนแรกแต่ละเหรียญจะเป็นหัวหรือก้อยตาม std::vector<int> b ที่ได้รับมา
มี 1 คนที่รู้ว่าเเหรียญที่ต้องการหาคือเหรียญ $c$ แต่ทว่าในการหาเหรียญ $c$ นั้นคนที่จะตอบ(อีกคนหนึ่ง)ก็จะไม่รู้ว่าเหรียญ $c$ คือเหรียญหมายเลขใด

งานของคุณ ช่วยคิดวิธีทำให้คนที่ไม่รู้ว่าเหรียญ $c$ สามารถรู้ได้ว่าเหรียญ $c$ คือเหรียญใดโดยคนที่รู้ว่าเหรียญ $c$ คือเหรียนไหนพลิกเหรียญได้ไม่เกิน $k$ ครั้ง

ปัญหาย่อย $c < 0, k = 1$

ในกรณีนี้สามารถแก้ได้โดย

1. ถ้า $c=0$ ให้พลิกเหรียญหมายเลข $0$ เป็น $0$ ได้โดยพลิกไม่เกิน $1$ ครั้ง
2. ถ้า $c=1$ ให้พลิกเหรียญหมายเลข $0$ เป็น $1$ ได้โดยพลิกไม่เกิน $1$ ครั้ง

ปัญหาย่อย $k=64$

พลิกเหรียญทั้งหมดที่ไม่ใช่ $c$ ให้เป็น $0$ และทำให้เหรียญ $c$ เป็น $1$ ทำได้ในการพลิกไม่เกิน $64$ ครั้ง

ปัญหาย่อย $k=8$

แปลงตารางช่อง $0,1,\dots,7$ ให้เป็นเลขฐานสอง ของ $c$ ทำทำได้ในการพลิกไม่เกิน $8$ ครั้ง

ปัญหาเต็ม $k=1$

นำหมายเลขของเหรียญที่พลิกเป็นหน้า $1$ มา $\oplus$ (Binary XOR) กันได้ $z*$ แล้วพลิกเหรียญหมายเลข $c \oplus z*$ ทำให้พลิกเพียง $1$ ครั้งเท่านั้น

เมื่ออีกคนมาหาหมายเลข $c$ ก็สามารถนำหมายเลขของเหรียญที่มีค่าเป็น $1$ มา $\oplus$ กันเพื่อหาเหรียญ $c$ ได้เลย

โดยการทำวิธีการนี้อาศัยสมบัติของ $\oplus$ คือ

Solution Code