Competitive Programming Solutions

1466A - Bovine Dilemma

30 Dec 2020 — Tags: math,brute_force — URL

In the formula $A = \frac{h_b b}{2}$, the only variable that changes is the base length, $b$. List all pairs, of points on the x axis and count the unique distances.

Time complexity: $O(n^2)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a)
{
    int n = (int)(a).size(), ans = 0;
    vector<bool> vis(100, 0);
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            int b = abs(a[i] - a[j]);
            if (vis[b])
                continue;
            vis[b] = true;
            ans++;
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        for (auto &x : a)
            cin >> x;
        cout << solve(a) << endl;
    }
    return 0;
}

Related posts