Codeforces Round #132 (Div. 2) A : Bicycle Chain
問題概要
長さN,M(<50)の配列A,Bが与えられる。argmin_{i,j, B[j]%A[i]==0} B[j]/A[i] の濃度を求める問題。
解法
全探索。
acceptされたコード
#include <cstdio> using namespace std; template<typename numType> inline bool updateMax(numType& old, const numType& test) { if (old < test) { old = test; return true; } return false; } const int MAX_N = 50; int N, M; int as[MAX_N], bs[MAX_N]; void init() { scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", as + i); } scanf("%d", &M); for (int i = 0; i < M; ++i) { scanf("%d", bs + i); } } int solve() { int maxi = -1; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (bs[j] % as[i] == 0) { updateMax(maxi, bs[j] / as[i]); } } } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (bs[j] % as[i] == 0 && bs[j] / as[i] == maxi) { ++ans; } } } return ans; } int main() { init(); printf("%d\n", solve()); return 0; }