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 A
s. Similarly, there are \(X\) or more C
s.
After removing \(X\) A
s and \(X\) C
s 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;
}
投稿日時:
最終更新: