// PR Bab 12, soal 4 -- pembahasan.
//
// Keluaran: k = 6, 9, 12, ... adalah nilai yang membuat greedy salah.

#include <iostream>
using namespace std;

const int BESAR = 1000000;
int koin[] = {4, 3, 1};          // terurut menurun

int greedy(int k) {
    int jumlah = 0;
    for (int i = 0; i < 3; i++) {
        jumlah += k / koin[i];
        k %= koin[i];
    }
    return jumlah;
}

int terbaik(int k) {
    if (k == 0) return 0;
    int hasil = BESAR;
    for (int i = 0; i < 3; i++) {
        if (k >= koin[i]) {
            int calon = terbaik(k - koin[i]) + 1;
            if (calon < hasil) hasil = calon;
        }
    }
    return hasil;
}

int main() {
    for (int k = 1; k <= 30; k++) {
        int g = greedy(k), t = terbaik(k);
        if (g != t) cout << "k = " << k << ": greedy " << g
                         << ", terbaik " << t << "\n";
    }
    return 0;
}