Ioi16/test gen tsp

input

input ของโปรแกรมในโจทย์ข้อ tsp (ควรเป็น output ของคุณ) มีรูปแบบดังนี้

• บรรทัดแรกระบุ N แทนจำนวนเมือง (N <= 11 อาจปรับได้ จะแจ้งอีกครั้ง) เมืองเรียกเป็นเมืองที่ 1,2,...,N
• อีก N บรรทัดระบุพิกัดของเมือง N เมือง โดยแต่ละบรรทัดระบุพิกัด x และ y เป็นจำนวนจริง มีค่าระหว่าง 0 - 1000

ตัวอย่าง

5
0 0
10 0
0 10
10 10
1 5

output

output ที่โปรแกรมทดสอบของข้อนี้จะพิมพ์ผลลัพธ์รวม N บรรทัด เป็นลำดับของเมืองที่จะเดินทางไป เป็นจำนวนเต็มไม่ซ้ำกัน กล่าวคือ ถ้าเราเดินทางตามคำตอบนี้จะเดินทางเริ่มจากเมืองในบรรทัดแรก ไล่ไปจนถึงเมืองที่มีหมายเลขตามบรรทัดที่ N และกลับไปยังเมืองแรก

โปรแกรมทดสอบ

ดาวน์โหลดได้ที่ http://theory.cpe.ku.ac.th/~jittat/ioi/2016/test-gen/tsp/

• random - พิมพ์คำตอบเป็นลำดับสุ่มของเมือง N เมือง
• greedy1 - เริ่มจากเมือง 1 เลือกเมืองใกล้สุดที่ยังไม่เคยไป ไล่ไปเรื่อย ๆ
• greedyall - ทดลองเริ่มจากทุกเมือง จากนั้นใช้ greedy เลือกคำตอบที่ดีที่สุด
• opt - หาคำตอบที่ดีที่สุด

โปรแกรมอื่น ๆ

• ev - โปรแกรมคำนวณระยะทางรวมที่ใช้เดินตามคำตอบ สั่งโดย ev input output