CodeForces 1475B - 做题记录

原题链接

• CodeForces
• 洛谷

题意

• 给出 $T$ 组数据，询问每组数据是否能够被若干个 $2020$ 与若干个 $2021$ 相加组成。

思路

对于题意的一种想法为

$$num = k_{1} \times 2020 + k_{2} \times 2021 \newline \Rightarrow num = (k_{1} + k_{2}) \times 2021 - k_{1}$$

则对于给定的数 $num$ 如果有方案使得其能够由 $k_{1} \times 2020 + k_{2} \times 2021$ 构成，满足：

• 对于超过 $num$ 的与其差最小的 $(k_{1} + k_{2}) \times 2021$ 的差，记为 $\Delta = (k_{1} + k_{2}) \times 2021 - num$ ，则 $\Delta \leq (k_{1} + k_{2})$

于是我们进行判断，符合条件输出 YES，否则输出 NO 即可。

code

#include <cmath>
#include <iostream>
using namespace std;

int T = 0;

inline void solve(const int num) {
  int delta = ceil(num * 1.0 / 2021) * 2021 - num;

  if (delta <= ceil(num * 1.0 / 2021)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin >> T;

  for (int i = 1, tmp; i <= T; ++i) {
    cin >> tmp;
    solve(tmp);
  }

  return 0;
}