题解归档 - cf2222A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2222A
• 本地来源：problems/cf2222A/idea.md
• 题目链接：https://codeforces.com/contest/2222/problem/A
• 原始标题：cf2222A - A Wonderful Contest

思路

cf2222A - A Wonderful Contest

Pattern

Problem i can contribute every multiple of d_i = 100 / a_i from 0 to
100.

To make score 1, at least one problem must have d_i = 1, i.e. a_i = 100.
This condition is necessary.

It is also sufficient. A d=1 problem covers every score in an interval of
length 100; every other problem only shifts this interval by one of its
possible scores, and consecutive possible shifts differ by at most 100.
Therefore the shifted intervals cover the whole range from 0 to 100n.

Algorithm

Output Yes iff some a_i is 100.

Checks

• python tools/math_reasoning_search.py --problem cf2222A -n 5 - required
  precheck done.

代码

来源：problems/cf2222A/solution.cpp

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        bool has_one_point_subtask = false;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            if (a == 100) has_one_point_subtask = true;
        }
        cout << (has_one_point_subtask ? "Yes" : "No") << '\n';
    }
    return 0;
}