C - Tombola 解説 by en_translator
Idea
Essentially, you are asked to implement the following procedure:
- For each row, inspect each of the \(N\) elements and check if it is contained in \(B\). Let \(r_i\) be the number of such elements.
- The answer is the maximum value among \(r_1, \dots, r_H\).
To determine if a value is contained in \(B\), inspect the \(N\) elements of \(B\) one by one. If you encounter the sought value, we can answer Yes, and otherwise, we can answer No. Perform this check for each of the \(W\) elements in a row. Prepare a counter \(r_i\) initialized with \(r_i = 0\). Every time you encounter a Yes element, increment the counter. This way, the sought count can be found.
The problem can be solved by implementing the procedure above using loops and conditional branches carefully. Be careful when implementing nested loop.
Sample code (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::max;
int main (void) {
// Input
int h, w, n;
cin >> h >> w >> n;
int a[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> a[i][j];
}
}
int b[n];
for (int i = 0; i < n; i++) {
cin >> b[i];
}
// Find the answer and store it in ans
int ans = 0;
int rowcount[h];
for (int i = 0; i < h; i++) {
// Find the answer for row i (rowcount[i])
rowcount[i] = 0;
for (int j = 0; j < w; j++) {
bool isfound = false; // Becomes true if a[i][j] is contained in b
for (int k = 0; k < n; k++) {
if (b[k] == a[i][j]) isfound = true;
}
if (isfound) {
rowcount[i] += 1;
}
}
// Update ans
ans = max(ans, rowcount[i]);
}
// Output
cout << ans << "\n";
return 0;
}
投稿日時:
最終更新: