Gcj2014

Round 1A 2014

A. Charging Chaos

Source: [1]

ชาวนา Shota มีปัญหา เขาเพิ่งจะย้ายไปที่บ้านฟาร์ม แต่ระบบปลั๊กไฟนั้นมีการติดตั้งที่ผิดพลาด เนื่องจากเขาเป็นชาวนายุคใหม่ Shota จึงมีมือถือและแลบทอปจำนวนมาก เขามีอุปกรณ์รวมทั้งสิ้น N ชิ้น

อุปกรณ์เหล่านี้มี spec ที่แตกต่างกันและทำโดยบริษัทที่แตกต่างกันด้วย อุปกรณ์เหล่านี้จึงมีความต้องการการไหลของกระแสไฟที่แตกต่างกัน ในทำนองเดียวกันปลั๊กไฟแต่ละอันก็มีการปล่อยกระแสไฟที่แตกต่างกันด้วย กระแสไฟที่ปล่องนี้ สามารถแทนได้ด้วยสตริงของ 0 และ 1 ความยาว L ตัวอักษร

Shota ต้องการที่จะชาร์ตอุปกรณ์ทั้ง N ชิ้นนี้พร้อม ๆ กัน และก็เป็นเหตุบังเอิญเลยทีเดียวที่ในบ้านก็มีปลั๊กจำนวน N อันเช่นเดียวกัน ในการปรับแต่งกระแสไฟฟ้า จะมีแป้นควบคุมที่ประกอบไปด้วยสวิตช์จำนวน L อัน สวิตช์อันที่ i จะสลับบิตที่ i ของกระแสไฟฟ้าของทุก ๆ ปลั๊กในบ้าน ยกตัวอย่างเช่น ถ้ากระแสของแต่ละปลั๊กเป็นดังนี้:

Outlet 0: 10
Outlet 1: 01
Outlet 2: 11

การสลับสวิตช์ตัวที่ 2 จะเปลี่ยนกระแสไฟฟ้าเป็น

Outlet 0: 11
Outlet 1: 00
Outlet 2: 10

ถ้า Shota มีมือถือที่ใช้กระแส "11" ในการชาร์ต, แทบเบล็ตที่ใช้กระแส "10" ในการชาร์ตและแลบทอปที่ใช้กระแส "00" ในการชาร์ต การสลับสวิชต์ที่ 2 จะทำให้เค้ามีความสุขอย่างมาก

Misaki ได้รับการว่าจ้างจาก Shota ให้ช่วยเขาแก้ปัญหา เธอได้วัดกระแสจากทุก ๆ ปลั๊กในบ้านและสังเกตว่ามันแตกต่างกันทั้งหมด ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่ Shota จะสามารถชาร์ตอุปกรณ์ทั้งหมดของเขาในเวลาเดียวกันได้หรือไม่ ถ้าเป็นไปได้ ให้หาว่าจำนวนสวิชต์ที่ต้องสลับทั้งหมดที่น้อยที่สุดเป็นเท่าใด (เนื่องจาก Misaki ไม่อยากจะเหนื่อยกดสวิชต์มากเกินความจำเป็น)

B. Full Binary Tree

Source: [2]

tree คือ connected graph ที่ไม่มี cycle

rooted tree คือ tree ที่มีจุดยอดพิเศษที่เรียกว่า root. ถ้ามีเส้นเชื่อมระหว่าง X และ Y ใน rooted tree, เราจะกล่าวว่า Y เป็นลูกของ X ถ้า X อยู่ใกล้กับ root มากกว่า Y (กล่าวคือ เส้นทางสั้นที่สุดจาก root ไปยัง X สั้นกว่าเส้นทางที่สั้นที่สุดจาก root ไปยัง Y)

full binary tree คือ rooted tree ที่ทุก ๆ จุดยอดมีลูกสองจุดยอดพอดี หรือไม่ก็ไม่มีเลย

คุณได้รับ tree G ที่มี N โหนด (เรียกเป็นโหนด 1 ถึง N) คุณจะสามารถลบบางโหนดทิ้งได้ ถ้าโหนดถูกลบทิ้ง เส้นเชื่อมทั้งหมดที่ต่อกับโหนดนั้นก็จะถูกลบไปด้วย งานของคุณคือลบโหนดให้น้อยที่สุดเพื่อโหนดที่เหลือเป็น full binary tree สำหรับบาง root ที่เลือกจากโหนดที่เหลือ

C. Proper Shuffle

Source: [3]