Codeforces Round 697 B 题解

New Year's Number

Polycarp remembered the $2020$-th year, and he is happy with the arrival of the new $2021$-th year. To remember such a wonderful moment, Polycarp wants to represent the number $n$ as the sum of a certain number of $2020$ and a certain number of $2021$.

For example, if:

  • $n=4041$, then the number $n$ can be represented as the sum $2020+2021$;
  • $n=4042$, then the number $n$ can be represented as the sum $2021+2021$;
  • $n=8081$, then the number $n$ can be represented as the sum $2020+2020+2020+2021$;
  • $n=8079$, then the number $n$ cannot be represented as the sum of the numbers $2020$ and $2021$.
    Help Polycarp to find out whether the number $n$ can be represented as the sum of a certain number of numbers $2020$ and a certain number of numbers $2021$.

Input

The first line contains one integer $t$ ($1≤t≤10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case contains one integer $n$ ($1≤n≤10^6$) — the number that Polycarp wants to represent as the sum of the numbers $2020$ and $2021$.

Output

For each test case, output on a separate line:

  • YES if the number $n$ is representable as the sum of a certain number of $2020$ and a certain number of $2021$;
  • NO otherwise.

You can output YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Example

input

1
2
3
4
5
6
5
1
4041
4042
8081
8079

output

1
2
3
4
5
NO
YES
YES
YES
NO

题目大意

对于一个数 $n$ ,判断能不能被分解成 $a$ 个 $2020$ 和 $b$ 个 $2021$ 的和 ($a,b \in N$)。如果可以分解,输出 YES ,否则输出 NO

分析

$n$ 对 $2020$ 取模的结果就是如果 $n$ 全用 $2020$ 表示所剩下游离的个数,记作 $a$ 。现在我们把这 $a$ 个 $2020$ 替换成 $2021$ 就可以了。但问题是万一已有的 $2020$ 不足 $a$ 个呢?这样就不能表示,因此问题可化为判断已有的 $2020$ 的个数(n/2020) 是否大于等于(即足够替换) 需要替换的 $2020$ (n%2020) 。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main() {
int t, n;
scanf("%d", &t);
for(int i=0; i<t; ++i) {
scanf("%d", &n);
if(n%2020 <= n/2020) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}

Codeforces Round 697 B 题解

https://mmdjiji.com/2021/01/2602/

作者

吉吉

发布于

2021-01-26

更新于

2022-12-10

许可协议