กระต่ายกับเต่า (acm15_chasing)


Time limit:
1000 ms
Memory limit:
256 MB

กระต่ายกับเต่ากำลังวิ่งไล่จับกันบนทางวิ่งที่วนเป็นวงกลมขนาด N ช่อง แต่ละช่องมีหมายเลขกำกับตั้งแต่ช่องที่ 1, 2, …, N โดยช่องที่ N จะอยู่ติดกับช่องที่ 1 ทางวิ่งนี้เป็นทางวิ่งทางเดียว กล่าวคือ ถ้าเราอยู่ในช่องที่ i จะต้องวิ่งต่อไปยังช่องที่ i+1 เสมอ ยกเว้นกรณีอยู่ในช่องที่ N จะวิ่งต่อไปยังช่องที่ 1

เมื่อเริ่มเกม กระต่ายจะอยู่ในช่องที่ R และเต่าจะอยู่ในช่องที่ T กระต่ายและเต่าจะผลัดกันวิ่งไปเรื่อย ๆ โดยในแต่ละรอบ เต่าจะได้เริ่มวิ่งก่อนเป็นระยะ 1 ช่อง ตามทิศที่กล่าวไว้ข้างต้น หลังจากนั้น กระต่ายจะวิ่งเป็นระยะ 2 ช่อง ตามทิศที่กล่าวไว้ข้างต้นเช่นกัน เกมจะจบลงเมื่อกระต่ายและเต่าอยู่ในช่องเดียวกัน (เกมอาจจะจบแม้ว่ากระต่ายยังวิ่งไม่ครบ 2 ช่องก็ได้) เนื่องจากเกมนี้ใช้เวลานานพอสมควร คุณซึ่งเป็นกรรมการจึงอยากทราบว่าเกมจะจบลงในรอบที่เท่าใด (เกม 1 รอบประกอบด้วยการที่เต่าวิ่งและกระต่ายวิ่ง ถ้าทั้งสองอยู่ในช่องเดียวกันตั้งแต่เริ่มเกม ให้ถือว่าเกมจบในรอบที่ 0)

จงเขียนโปรแกรมเพื่อรับจำนวนช่องของทางวิ่งและหมายเลขของช่องเริ่มต้นของกระต่ายและเต่า จากนั้นคำนวณว่าเกมจะจบลงในรอบที่เท่าใด

Input

บรรทัดแรก ระบุจำนวนเต็ม K (1 ≤ K ≤ 100,000) แทนจำนวนเกมที่กระต่ายและเต่าวิ่งไล่จับกัน

อีก K บรรทัดต่อมา แต่ละบรรทัดประกอบด้วยจำนวนเต็ม Ni Ri Ti (1 ≤ Ni ≤ 1018,
1 ≤ Ri, Ti ≤ Ni) ระบุจำนวนช่องของทางวิ่ง หมายเลขของช่องเริ่มต้นของกระต่าย และหมายเลขของช่องเริ่มต้นของเต่า ในเกมที่ i ตามลำดับ

Output

มี K บรรทัด ระบุว่าในแต่ละเกม เกมจะจบลงในรอบที่เท่าใด

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None