ผลต่างระหว่างรุ่นของ "Ioi16/test gen tsp"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย '== input == input ของโปรแกรมในโจทย์ข้อ tsp (ควรเป็น output ของคุณ) ...')
 
 
แถว 15: แถว 15:
 
1 5
 
1 5
 
</pre>
 
</pre>
 
  
 
== output ==
 
== output ==

รุ่นแก้ไขปัจจุบันเมื่อ 14:36, 10 มีนาคม 2559

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