0037 : บินดูไฟ (skylight)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ในวันปีใหม่ สนามกีฬาแห่งหนึ่งได้ประดับไฟที่พื้นสนามฟุตบอลเพื่อความสวยงาม ในการประดับไฟนั้นทำโดยแบ่งสนามสี่เหลี่ยมเป็นช่องย่อยๆ จำนวน N แถว แถวละ M คอลัมน์ รวม N×M ช่อง เจ้าของสนามได้เปิดสนามให้ประชาชนทั่วไปเข้าชมเพื่อความสวยงาม
อย่างไรก็ตาม โลกนี้ไม่มีอะไรฟรี เจ้าของสนามจะต้องจ่ายค่าไฟให้กับไฟประดับเหล่านี้ เนื่องจากมีการประดับไฟเป็นลวดลายต่างๆ ค่าไฟของไฟแต่ละช่องไม่จำเป็นต้องเท่ากัน
เพื่อไม่ให้เป็นการขาดทุน เจ้าของสนามจึงได้จัดเครื่องไอพ่นเจ็ตส่วนบุคคลให้กับประชาชนเช่าเพื่อบินดูไฟประดับ เครื่องพ่นเจ็ตแต่ละเครื่องเมื่อเช่าไปแล้วจะผู้ใช้จะสามารถบินได้ทั้งสิ้น K ครั้ง ในการบินแต่ละครั้งจะใช้เชื้อเพลิงมูลค่าเท่ากับ L บาท ดังนั้น ค่าใช้จ่ายรวมทั้งหมดของเจ้าของสนามคือค่าไฟรวมของไฟประดับ และค่าเชื้อเพลิงรวมของการบินเครื่องไอพ่นเจ็ตในการบินทั้งหมด
เจ้าของสนามทราบว่าจะมีคนมาชมและเช่าเครื่องไอพ่นเจ็ตจำนวน C คน เขาต้องการคำนวณค่าเช่าเครื่องไอพ่นเจ็ตต่อคนที่น้อยที่สุด ที่จะทำให้เขาไม่ขาดทุน เพื่อให้การเช่าเป็นไปได้สะดวก ค่าเช่าจะต้องเป็นจำนวนเต็มเสมอด้วย
งานของคุณ
อย่างไรก็ตาม โลกนี้ไม่มีอะไรฟรี เจ้าของสนามจะต้องจ่ายค่าไฟให้กับไฟประดับเหล่านี้ เนื่องจากมีการประดับไฟเป็นลวดลายต่างๆ ค่าไฟของไฟแต่ละช่องไม่จำเป็นต้องเท่ากัน
เพื่อไม่ให้เป็นการขาดทุน เจ้าของสนามจึงได้จัดเครื่องไอพ่นเจ็ตส่วนบุคคลให้กับประชาชนเช่าเพื่อบินดูไฟประดับ เครื่องพ่นเจ็ตแต่ละเครื่องเมื่อเช่าไปแล้วจะผู้ใช้จะสามารถบินได้ทั้งสิ้น K ครั้ง ในการบินแต่ละครั้งจะใช้เชื้อเพลิงมูลค่าเท่ากับ L บาท ดังนั้น ค่าใช้จ่ายรวมทั้งหมดของเจ้าของสนามคือค่าไฟรวมของไฟประดับ และค่าเชื้อเพลิงรวมของการบินเครื่องไอพ่นเจ็ตในการบินทั้งหมด
เจ้าของสนามทราบว่าจะมีคนมาชมและเช่าเครื่องไอพ่นเจ็ตจำนวน C คน เขาต้องการคำนวณค่าเช่าเครื่องไอพ่นเจ็ตต่อคนที่น้อยที่สุด ที่จะทำให้เขาไม่ขาดทุน เพื่อให้การเช่าเป็นไปได้สะดวก ค่าเช่าจะต้องเป็นจำนวนเต็มเสมอด้วย
งานของคุณ
เขียนโปรแกรมรับราคาค่าไฟของสนามแต่ละช่อง รวมทั้งข้อมูลของการใช้เครื่องไอพ่นเจ็ต จากนั้นคำนวณหาค่าเช่าเครื่องไอพ่นเจ็ตต่อคนที่เป็นจำนวนเต็มที่น้อยที่สุด ที่จะทำให้เจ้าของสนามไม่ขาดทุน
ข้อมูลนำเข้า
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็มบวก N และ M คั่นด้วยช่องว่าง แทนขนาดความกว้างและความยาวของสนาม (1 ≤ N ≤ 100; 1 ≤ M ≤ 100)
บรรทัดที่สองระบุจำนวนเต็มบวก L และ K คั่นด้วยช่องว่าง โดยที่ L แทนราคาเชื้อเพลิงต่อการบินหนึ่งครั้งและ K แทนจำนวนครั้งที่เครื่องไอพ่นใช้บินได้ต่อคนเช่าหนึ่งคน (1 ≤ L ≤ 100; 1 ≤ K ≤ 100)
บรรทัดที่สามระบุจำนวนเต็มบวก C แทนจำนวนผู้เล่นทั้งหมดที่เข้ามาเล่น (1 ≤ C < 1,000)
บรรทัดถัดไปอีก N บรรทัด แต่ละบรรทัดรับจำนวนเต็มบวก M ตัว แต่ละตัวถูกคั่นด้วยช่องว่าง แทนค่าไฟในแต่ละช่องที่ประดับไฟ ซึ่งจะเป็นจำนวนเต็มบวกที่มีค่าไม่เกิน 3,000
ข้อมูลส่งออก
มีบรรทัดเดียวเป็นจำนวนเต็มบวกหนึ่งจำนวน แทนค่าเช่าเครื่องไอพ่นเจ็ตต่อคนที่เป็นจำนวนเต็มที่น้อยที่สุด ที่จะทำให้เจ้าของสนามไม่ขาดทุน
ที่มา
การแข่งขัน IOI Thailand League เดือนกันยายน 2553
โจทย์โดย: ธงชัย วิโรจน์ศักดิ์เสรี
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 3 3 2 1 1 1 1 1 1 1 1 1 1 1 | 11 |
| 3 4 3 2 7 1 2 3 4 4 3 2 1 1 1 1 1 | 10 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 28 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)