B. Баавгай ба Кубуудын цамхаг

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

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

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

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

Лимак бол бяцхан туйлын баавгай юм. Тэрээр блокуудаар цамхаг барин тоглож байв. Блок бүр нь эерэг бүхэл тоон талтай куб байх бөгөөд Лимак-д тал бүрийн урттай хязгааргүй олон тооны блокууд байжээ.

$a$ талтай блок нь $a^{3}$ эзлэхүүнтэй байх бөгөөд $a_{1}, a_{2}, ..., a_{k}$ талуудтай блокуудаас тогтох цамхгийн нийт эзлэхүүн нь $a_{1}^{3} + a_{2}^{3} + ... + a_{k}^{3}$ байх ажээ.

Лимак одоо цамхаг барихаар болов. Эхлээд тэрээр танаас цамхгийн нийт эзлэхүүний шаардлагатай утга болох эерэг бүхэл тоо $X$-ыг хэлж өгөхийг хүсжээ. Дараа нь Лимак шинэ блокуудыг нэг нэгээр нь байрлуулах юм. Ингэж байрлуулах болгондоо тэрээр нийт цамхгийн эзлэхүүн нь $X$-ээс хэтрэхгүй байхаар хамгийн том блокыг нэмж байрлуулах ажээ.

Лимак танаас $m$-ээс хэтрэхгүй байх $X$-ыг сонгож өгөхийг хүсэв. Мөн тэрээр цамхгийг барьж дууссаны дараа цамхаг дахь нийт блокны тоо нь хамгийн их байхыг хүсжээ. 2-т тэрээр $X$-ыг хамгийн их байлгахыг хүсэв.

Та Лимак-д тусалж чадах уу? Түүнд туслан түүний барих цамхагт байж болох хамгийн их блокны тоо болон ийм тооны блок байрлуулж болох хамгийн их $X ≤ m$-ын утгуудыг олж өгнө үү.

Оролт

Эхний мөрөнд бүхэл тоо $m$ ($1 ≤ m ≤ 10^{15}$) өгөгдөх бөгөөд энэ нь Лимак таныг $X$-ын утгыг $1$ болон $m$-ын хооронд (эдгээр нь өөрсдөө мөн орно) байхаар сонгохыг хүсэж байгааг илэрхийлэх юм.

Гаралт

Цамхагт байж болох хамгийн их блокны тоо болон ийм тооны блок байрлуулж болох хамгийн их нийт эзлэхүүн $X$-ын утгуудыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
48
Гаралт
9 42
Оролт
6
Гаралт
6 6

Тэмдэглэл

Эхний жишээнд хэрэв та $X = 23$ эсвэл $X = 42$ гэж сонговол нийт $9$ блок байрлуулах юм. Лимак 2-т $X$-ыг хамгийн их байлгахыг хүссэн тул та $42$-ыг сонгох юм.

Илүү дэлгэрэнгүй байдлаар тайлбарлавал $X = 42$ гэж сонгосны дараа цамхаг барих явц нь дараах байдалтай өрнөх юм:

  • Эхлээд Лимак $3$ гэсэн талтай блок байрлуулах юм. Учир нь энэ нь эзлэхүүн нь $42$-оос хэтрээгүй байх хамгийн том блок бөгөөд ингэснээр үлдэж буй эзлэхүүн нь $42 - 27 = 15$ байх юм.
  • 2-т тэрээр $2$ гэсэн талтай блок байрлуулах ба ингэснээр үлдэж буй эзлэхүүн нь $15 - 8 = 7$ байх юм.
  • Эцэст нь Лимак $1$ гэсэн талтай $7$ ширхэг блокуудыг нэг нэгээр нь байрлуулах юм.

Ингэснээр нийтдээ $9$ ширхэг блок цамхагт байх бөгөөд нийт эзлэхүүн нь $3^{3} + 2^{3} + 7*1^{3} = 27 + 8 + 7 = 42$ байна.

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