1076 : โกหก (lieman)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 128 megabyte(s)

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

                รู้สึกตัวอีกที คุณก็กำลังอยู่ในเว็บบอร์ดใต้ดินที่รวบรวมนักเลงคอมพิวเตอร์มือฉมังเอาไว้เสียมากมาย เป้าหมายของคุณคือการเสาะหาวิธีการบุกเจาะเข้าไปยังฐานข้อมูลของ TOI.C หลังจากปฏิบัติการล้มเหลวมาแล้วถึงสองหน ถึงเวลาที่จะต้องพึ่งคนอื่นแล้ว

                คุณได้ตัดสินใจตั้งกระทู้ถามคำถามใช่-ไม่ใช่ เกี่ยวกับระบบการรักษาความปลอดภัยของ TOI.C เป็นจำนวนมากถึง M คำถาม เหล่านักเลงคอมพิวเตอร์ผู้สิงสถิตในบอร์ดต่างตื่นตาตื่นใจกับคำถาม และได้ตอบคำถามของคุณอย่างจริงจัง เป็นจำนวน N คน (ไม่นับคนที่ป่วนกระทู้ ปั่นกระทู้ ดันกระทู้ กวนกระทู้ และดองกระทู้) โดยคนที่มาตอบคำถามอาจไม่ตอบทุกคำถามของคุณก็ได้ แต่แล้วคุณก็ต้องตกใจ เพราะคำตอบที่ได้มานั้น มีทั้งคำตอบที่ถูกต้องและคำโกหก คุณลืมไปเสียสนิทว่านักเลงคอมพิวเตอร์เหล่านี้มักจะลองเชิงสมาชิกหน้าใหม่ด้วยการโกหกคำตอบในบางข้อ

                แต่ถึงอย่างนั้น คุณได้ตัดสินใจวิเคราะห์คำตอบของแต่ละคน แต่ถึงจะวิเคราะห์ยังไง คุณก็ไม่สามารถวิเคราะห์ได้ด้วยมือซักที เพราะคุณไม่ใช่นักเศรษฐศาสตร์ หรือนักจิตวิทยา แต่คุณคือโปรแกรมเมอร์ ฉะนั้น หน้าที่ของคุณคือ เขียนโปรแกรมเพื่อวิเคราะห์ว่า ถ้าคนจำนวนมากที่สุดที่เป็นไปได้ตอบคำถามเป็นความจริงแล้ว แล้วจะมีคนโกหกทั้งหมดกี่คน

งานของคุณ

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

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

บรรทัดแรก มีจำนวนเต็ม N (1 ≤ N ≤ 20), M (1 M 20) แทนจำนวนคนตอบกระทู้ และจำนวนคำถาม ตามลำดับ

อีก N บรรทัดถัดไป จะมีจำนวนเต็มบรรทัดละ M ตัว แทนข้อมูลการตอบคำถามของนักเลงคอมพิวเตอร์แต่ละคนในแต่ละคำถาม โดยจำนวนเต็มตัวที่ j ของบรรทัดที่ i + 1 จะระบุคำตอบของนักเลงคอมพิวเตอร์หมายเลข i ต่อคำถามที่ j ซึ่งจำนวนเต็มดังกล่าวแปลความหมายดังนี้

  • 1 แทนคำตอบว่า ใช่
  • -1 แทนคำตอบว่า ไม่ใช่
  • 0 แทน ไม่ตอบกระทู้

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

บรรทัดเดียว พิมพ์จำนวนคนที่โกหก เมื่อคนจำนวนมากที่สุดที่เป็นไปได้ไม่ได้โกหก

อธิบายตัวอย่างข้อมูลนำเข้าและส่งออก

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

 

โจทย์โดย: ภัทร สุขประเสริฐ

ที่มา: TOI.C:01-2009


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 3
0 1 0
-1 -1 1
1 1 1
1

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

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