ผลต่างระหว่างรุ่นของ "Gcj2014"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 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]