## Complete Search

**Complete Search** atau lebih umumnya dikenal dengan istilah **Brute Force** (untuk selanjutnya kita akan menggunakan istilah tersebut) adalah suatu teknik penyelesaian masalah yang umumnya sering digunakan khususnya pada soal pemula. Teknik ini hanya memiliki satu tujuan yakni untuk **memeriksa segala kemungkinan jawaban yang ada dan memilih jawaban yang paling tepat. Karena teknik ini akan mencoba segala kemungkinan jawaban yang ada**, maka algoritma yang menggunakan teknik ini akan sangatlah akurat akan tetapi umumnya berjalan dengan lambat demikian apabila batasan pada soal bernilai kecil, patut dicurigai bahwa solusi yang diinginkan adalah solusi Brute Force.

> Umumnya pada kompetisi yang berformatkan International Olympiad in Informatics (IOI), sub-soal awal hanya akan menuntut Anda untuk menuliskan program Brute Force untuk mendapatkan poin parsial.

#### Contoh Soal 1
Pak Dengklek memiliki suatu peternakan yang berisikan tiga jenis hewan ternak yakni ayam, bebek, dan capung. Ia ingin mengisi peternakannya dengan sejumlah hewan tersebut. Sayangnya kapasitas dari peternakan tersebut hanya adalah $N$ $(1 \le N \le 100)$ ekor hewan (untuk setiap satu ekor hewan yang disebutkan di atas dihitung satu). Ia harus mengisi penuh peternakannya. Berapa banyak cara pengisian peternakan yang mungkin?

#### Solusi
Anggap bahwa jumlah dari ayam adalah $a$, jumlah bebek adalah $b$, dan jumlah capung adalah $c$, persoalan di atas dapat disederhanakan menjadi persoalan dalam mencari seluruh pasangan $(a, b, c)$ sehingga $a + b + c = N$. Karena batasan nilai kecil, maka kita dapat menggunakan teknik Brute Force dengan memeriksa seluruh pasangan $a + b + c$ di mana $a, b, c$ adalah bilangan non-negatif kurang dari $N$, dan apabila penjumlahan $a, b$, dan $c$ tidak sama dengan $N$, maka pasangan tersebut bukanlah pasangan yang valid, dan apabila sebaliknya, kita akan menambahkan jawabannya dengan 1. Ini akan memberikan solusi dengan kompleksitas $\mathcal{O}(N^3)$. Berikut adalah program `C++` dari solusi di atas:

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    int ans = 0;
    for(int a = 0; a <= n; a++){
       for(int b = 0; b <= n; b++){
            for(int c = 0; c <= n; c++){
                if(a + b + c = n) ans++;
            }
        } 
    }
    cout << ans << endl;
}

Dalam beberapa kasus, solusi *Brute Force* dapat dioptimisasi, dalam kasus ini, solusi diatas dapat dioptimisasi menjadi $\mathcal{O}(N^2)$, walau demikian ide utamanya tetaplah *Brute Force*. Observasi pertama yang berguna adalah, kita hanya perlu menghitung jumlah dari dua hewan di atas, anggap hewan yang dihitung adalah ayam dan bebek, maka untuk mendapatkan jumlah capung kita hanya perlu mengurangkan $N$ dengan $a + b$ dan apabila nilainya lebih besar sama dengan 0 maka nilai tersebut adalah nilai jumlah capung yang valid, secara formal jumlah capung yang valid adalah $N - (a + b)$ jika dan hanya jika $N \ge a + b$ . Maka dari sini kita hanya ingin menghitung jumlah nilai $c$ yang valid. Berikut adalah program `C++` dari solusi di atas:

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    int ans = 0;
    for(int a = 0; a <= n; a++){
       for(int b = 0; b <= n; b++){
            if(n - (a + b) >= 0) ans++;
        } 
    }
    cout << ans << endl;
}

##