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 ใน 4 รูปแล้วระบายสีขาวลงไป
- เลือกรูปสี่เหลี่ยมขนาดเล็กจาก 1 ใน 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]