// Contoh Bab 10: menguji penyelesaian cepat dengan penyelesaian lambat.
//
// Soal: berapa banyak pasangan (i, j) dengan i < j dan a[i] + a[j] genap?
//
// Versi lambat memeriksa semua pasangan: O(n^2), pasti benar.
// Versi cepat memakai pengamatan: genap+genap atau ganjil+ganjil.
//
// Compile:  g++ -std=c++17 -O2 -o banding exercises/10/04-uji-banding.cpp
// Jalankan: ./banding

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

long long lambat(int a[], int n) {
    long long banyak = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if ((a[i] + a[j]) % 2 == 0) banyak++;
    return banyak;
}

long long cepat(int a[], int n) {
    long long genap = 0, ganjil = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) genap++;
        else ganjil++;
    }
    return genap * (genap - 1) / 2 + ganjil * (ganjil - 1) / 2;
}

int main() {
    srand(12345);                       // angka acak yang sama tiap kali

    for (int uji = 1; uji <= 1000; uji++) {
        int n = rand() % 6 + 1;         // n antara 1 dan 6
        int a[10];
        for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;

        long long h1 = lambat(a, n);
        long long h2 = cepat(a, n);

        if (h1 != h2) {
            cout << "berbeda pada uji ke-" << uji << ": n = " << n << "\n";
            for (int i = 0; i < n; i++) cout << a[i] << " ";
            cout << "\nlambat = " << h1 << ", cepat = " << h2 << "\n";
            return 0;
        }
    }

    cout << "1000 uji cocok semua\n";
    return 0;
}