题解 CF1679A【AvtoBus】

2022-05-15 21:06:54


题意

有两种类型的公交车,第一种车需要 4 个轮子,另一种需要 6 个轮子。

现在给你 $n$ 个轮子,要求恰好装到 $m$ 辆公交车上。问 $m$ 的最小值和最大值。

分析

首先考虑无解情况:

  • 如果给定的轮子不足 $4$ 个,则一辆车都装不好,无解。
  • 如果给的轮子数量是奇数,则无论如何都不能恰好地装上车。

其余情况:方程 $4x + 6y = 2k \ (k \geq 2)$ 一定有正整数解。其中 $x+y = m$。

要让 $x$ 取最小值,就让尽可能让每辆车消耗 $6$ 个轮子;反之,要取最大值,就尽可能多的让每辆车装 $4$ 个轮子。

代码

void solution() {
  ll n;
  read(n);
  if (n < 4) return print(-1);
  if (n & 1) return print(-1);
  if (n % 6 == 0 && n % 4 == 0) return print(n / 6, n / 4);
  ll y = n / 4;
  ll x = n / 6 + int(n % 6 != 0);
  return print(x, y);
}