D1. Суперколлайдер

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

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

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

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

Энэ бодлого нь хоёр дэд бодлогоос бүрдэнэ: дэд бодлого D1-ийг бодсоноор та 3 оноо авна, харин D2 дэд бодлогыг бодсоноор та 16 оноо авна.

Манао бол шинэ супер коллиайдер төлөвлөхөд оролцсон ахлах архитектор. Тэр боломжит хамгийн том супер коллайдерийг барьж болохуйц газрыг тодорхойлох хэрэгтэй байна. Түүний барьж буй супер коллайдер нь ижил хурдаар хөдлөх дөрвөн жижиг хэсгүүдийн тэгш өнцөг үүсгэн дөрвөн зүгт огтлолцох огтлолцлыг шаардана, мөн хурдасгуур бүхий дөрвөн хэсгээс бүрдэх ба нэмэх тэмдэг шиг хэлбэртэй байна (өөрөөр +). Хурдсаж буй дөрвөн жижиг хэсэг бүр ижил урттай байх ёстой ба интерференцийг багасгахын тулд дэлхийн соронзон оронтой зэрэгцэн байрлах ёстой.

Хурдсаж буй жижиг хэсгүүд нь зардлыг удирдахын тулд газрын нарийн хавтгай хэсгүүдийн дагуу байх ёстой. Түүнчлэн Манао хурдсаж буй жижиг хэсгүүдийг дэлхийн соронзон оронтой паралель эсвэл тэгш өнцөгт үүсгэн барьж болохуйц боломжит хамгийн урт хэсэг газруудыг тодорхойлох байрзүйн судалгааг хийх болсон. Боломжит хамгийн том супер коллайдерийг барихын тулд Манао эдгээр хэсгүүдээс хамгийн том тэгш хэмт нэмэх тэмдэг бүхий дүрсийг тодорхойлох ёстой. Энэ нь Манао нэмэх тэмдгийн төвөөс дөрвөн гарны хамгийн богиных нь үзүүр хүртэлх хамгийн их зайтай мөн тэнхлэгтэй зэрэгцсэн нэмэх тэмдэг үүсгэх газрын хоёр урт хэсэг олох хэрэгтэй гэсэн үг юм. Коллайдер тодорхойлсон хэсгүүдийн уртыг бүхлээр нь ашиглах шаардлагагүй (тэмдэглэл дээрх жишээнүүдийг харна уу).

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ буюу хойд-урд урт хэсгүүдийн тоо ба $m$ буюу баруун-зүүн урт хэсгүүдийн тоо.

Дараагийн $n$ мөр бүрт эхлээд хойд-урд нэг урт хэсгийг тодорхойлно. Ийм урт хэсэг бүр зайгаар тусгаарлагдсан $x_{i}, y_{i}, l_{i}$ гурван бүхэл тоогоор тодорхойлогдох ба босоо шулуун дээрх $(x_{i}, y_{i})$-с $(x_{i}, y_{i} + l_{i})$ хүртэлх хэсэг газрыг илэрхийлнэ.

Үүнтэй адилаар хойд-урд урт хэсгүүдийг тодорхойлсон $n$ мөрийн дараа баруун-зүүн урт хэсгүүдийг тодорхойлсон төсөөтэй $m$ мөр байна. Ийм хэсэг бүр зайгаар тусгаарлагдсан $x_{i}, y_{i}, l_{i}$ гурван бүхэл тоогоор тодорхойлогдох ба $(x_{i}, y_{i})$-с $(x_{i} + l_{i}, y_{i})$ хөндлөн шугам бүхий хэсэг газрыг илэрхийлнэ.

Бүх $x_{i}$ ба $y_{i}$ нь -100000000-с 100000000-н хооронд байна (захын тоонуудыг оролцуулаад). Бүх $l_{i}$ нь 1-с 100000000-н хооронд байна (захын тоонуудыг оролцуулаад). Ямар ч хос хөндлөн хэсгүүд хоорондоо огтлолцохгүй мөн давхардахгүй ба ямар ч хос босоо хэсгүүд огтлолцохгүй мөн давхардахгүй.

Бодлого маань хоёр дэд бодлогоос бүрдэнэ. Дэд бодлогууд оролтондоо ялгаатай хязгаарлалтуудтай. Та дэд бодлогын зөв бодолтыг илгээснээр оноо авах болно. Дэд бодлогуудын тайлбарыг доор үзүүлэв.

  • D1 (3 оноо) дэд бодлогод $n$ ба $m$ нь $1$-с $1000$-н хооронд байна, захын тоонуудыг оролцуулаад.
  • D2 (16 оноо) дэд бодлогод $n$ ба $m$ нь $1$-с $50000$-н хооронд байна, захын тоонуудыг оролцуулаад.

Гаралт

Нэг хойд-урд урт хэсэг болон нэг баруун-зүүн урт хэсэг дээр байгуулж чадах хамгийн том супер коллайдерийн хэмжээг илэрхийлэх бүхэл тоог нэг мөрөнд хэвлэ. Супер коллайдерийн хэмжээ нь хурдсаж буй дөрвөн жижиг хэсгийн нэгнийх нь уртаар тодорхойлогдоно. Өөрөөр хэлбэл үүсч буй супер коллайдерийн хэмжээ нь хоёр шулуун хэсгийн огтлолцлоос уг хоёр хэсгийн аль нэгнийх нь хамгийн ойр төгсгөлийн цэг хүртэлх зайгаар тодорхойлогдоно. Хэрвээ хойд-урд болон баруун-зүүн хоорондоо огтлолцох хоёр урт хэсэг байхгүй бол супер коллайдерийг барих боломжгүй ба програм хамгийн их хэмжээг тэг гэж гаргах ёстой.

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

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

Оролт
1 2
4 0 9
1 1 8
1 2 7
Гаралт
2

Тэмдэглэл

Жишээг авч үзье. (4, 0)-с (4, 9) хүртэл нэг босоо шулуун хэсэг байна, мөн (1, 1)-с (9, 1) хүртэл, (1, 2)-с (8, 2) хүртэл хоёр хэвтээ шулуун байна. Эдгээр хэсгүүдээс үүсгэж болох хамгийн том нэмэх дүрс нь босоо шулуун болон хоёр дахь хэвтээ шулуунаар үүсгэх ба (4, 2) дээр төвтэй байна.

Эдгээр хэсгүүдийн хамгийн ойрхон төгсгөлийн цэг нь төв цэг (4, 2) цэгээс 2 зайтай (4, 0) цэг юм. Иймээс програм 2 гэсэн хариу гаргах ёстой. Коллайдер маань (2, 2)-с (6, 2) хүртэл мөн (4, 0)-с (4, 4) хүртэл хэсгүүдээс бүтнэ.

Сэтгэгдлүүдийг ачааллаж байна...