Fario2014

Source: [1]

Problem 1: Network System Administration

คุณเป็น Network System Administrator (NSA) ของโรงเรียนแห่งหนึ่ง เนื่องจากโรงเรียนเพิ่งโดนแฮ็คเพื่อแก้หน้าเว็บไซต์ คุณจึงได้ถูกจ้างมาเพื่อเฝ้าระวังเครื่องข่ายของโรงเรียน

ผู้บริหารโรงเรียนได้ตกลงที่จะมอบ meta data ของการส่งอีเมลของนักเรียน (คือเวลาที่ส่ง ผู้ส่ง ผู้รับของทุก ๆ อีเมลที่วิ่งผ่านเครือข่าย) แต่การตัดสินใจนี้ทำให้เกิดการโวยวายจากเหล่านักเรียนเป็นอันมากเพราะว่าอาจจะเข้าข่ายละเมิดความเป็นส่วนตัวของนักเรียน

เพื่อที่แสดงว่าการได้รับข้อมูลดังกล่าวของคุณนั้นเหมาะสม คุณจะเขียนโปรแกรมเพื่อแสดงว่า meta data ดังกล่าวจะมีประโยชน์ในกรณีที่มีการบุกรุกของลาโทรจัน (trojan mule) จากการฝึกอบรมของ NSA คุณทราบว่าลาโทรจันคือไวรัสที่ทำงานคล้าย ๆ กับ ม้าโทรจัน เพียงแต่ว่า มันจะไม่ขยายพันธุ์เท่านั้น

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

โปรแกรมคอมพิวเตอร์ของคุณจะต้องสามารถตอบคำถามที่อยู่ในรูปแบบ "ถ้าลาโทรจันเริ่มต้นอยู่ที่เครื่องคอมพิวเตอร์ X เครื่องคอมพิวเตอร์เครื่องใดที่มันอยู่ในขณะนี้?" คำถามเหล่านี้จะปะปนกับข้อมูล meta data ของอีเมลใหม่

Problem 2: Connect

คุณกำลังสร้างวงจรสำหรับ xPhone 6 โทรศัพท์ที่จะปฏิวัติวงการด้วยความหนาที่ลดลง 2.2 มิลลิเมตร และความโค้งมนที่ลดลงไป 5.4% จากเครื่อง xPhone 5 ที่ตกรุ่นและไร้คุณค่าแล้ว

วงจรที่คุณจะสร้างอยู่ในรูปแบบนี้:

• มีโหนดจำนวน 2N โหนดบนสายสัญญาณหลัก (เรียกว่า bus) เชื่อมต่อกันเป็นเส้น

• แต่ละโหนดจะต้องเชื่อมกับอีกหนึ่งโหนดโดยใช้สายสัญญาณเส้นใหม่ โหนดทั้ง 2N โหนดจะถูกกำหนดชื่อด้วยจำนวนเต็มระหว่าง 1 ถึง N จะมีโหนดสองโหนดพอดีที่มีชื่อเดียวกันและคู่ของโหนดเหล่านี้จะต้องถูกเชื่อมเข้าด้วยกันด้วยสายสัญญาณใหม่รวม N เส้น

• วงจรจะต้องถูกพิมพ์ออกมาบนแผ่นวงจร ดังนั้น จะต้องไม่มีสายสัญญาณคู่ใดที่ตัดกัน สายสัญญาณใหม่ที่จะเพิ่มเข้าไปนั้นจะต้องอยู่ด้านบนอย่างเดียว หรืออยู่ด้านล่างอย่างเดียวของสายสัญญาญหลักเท่านั้น

(ดูรูปในแฟ้ม)

รูปด้านซ้ายระบุวิธีการวางสายสัญญาณที่ใช้ได้ รูปกลางแสดงตัวอย่างการวางสายสัญญาณที่ผิด รูปขวาแสดงวิธีการวางสายสัญญาณที่สายสัญญาณใหม่อยู่ด้านบนของสายสัญญาณหลักเท่านั้น สังเกตว่าสำหรับกรณีทดสอบด้านซ้ายและตรงกลาง เราจะไม่สามารถวางสายให้ผ่านเงื่อนไขโดยที่วางสายสัญญาณใหม่อยู่ด้านบนสายสัญญาณหลักเสมอ

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

Problem 3: Super Maria II: Another Castle

Fungus Republic กลับสู่ความสงบสุขไปครั้งหนึ่งด้วยความช่วยเหลือจาก Maria ช่างไฟฟ้าผู้ถ่อมตน แต่ทุกอย่างกลับสิ้นสลายเนื่องจากการรุกรานของ Wowser โดย Wowser ได้จับตัว Prince Nectarine (อีกแล้ว) และซ่อนไว้ในที่ที่ Maria จะไม่มีวันหาเจอ

อย่างไรก็ตาม Maria ก็ไม่หวาดหวั่นแต่อย่างใด อาศัยสัญญาณจากโทรศัพท์เห็ดของ Nectarine, Maria ได้จำกัดขอบเขตการค้นหาอยู่ที่ปราสาท N หลัง ปราสาทเหล่านี้เรียงตัวกันเป็นเส้นตรงโดยมีหมายเลขเป็น 0 ถึง N-1 โดยปราสาทที่ 0 อยู่ด้านซ้ายสุด และ 1 อยู่ถัดมาตามลำดับ

Maria นั้นเร่งรีบที่จะหาองค์ชาย เธอจึงได้เช่ารถลากที่ลากโดยไดโนเสาร์ Shoyi เมื่อใดก็ตามที่ Maria ต้องการลงจากรถหรือต้องการให้รถลากเปลี่ยนทิศทางเธอจะต้องให้ทิปกับ Shoyi

Maria เริ่มต้นที่ปราสาท 0 หันหน้าไปทางขวา เมื่อ Maria ไปถึงปราสาท i เธอสามารถทำเลือกทำกิจกรรมจากกิจกรรมทั้งสามแบบดังนี้

• เดินทางไปยังปราสาทถัดไปในทิศทางที่หันอยู่ตอนนี้ โดยไม่ต้องเสียเงินแต่อย่างใด นั่นคือ ถ้าเธอหันไปทางซ้าย เธอสามารถเดินทางไปยังปราสาท j ใด ๆ โดยไม่เสียค่าใช้จ่าย ถ้า j < i และถ้าเธอหันไปทางขวา เธอสามารถเดินทางไปยังปราสาท j โดยไม่เสียค่าใช้จ่าย ถ้า j > i

• จ่ายเงิน C₁ หน่วย เพื่อให้กลับรถลากและหันหน้าไปอีกทางหนึ่ง

• จ่ายเงิน C₂ เพื่อลงจากรถลากเพื่อไปเปิดประตูปราสาท i ถ้า Maria เลือกจะทำกิจกรรมนี้ มีเหตุการณ์เกิดขึ้นได้สองแบบ คือ
  • เธอเจอเจ้าชาย สู้ชนะ Wowser และกลับไปยัง Fungus Republic อย่างปลอดภัย
  • เธอเจอกบ โดยกบจะบอกเธอว่าเจ้าชายอยู่ในปราสาทอื่น และการไปยังปราสาทนั้นจากปราสาทนี้ จะต้องไปในทิศทางใด (ซ้ายหรือขวา)

Maria ต้องการให้จำนวนเหรียญที่ต้องจ่ายนั้น น้อยที่สุด Maria หยิบแลบทอปคู่ใจขึ้นมาแล้วส่งอีเมลหาคุณให้ช่วยแก้ปัญหานี้ทันที