let's code: แก้โจทย์ ACM-ICPC

ACM-ICPC หรือเรามักที่เรียกย่อๆ กันว่า ACM คืองานแข่งขันโปรแกรมมิ่งในระดับอุดมศึกษาทั่วโลก นศ.ที่เรียนทางด้านวิศวกรรม-วิทยาการคอมพิวเตอร์ ก็คงหนีไม่พ้นที่จะโดนอาจารย์ชักชวนให้ลงแข่งเป็นแน่แท้

และด้วยความที่มันเป็นการแข่งที่แพร่หลายมาก ก็ทำให้มี mirror site เกิดขึ้นมากมาย เช่น Online Judge, Zhejiang University หรือจะลองไปถามๆ อาจารย์ที่ภาควิชาคอมพิวเตอร์ดูก็ได้นะ :D

ระดับความยากของโจทย์นั้นถือว่าอยู่ในระดับกลางๆ เนื่องจากการแข่งแต่ละรอบจะมีโจทย์ให้ทำค่อนข้างเยอะพอสมควร แต่ก็ชดเชยกับการที่ลงแข่งกันเป็นทีมละไม่เกิน 3 คน ทำให้สามารถแบ่งหน้าที่ตามที่แต่ละคนถนัดได้ครับ

ภาษาที่ใช้ได้
C/C++, Java, Pascal

รูปแบบการตรวจคำตอบ
ส่ง source code ให้ server ประมวลผลกับ test case

ตัวอย่างโจทย์

• 2088 - Entropy: สมมติให้คำในภาษาอังกฤษมาคือ "AAAAABCD" ถ้าย่อตัวอักษรแต่ละตัวด้วยบิตดังนี้ {"A": "0", "B": "10", "C": "110", "D": "111"} จะได้ว่าคำนี้สามารถเขียนด้วยบิตได้สั้นที่สุด (entropy encoding) ถ้าให้คำใดๆ มา จงบอกว่าคำนั้นสามารถย่อได้เหลือกี่บิต
• 2145 - Lost in Space: ให้ความยาวด้านทั้งสามของสามเหลี่ยมต้นแบบมา และให้เซ็ตของพิกัด xyz ของจุดมาอีกจำนวนหนึ่ง จงหาจุด 3 จุดจากเซ็ตนั้น ที่จะสร้างสามเหลี่ยมคล้ายกับสามเหลี่ยมต้นแบบ (มีสัดส่วนด้านทั้งสามคงเดิม) และมี error น้อยกว่า 0.01%
• 2334 - Gridland: สมมติประเทศ ซึ่งเมืองแต่ละเมืองอยู่บนกริดขนาด N x M แต่ละเมืองสามารถเดินทางไปยังเมืองอื่นๆ ที่อยู่ติดกันได้ 8 ทิศ คนขายของต้องเดินทางสั้นที่สุดเป็นระยะทางเท่าไหร่ ถึงจะผ่านเมืองครบทุกเมือง