D. Биатлоны зам

хугацааны хязгаарлалт 4.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Саяхан Олимпийн хорооноос гаргасан албан ёсны мэдэгдэлд 2030 оны Өвлийн Олимп Томскд зохион байгуулагдахыг зарласан. Хотын албаны хүмүүс Олимпод нарийн бэлдэхээр шийдсэн ба шаардлагатай бүх Олимпийн байгууламжуудыг боломжит хамгийн эрт барихаар шийдсэн. Эхлээд биатлоны замыг барина.

Биатлоны замыг барихын тулд хэсэг газрыг нөөцлөсөн ба энэ газар нь $n × m$ ижилхэн квадратуудад хуваагдсан тэгш өнцөгт юм. Квадрат бүр хоёр координаттай: байрласан мөрийн дугаар (1-c $n$ хүртэл), байрласан баганын дугаар (1-c $m$ хүртэл) байна. Мөн квадрат бүр өөрийн өндрөөрөө тодорхойлогдоно. Тэмцээний үеэр биатлончид нэг квадратаас нөгөө квадратруу явах хэрэгтэй. Хэрвээ байтлонч өндөр квадратаас намхан квадратруу буух бол тэр буулт хийнэ. Хэрвээ биатлонч намхан квадратаас өндөр квадратруу явах бол өгсөлт хийнэ. Хэрвээ биатлонч ижил өндөрт байгаа хоёр квадратын хооронд гулгахаар болвол тэгш газар дээгүүр явна.

Биатлоны зам нь биатлончид цагийн зүүний дагуу гулгах газраас нөөцлөсөн тэгш өнцөгт хэсгийн хүрээ байх ёстой. Тэгш газар дээрх нэг хөдөлгөөнд дундаж биатлонч $t_{p}$ секунд зарцуулдаг бол өгсөлт хийхэд $t_{u}$ секунд харин буулт хийхэд $t_{d}$ секунд зарцуулна. Томскийн удирдлагууд дундаж биатлонч $t$ секундтэй аль болох ойр туулахаар замыг сонгохыг хүсч байна. Өөрөөр хэлбэл сонгосон замыг туулах $t_{s}$ хугацаа болон $t$-н хоорондох зөрүү хамгийн бага байхаар.

Илүү сайн ойлгохын тулд та оролтын өгөгдлийн эхний жишээг харна уу. Энэ жишээнд $n = 6, m = 7$ ба удирдлагууд замыг туулах хугацааг $t = 48$ секундтэй аль болох ойрхон байлгахыг хүссэн, мөн $t_{p} = 3$, $t_{u} = 6$ ба $t_{d} = 2$ байна. Хэрвээ бид зурагт сумаар дүрсэлсэн тэгш өнцөгтийг авч үзвэл дундаж биатлонч энэ тэгш өнцөгтийн хүрээг цагийн зүүний дагуу яг $48$ секундэд туулна. Энэ замын зүүн дээд булан нь $4$ дугаартай мөр болон $3$ дугаартай баганад байрласан квадратад байрласан ба баруун доод булан нь $6$ дугаартай мөр болон $7$ дугаартай баганад байрласан квадратад байрласан байна.

Бусад зүйлсийн хувьд удирдлага хүрээ нь биатлоны зам болох тэгш өнцөгтийг гурваас багагүй квадратаас бүтсэн мөн сонгосон газарт бүрэн багтсан байгаасай гэж хүсч байна.

Танд хэсэг газрын тайлбар, мөн бүх шаардлагатай цагийн утгууд өгөгдсөн. Та биатлоны замд хамгийн сайн тохирох тэгш өнцөгтийг олох програм бичих хэрэгтэй. Хэрвээ ийм хэд хэдэн тэгш өнцөгт байвал та алийг нь ч хэвлэж болно.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоо $n$, $m$ ба $t$ ($3 ≤ n, m ≤ 300$, $1 ≤ t ≤ 10^{9}$) байх буюу хэсэг газрын хэмжээ ба шаардлагатай туулах хугацаа юм.

Хоёрдугаар мөрөнд ч мөн адил гурван бүхэл тоо $t_{p}$, $t_{u}$ ба $t_{d}$ ($1 ≤ t_{p}, t_{u}, t_{d} ≤ 100$) байх ба харгалзан дундаж биатлонч замын нэг хавтгай хэсгийг туулах хугацаа, өгсөлт болон буулт хийх хугацаа байна.

Тэгээд $n$ мөр байх ба мөр бүрт $m$ бүхэл тоо байх буюу өгөгдсөн хэсэг газрын квадрат бүрийн өндөр байна. Өндрийн утга бүр $10^{6}$-с хэтрэхгүй эерэг бүхэл тоо байна.

Гаралт

Гаралтын нэг мөрөнд дөрвөн эерэг бүхэл тоо хэвлэх буюу замд зориулж сонгосон тэгш өнцөгтийн зүүн дээд булангийн мөр болон баганын дугаар ба баруун доод булангийн мөр ба баганын дугаар байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
6 7 48
3 6 2
5 4 8 3 3 7 9
4 1 6 8 7 1 1
1 6 4 6 4 8 6
7 2 6 1 6 9 4
1 9 8 6 3 9 2
4 5 6 8 4 3 7
Гаралт
4 3 6 7
Сэтгэгдлүүдийг ачааллаж байна...