คุณและเพื่อนๆของคุณอีก n-1 คน (นับรวมคุณเป็น n คน) นั่งเล่นเกมปัญญาอ่อนด้วยกัน ซึ่งมีกฎดังนี้

1.       1. ทุกคนจะนั่งกันเป็นวงกลมและจะติดหมายเลขประจำตัวโดยเริ่มจากคนที่ 1, 2, 3, … , n (คนที่หมายเลขต่างกัน 1 จะนั่งติดกันและคนหมายเลข n จะนั่งติดกับคนหมายเลข 1)

2.       2. เกมจะเริ่มโดยการกำหนดหมายเลข k ขึ้น

3.       3. คนที่มีหมายเลขของตนเป็น k จะต้องลุกออกจากวง จากนั้นคนที่นั่งถัดจากคนหมายเลข k จะต้องเริ่มนับเลข 1, คนถัดไปนับเลข 2 ไปเรื่อยๆ (จะไม่นับคนที่ออกจากวงไปแล้ว) จนมีคนนับเลข k ขึ้น กำหนดให้คนที่นับเลข k คือคนหมายเลข i

4.       4. ทำตามข้อ 3 ซ้ำแต่เปลี่ยนค่า k ให้มีค่าเท่ากับ i

5.       5. เกมจะจบเมื่อเหลือคนเพียงคนเดียว ซึ่งก็คือผู้ชนะ

ตัวอย่าง

กำหนด n = 5 และ k = 2

เริ่มต้นที่ k = 2 ทำให้หมายเลข 2 ต้องออกไป (วงกลมสีแดง แสดงถึงหมายเลขที่ออกจากวงไปแล้วและจะไม่เกี่ยวข้องกับเกมอีก)

หลังจากนั้น หมายเลข 3 จะนับ “1”  หมายเลข 4 จะนับ “2”  ทำให้ k = 4 และหมายเลข 4 ต้องออกไป

หลังจากนั้น หมายเลข 5 จะนับ “1”  หมายเลข 1 จะนับ “2”  หมายเลข 3 จะนับ “3”  หมายเลข 5 จะนับ “4”  ทำให้ k = 5 และหมายเลข 5 ต้องออกไป

หลังจากนั้น หมายเลข 1 จะนับ “1”  หมายเลข 3 จะนับ “2”  หมายเลข 1 จะนับ “3”  หมายเลข 3 จะนับ “4”  หมายเลข 1 จะนับ “5”  ทำให้ k = 1 และหมายเลข 1 ต้องออกไป

จบการแข่งขัน หมายเลข 3 เป็นผู้ชนะ

กำหนดค่า n และ k จงหาหมายเลขของผู้ชนะ

ข้อมูลนำเข้า

บรรทัดแรกและบรรทัดเดียวประกอบด้วยจำนวนนับ n และ k ( 2 < n < 200 000 , 1 < k < n )

ข้อมูลส่งออก

บรรทัดแรกและบรรทัดเดียวแสดงหมายเลขของผู้ที่ชนะเกมการแข่งขันนี้

โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int )

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์