Gcj2009

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 02:20, 17 พฤษภาคม 2556 โดย Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== Round 2 == === A. Crazy Rows === Source: [https://code.google.com/codejam/contest/204113/dashboard#s=p0] คุณได้รั...')
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

Round 2

A. Crazy Rows

Source: [1]

คุณได้รับเมตริกซ์ขนาด N x N ที่มีค่า 0 กับ 1 คุณสามารถสลับสองแถวที่ติดกันในเมตริกซ์ได้

เป้าหมายของคุณคือการสลับให้ค่า 1 ทั้งหมดอยู่บนหรือล่างแนวทแยงมุมหลัก นั่นคือ สำหรับ X ที่ 1 <= X <= N, จะต้องไม่มี 1 ในแถวที่ X ที่อยู่ด้านขวาของคอลัมน์ X

ให้โปรแกรมพิมพ์จำนวนครั้งของการสลับที่น้อยที่สุดที่ต้องใช้

Input

  • บรรทัดแรกระบุจำนวนเต็ม T, จากนั้นจะมีข้อมูลทดสอบ T ชุดหลังจากนั้น
  • บรรทัดแรกของแต่ละชุดข้อมูลทดสอบระบุจำนวนเต็ม N จากนั้นอีก N บรรทัด ในแต่ละบรรทัดจะมีอักขระ N ตัว ซึ่งมีค่าเป็น 0 หรือ 1

Output

สำหรับแต่ละข้อมูลทดสอบ พิมพ์

Case #X: K

เมื่อ X แทนหมายเลขข้อมูลทดสอบ และ K เป็นจำนวนครั้งที่ต้องสลับที่น้อยที่สุด

รับประกันว่ามีคำตอบในทุก ๆ ข้อมูลทดสอบ