题解：P14684 [ICPC 2025 Yokohama R] Cutting Tofu

· · 题解

题解：P14684 [ICPC 2025 Yokohama R] Cutting Tofu

前言

博客食用更佳 题目传送门

思路讲解

一块 a\times b\times c 的豆腐，要用平行面切出至少 k 个尽可能大的立方体豆腐块。

立方体边长可为有理数，输出最简分数 p/q。

一次切割贯穿整个豆腐块，若以 a 维度 x 为基准维度，分成 n 段，那么边长为 s=\frac{a}{n}。

其他两个维度的切割次数为：

y=\left \lfloor \frac{b}{s} \right \rfloor=\left \lfloor \frac{b}{\frac{a}{n} } \right \rfloor=\left \lfloor \frac{b\times n}{a} \right \rfloor z=\left \lfloor \frac{c}{s} \right \rfloor=\left \lfloor \frac{c}{\frac{a}{n} } \right \rfloor=\left \lfloor \frac{c\times n}{a} \right \rfloor

所以总方块数量为：

ans=n\times y\times z=n\times\left \lfloor \frac{b\times n}{a} \right \rfloor \times \left \lfloor \frac{c\times n}{a} \right \rfloor

题目要求为 ans\ge k