สมมติว่าเราได้สี่เหลี่ยมจัตุรัสที่มีขนาด n สี่เหลี่ยมจัตุรัสขนาด n ถูกแบ่งออกเป็นอีก n2 สี่เหลี่ยมจัตุรัสที่เล็กกว่า สี่เหลี่ยมจัตุรัสที่เล็กกว่านั้นมีขนาดเท่ากับหน่วย และหนึ่งในสี่เหลี่ยมนั้นถูกระบายสีด้วยสีที่เป็นเอกลักษณ์
ทีนี้ ถ้าเราตัดสี่เหลี่ยมที่ใหญ่กว่าออกเป็นสองส่วนเท่า ๆ กัน เราต้องตัดมันในลักษณะที่เส้นตัดจะไม่มีจุดเหมือนกันกับสี่เหลี่ยมเล็ก ๆ ที่มีสีเฉพาะตัวนั้น เราต้องพิจารณาด้วยว่าชิ้นส่วนสองชิ้นที่เพิ่งตัดใหม่เป็นภาพสะท้อนของกันและกัน ดังนั้น เราต้องค้นหาว่าการตัดสี่เหลี่ยมจัตุรัสแบบนั้นเป็นไปได้หรือไม่โดยพิจารณาจากเงื่อนไข เรามีค่า n และตำแหน่งของสี่เหลี่ยมสีในสี่เหลี่ยมที่ใหญ่กว่า
ดังนั้น หากอินพุตเท่ากับขนาด =50, colored_row_pos =25, colored_col_pos =25 ผลลัพธ์จะเป็น "ไม่สามารถตัดได้"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กลาง :=ค่าพื้นของขนาด /2
- ถ้า (ตรงกลางเหมือนกับ colored_row_pos หรือ mid เหมือนกับ colored_row_pos - 1) และ (ตรงกลางเหมือนกับ colored_col_pos หรือ mid เหมือนกับ colored_col_pos - 1) แล้ว
- คืนค่าเท็จ
- มิฉะนั้น
- คืนค่า True
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(size, colored_row_pos, colored_col_pos) :
middle = size // 2
if (middle == colored_row_pos or middle == colored_row_pos - 1) and (middle == colored_col_pos or middle == colored_col_pos - 1) :
print("Cutting is not possible")
else :
print("Cutting is possible")
size = 50
colored_row_pos, colored_col_pos = 25, 25
solve(size, colored_row_pos, colored_col_pos) อินพุต
50, 25, 25
ผลลัพธ์
Cutting is not possible
