ผลต่างระหว่างรุ่นของ "Gcj2013/lawnmower"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 5 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 3: | แถว 3: | ||
== โจทย์ == | == โจทย์ == | ||
| − | Alice และ Bob มีสนามหญ้าที่หน้าบ้านที่มีรูปร่างเป็นสี่เหลี่ยมขนาด N เมตร คูณ M เมตร ในแต่ละปี พวกเขาพยายามจะตัดหญ้าให้เป็นรูปแบบต่าง ๆ พวกเขาเคยใช้ที่ตัดหญ้าในการตัด แต่นั่นก็เป็นกิจกรรมที่เสียเวลามาก ตอนนี้พวกเขาเพิ่งได้เครื่องตัดหญ้าอัตโนมัติที่สามารถปรับค่าได้หลากหลาย ทำให้อยากจะลองเริ่มใช้เสียหน่อย | + | Alice และ Bob มีสนามหญ้าที่หน้าบ้านที่มีรูปร่างเป็นสี่เหลี่ยมขนาด '''N''' เมตร คูณ '''M''' เมตร ในแต่ละปี พวกเขาพยายามจะตัดหญ้าให้เป็นรูปแบบต่าง ๆ พวกเขาเคยใช้ที่ตัดหญ้าในการตัด แต่นั่นก็เป็นกิจกรรมที่เสียเวลามาก ตอนนี้พวกเขาเพิ่งได้เครื่องตัดหญ้าอัตโนมัติที่สามารถปรับค่าได้หลากหลาย ทำให้อยากจะลองเริ่มใช้เสียหน่อย |
เครื่องตัดหญ้าใหม่นี้ สามารถปรับระดับความสูงในการตัดได้ โดยการปรับค่านั้นสามารถปรับค่าความสูง '''h''' ระหว่าง 1 ถึง 100 มิลลิเมตร เมื่อตั้งค่านี้แล้ว เครื่องจะตัดหญ้าที่มีความสูงมากกว่า '''h''' ให้เหลือความสูงเท่ากับ '''h''' ในการตัดหญ้านั้นจะเริ่มตัดจากขอบด้านหนึ่ง จากนั้นเครื่องตัดหญ้าจะตัดหญ้าไปในทิศทางตรง ตั้งฉากกับขอบของสนามด้านที่เครื่องตัดหญ้าเริ่มเข้าไป โดยจะตัดเป็นแถบความกว้าง 1 เมตร พอดี จนกระทั่งเครื่องตัดไปทะลุขอบอีกด้านของสนาม เครื่องตัดหญ้าสามารถปรับความสูงได้เฉพาะตอนที่ไม่ได้อยู่ในสนามเท่านั้น | เครื่องตัดหญ้าใหม่นี้ สามารถปรับระดับความสูงในการตัดได้ โดยการปรับค่านั้นสามารถปรับค่าความสูง '''h''' ระหว่าง 1 ถึง 100 มิลลิเมตร เมื่อตั้งค่านี้แล้ว เครื่องจะตัดหญ้าที่มีความสูงมากกว่า '''h''' ให้เหลือความสูงเท่ากับ '''h''' ในการตัดหญ้านั้นจะเริ่มตัดจากขอบด้านหนึ่ง จากนั้นเครื่องตัดหญ้าจะตัดหญ้าไปในทิศทางตรง ตั้งฉากกับขอบของสนามด้านที่เครื่องตัดหญ้าเริ่มเข้าไป โดยจะตัดเป็นแถบความกว้าง 1 เมตร พอดี จนกระทั่งเครื่องตัดไปทะลุขอบอีกด้านของสนาม เครื่องตัดหญ้าสามารถปรับความสูงได้เฉพาะตอนที่ไม่ได้อยู่ในสนามเท่านั้น | ||
| แถว 10: | แถว 10: | ||
เมื่อเริ่มต้น หญ้าทั้งสนามมีความสูงเท่ากับ 100 มิลลิเมตร | เมื่อเริ่มต้น หญ้าทั้งสนามมีความสูงเท่ากับ 100 มิลลิเมตร | ||
| + | |||
| + | == ข้อมูลนำเข้า == | ||
| + | |||
| + | บรรทัดแรกของข้อมูลนำเข้าระบุจำนวนข้อมูลทดสอบ '''T''' หลักจากนั้นมีข้อมูลทดสอบ '''T''' ชุด | ||
| + | |||
| + | ข้อมูลทดสอบแต่ละชุดจะเริ่มด้วยบรรทัดแรกระบุจำนวนเต็มสองจำนวน '''N''' และ '''M''' จากนั้นจะมีข้อมูลอีก '''N''' บรรรทัด ข้อมูลบรรทัดที่ ''i'' ถัดจากนั้นระบุจำนวนเต็ม '''M''' จำนวน ''a<sub>i,1</sub>'' ถึง ''a<sub>i,M</sub>'' โดยที่ ''a<sub>i,j</sub>'' ระบุความสูงของหญ้าในช่องที่ ''j'' ในแถวที่ ''i'' | ||
| + | |||
| + | == ข้อมูลส่งออก == | ||
| + | |||
| + | สำหรับแต่ละข้อมูลทดสอบ ให้พิมพ์บรรทัดในรูปแบบ <tt>Case #x: y</tt> โดยที่ ''x'' แทนหมายเลขชุดทดสอบ และ ''y'' เป็นคำว่า <tt>YES</tt> ถ้าสามารถสร้างรูปแบบที่ ''x'' ได้โดยใช้เครื่องตัดหญ้า หรือ <tt>NO</tt> ถ้าไม่สามารถทำได้ | ||
| + | |||
| + | == ขอบเขต == | ||
| + | |||
| + | * 1 <= '''T''' <= 100 | ||
| + | |||
| + | == ข้อมูลทดสอบเล็ก == | ||
| + | |||
| + | * 1 <= '''N''', '''M''' <= 10 | ||
| + | * 1 <= ''a<sub>i,j</sub>'' <= 2 | ||
| + | |||
| + | == ข้อมูลทดสอบใหญ่ == | ||
| + | |||
| + | * 1 <= '''N''', '''M''' <= 100 | ||
| + | * 1 <= ''a<sub>i,j</sub>'' <= 100 | ||
| + | |||
| + | == ตัวอย่าง == | ||
| + | |||
| + | === input === | ||
| + | <pre> | ||
| + | 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 | ||
| + | </pre> | ||
| + | |||
| + | === output === | ||
| + | <pre> | ||
| + | Case #1: YES | ||
| + | Case #2: NO | ||
| + | Case #3: YES | ||
| + | </pre> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 05:24, 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 โดยที่ ai,j ระบุความสูงของหญ้าในช่องที่ j ในแถวที่ i
ข้อมูลส่งออก
สำหรับแต่ละข้อมูลทดสอบ ให้พิมพ์บรรทัดในรูปแบบ Case #x: y โดยที่ x แทนหมายเลขชุดทดสอบ และ y เป็นคำว่า YES ถ้าสามารถสร้างรูปแบบที่ x ได้โดยใช้เครื่องตัดหญ้า หรือ NO ถ้าไม่สามารถทำได้
ขอบเขต
- 1 <= T <= 100
ข้อมูลทดสอบเล็ก
- 1 <= N, M <= 10
- 1 <= ai,j <= 2
ข้อมูลทดสอบใหญ่
- 1 <= N, M <= 100
- 1 <= ai,j <= 100
ตัวอย่าง
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
