1096 : SLIKAR
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

Josip เป็นจิตรกรที่มีนิสัยแปลก ๆ   เขาต้องการที่จะระบายสีลงบนรูปภาพที่มีขนาด N x N พิกเซล โดยที่ N สามารถเขียนให้อยู่ในรูปของสองยกกำลังตัวเลขใดๆ (1, 2, 4, 8, 16 และอื่น ๆ)    ในแต่ละพิกเซลจะต้องเป็นสีขาวหรือดำเท่านั้นและ Josip ก็มีแนวทางในการระบายสีลงในแต่ละพิกเซลแล้วด้วย
การระบายสีนี้ของ Josip ไม่น่าที่จะมีปัญหาอะไร ถ้าเขาไม่ระบายสีด้วยวิธีการแปลก ๆ โดยเขาได้ใช้วิธีการระบายสีแบบเรียกซ้ำ ดังนี้ 

  • ถ้ารูปภาพมีขนาด pixel เดียว  เขาจะระบายสีลงไปบนภาพนั้นตามแนวทางที่เขาตั้งใจ
  • ถ้าไม่เช่นนั้น   เขาจะแบ่งรูปภาพออกเป็นรูปสี่เหลี่ยมขนาดเล็ก 4 รูป แล้วทำดังนี้
    1. เลือกรูปเหลี่ยมขนาดเล็กจาก 1 ใน 4 รูปแล้วระบายสีขาวลงไป
    2. เลือกรูปสี่เหลี่ยมขนาดเล็กจาก 1 ใน 3 ของรูปที่เหลือ แล้วระบายสีดำลงไป
    3. จากนั้น เขาจะพิจารณารูปสี่เหลี่ยมขนาดเล็ก 2 รูปที่เหลือเสมือนว่าเป็นการระบายสีครั้งใหม่ และใช้วิธีการ 3 ขั้นตอนนี้กับรูปเหล่านั้น

เมื่อเร็ว ๆ นี้ เขาสังเกตพบว่า  มันเป็นไปไม่ได้ที่จะเปลี่ยนการมองเห็นภาพของเขามาเป็นการระบายสีด้วยวิธีการนี้ได้

งานของคุณ

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

ข้อมูลนำเข้า

ในบรรทัดแรกประกอบด้วยเลขจำนวนเต็ม N (1 ≤ N ≤ 512) ซึ่งเป็นขนาดของรูปที่ Josip ต้องการจะระบายสีลงไป และ N สามารถเขียนให้อยู่ในรูปของสองยกกำลังตัวเลขใดๆ
ในแต่ละ N บรรทัดที่เหลือ จะประกอบด้วย เลขจำนวนเต็ม 0 หรือ 1 จำนวน N ตัวซึ่งหมายถึงสี่เหลี่ยมสีขาวและดำในรูปเป้าหมาย

ข้อมูลส่งออก

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

การให้คะแนน

ที่มา: COCI 2008/2009, Contest #4 – January 17, 2009 :: ดัดแปลงเล็กน้อย (:


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4
0001
0001
0011
1110
1
4
1111
1111
1111
1111
6
8
01010001
10100011
01010111
10101111
01010111
10100011
01010001
10100000
16

ความช่วยเหลือ: Hint[1]  Hint[2]  Hint[3]  

กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 9 สมาชิก (0 บอท)