ผลต่างระหว่างรุ่นของ "Gcj2013/lawnmower"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 15: แถว 15:
 
บรรทัดแรกของข้อมูลนำเข้าระบุจำนวนข้อมูลทดสอบ '''T'''  หลักจากนั้นมีข้อมูลทดสอบ '''T''' ชุด
 
บรรทัดแรกของข้อมูลนำเข้าระบุจำนวนข้อมูลทดสอบ '''T'''  หลักจากนั้นมีข้อมูลทดสอบ '''T''' ชุด
  
ข้อมูลทดสอบแต่ละชุดจะเริ่มด้วยบรรทัดแรกระบุจำนวนเต็มสองจำนวน '''N''' และ '''M''' จากนั้นจะมีข้อมูลอีก '''N''' บรรรทัด  ข้อมูลบรรทัดที่ ''i'' ถัดจากนั้นระบุจำนวนเต็ม '''M''' จำนวน ''a<sub>i,1</sub>'' ถึง ''a<sub>i,M</sub>''  โดยที่ ''a<sub>i,j</sub>'' ระบุความสูงของหญ้าในช่องที่ ''j'' ในแถวที่ ''i''
+
ข้อมูลทดสอบแต่ละชุดจะเริ่มด้วยบรรทัดแรกระบุจำนวนเต็มสองจำนวน '''N''' และ '''M''' จากนั้นจะมีข้อมูลอีก '''N''' บรรรทัด  ข้อมูลบรรทัดที่ ''i'' ถัดจากนั้นระบุจำนวนเต็ม '''M''' จำนวน ''a<sub>i,1</sub>'' ถึง ''a<sub>i,M</sub>''  โดยที่ ''a<sub>j,i</sub>'' ระบุความสูงของหญ้าในช่องที่ ''j'' ในแถวที่ ''i''
  
 
== ข้อมูลส่งออก ==
 
== ข้อมูลส่งออก ==

รุ่นแก้ไขเมื่อ 05:21, 15 กรกฎาคม 2556

ต้นฉบับ (ทดลองส่งได้ที่เว็บต้นทาง): [1]

โจทย์

Alice และ Bob มีสนามหญ้าที่หน้าบ้านที่มีรูปร่างเป็นสี่เหลี่ยมขนาด N เมตร คูณ M เมตร ในแต่ละปี พวกเขาพยายามจะตัดหญ้าให้เป็นรูปแบบต่าง ๆ พวกเขาเคยใช้ที่ตัดหญ้าในการตัด แต่นั่นก็เป็นกิจกรรมที่เสียเวลามาก ตอนนี้พวกเขาเพิ่งได้เครื่องตัดหญ้าอัตโนมัติที่สามารถปรับค่าได้หลากหลาย ทำให้อยากจะลองเริ่มใช้เสียหน่อย

เครื่องตัดหญ้าใหม่นี้ สามารถปรับระดับความสูงในการตัดได้ โดยการปรับค่านั้นสามารถปรับค่าความสูง h ระหว่าง 1 ถึง 100 มิลลิเมตร เมื่อตั้งค่านี้แล้ว เครื่องจะตัดหญ้าที่มีความสูงมากกว่า h ให้เหลือความสูงเท่ากับ h    ในการตัดหญ้านั้นจะเริ่มตัดจากขอบด้านหนึ่ง จากนั้นเครื่องตัดหญ้าจะตัดหญ้าไปในทิศทางตรง ตั้งฉากกับขอบของสนามด้านที่เครื่องตัดหญ้าเริ่มเข้าไป โดยจะตัดเป็นแถบความกว้าง 1 เมตร พอดี จนกระทั่งเครื่องตัดไปทะลุขอบอีกด้านของสนาม    เครื่องตัดหญ้าสามารถปรับความสูงได้เฉพาะตอนที่ไม่ได้อยู่ในสนามเท่านั้น

Alice และ Bob มีรูปแบบของสนามที่พวกเขาอยากได้ ในแต่ละรูปแบบ พวกเขาต้องการทราบว่าเป็นไปได้หรือไม่ที่จะตัดหญ้าให้เป็นตามแบบนั้นด้วยเครื่องตัดหญ้าเครื่องใหม่นี้ แต่ละรูปแบบจะระบุด้วยความสูงของหญ้าในแต่ละช่องขนาด 1 เมตร x 1 เมตร

เมื่อเริ่มต้น หญ้าทั้งสนามมีความสูงเท่ากับ 100 มิลลิเมตร

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

บรรทัดแรกของข้อมูลนำเข้าระบุจำนวนข้อมูลทดสอบ T หลักจากนั้นมีข้อมูลทดสอบ T ชุด

ข้อมูลทดสอบแต่ละชุดจะเริ่มด้วยบรรทัดแรกระบุจำนวนเต็มสองจำนวน N และ M จากนั้นจะมีข้อมูลอีก N บรรรทัด ข้อมูลบรรทัดที่ i ถัดจากนั้นระบุจำนวนเต็ม M จำนวน ai,1 ถึง ai,M โดยที่ aj,i ระบุความสูงของหญ้าในช่องที่ j ในแถวที่ i

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

ขอบเขต

ข้อมูลทดสอบเล็ก

ข้อมูลทดสอบใหญ่

ตัวอย่าง

input

3
3 3
2 1 2
1 1 1
2 1 2
5 5
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
1 3
1 2 1

output

Case #1: YES
Case #2: NO
Case #3: YES