公式

C - AtCoder AAC Contest 解説 by en_translator


Holding a contest requires one A, so the answer is not greater than \(n _ A\). Also, holding a contest requires on C, so the answer is not greater than \(n _ C\). Moreover, holding a contest requires three characters, so the answer is not greater than \(\left\lfloor\dfrac{n _ A+n _ B+n _ C}3\right\rfloor\).

Thus, the answer is not greater than \(X=\min\!\left\lbrace n _ A,n _ C,\left\lfloor\dfrac{n _ A+n _ B+n _ C}3\right\rfloor\right\rbrace\).

Now we will show that the answer is \(X\). This can be shown by actually demonstrating that \(X\) contests can be held.

Since \(X\le n _ A\), there are \(X\) or more As. Similarly, there are \(X\) or more Cs. After removing \(X\) As and \(X\) Cs from his characters, if he still has \(X\) or more characters, then we can hold \(X\) contests using them. Since \(X\le\left\lfloor\dfrac{n _ A+n _ B+n _ C}3\right\rfloor\), we have \(3X\le n _ A+n _ B+n _ C\), so we obtain \(n _ A+n _ B+n _ C-2X\ge X\); thus it has been shown.

Hence, the problem can be solved by printing \(X=\min\!\left\lbrace n _ A,n _ C,\left\lfloor\dfrac{n _ A+n _ B+n _ C}3\right\rfloor\right\rbrace\).

The following is sample code. Note that the value \(n _ A+n _ B+n _ C\) may become \(2 ^ {31}\) or greater.

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

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; ++t) {
        unsigned n_A, n_B, n_C;
        cin >> n_A >> n_B >> n_C;
        cout << min({n_A, n_C, (n_A + n_B + n_C) / 3}) << endl;
    }
    return 0;
}

投稿日時:
最終更新: