Ioi16/test gen tsp

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 14:36, 10 มีนาคม 2559 โดย Jittat (คุย | มีส่วนร่วม)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

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