ผลต่างระหว่างรุ่นของ "Gcj2014"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
| − | == Round 1A == | + | == Round 1A 2014 == |
| − | === Charging Chaos === | + | === A. Charging Chaos === |
Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p0] | Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p0] | ||
| แถว 29: | แถว 29: | ||
Misaki ได้รับการว่าจ้างจาก Shota ให้ช่วยเขาแก้ปัญหา เธอได้วัดกระแสจากทุก ๆ ปลั๊กในบ้านและสังเกตว่ามันแตกต่างกันทั้งหมด ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่ Shota จะสามารถชาร์ตอุปกรณ์ทั้งหมดของเขาในเวลาเดียวกันได้หรือไม่ ถ้าเป็นไปได้ ให้หาว่าจำนวนสวิชต์ที่ต้องสลับทั้งหมดที่น้อยที่สุดเป็นเท่าใด (เนื่องจาก Misaki ไม่อยากจะเหนื่อยกดสวิชต์มากเกินความจำเป็น) | Misaki ได้รับการว่าจ้างจาก Shota ให้ช่วยเขาแก้ปัญหา เธอได้วัดกระแสจากทุก ๆ ปลั๊กในบ้านและสังเกตว่ามันแตกต่างกันทั้งหมด ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่ Shota จะสามารถชาร์ตอุปกรณ์ทั้งหมดของเขาในเวลาเดียวกันได้หรือไม่ ถ้าเป็นไปได้ ให้หาว่าจำนวนสวิชต์ที่ต้องสลับทั้งหมดที่น้อยที่สุดเป็นเท่าใด (เนื่องจาก Misaki ไม่อยากจะเหนื่อยกดสวิชต์มากเกินความจำเป็น) | ||
| − | === Full Binary Tree === | + | === B. Full Binary Tree === |
Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p1] | Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p1] | ||
| − | === Proper Shuffle === | + | === C. Proper Shuffle === |
Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2] | Source: [https://code.google.com/codejam/contest/2984486/dashboard#s=p2] | ||
รุ่นแก้ไขเมื่อ 10:45, 8 มีนาคม 2558
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]
C. Proper Shuffle
Source: [3]
