Problem D - Burger, French Fries, Soft Drink

Anda diberikan urutan paket yang dikeluarkan oleh mesin seperti ini: BBFSSFSFBBFSSBFFSBBSF. Suatu pesanan dianggap valid jika jumlah B sama dengan jumlah F dan S. Misalkan diberi tahu ada N pesanan (N < 30), berapakah "kombinasi" pesanan yang mungkin terjadi kalau mesinnya mengeluarkan output seperti diatas?

Problem ini sengaja disamarkan dengan tidak menggunakan keyword "combination". Kembali ke contoh output mesin diatas, misalkan N = 3 (ada 3 pesanan). Maka kalau dilihat output dari mesin tersebut: BBFSSFSFBBFSSBFFSBBSF, terlihat ada 6 kemungkinan pesanan kecil-kecil yang valid: BBFSSF | SFB | BFS | SBF | FSB | BSF. Berikut adalah 10 possibilities dari pesanan tersebut:

• (BBFSSF) (SFB) (BFSSBFFSBBSF)
• (BBFSSF) (SFBBFS) (SBFFSBBSF)
• (BBFSSF) (SFBBFSSBF) (FSBBSF)
• (BBFSSF) (SFBBFSSBFFSB) (BSF)
• (BBFSSFSFB) (BFS) (SBFFSBBSF)
• (BBFSSFSFB) (BFSSBF) (FSBBSF)
• (BBFSSFSFB) (BFSSBFFSB) (BSF)
• (BBFSSFSFBBFS) (SBF) (FSBBSF)
• (BBFSSFSFBBFS) (SBFFSB) (BSF)
• (BBFSSFSFBBFSSBF) (FSB) (BSF)

Kalau anda melakukan analisa lebih dalam, akan terlihat rumus nCk berlaku (n choose k). Dalam kasus diatas, jawaban 10 didapat dari nCk(6-1, 3-1) -> (5 choose 2) -> 10 kombinasi pesanan. Kenapa ada -1? anda harus menganalisannya sendiri ;)

Ada cara lain untuk menyelesaikan soal ini tanpa pikir panjang. Yaitu dengan Dynamic Programming versi topdown atau boleh disebut juga rekursi + memoization. Cara ini sangat mudah bagi mereka yang sudah terbiasa melakukan DP Topdown :) Hampir tidak perlu berpikir panjang untuk menyelesaikan soal ini :) Silahkan lihat kode dp-topdown dibawah :)

#include <stdio.h>

int nChooseK(int n, int k){
    long long ret = 1, i;
    for (i=0; i<k; i++)
        ret = ret * (n-i) / (i+1);
    return (int) ret;
}

int main(){
    char s[101];
    int n;

    while (scanf("%d %s",&n,s)!=EOF){
        int G=0,B=0,F=0,S=0,i;

        for (i=0; s[i]; i++){
            if (s[i]=='B') B++;
            else if (s[i]=='F') F++;
            else S++;

            if (B==F && B==S) G++;
        }
        
        if (B!=F || B!=S || G<n)
            puts("Impossible");
        else
            printf("%d\n",nChooseK(G-1,n-1));
    }
}

#include <stdio.h>
#include <string.h>

char s[101];
int len, memo[101][35];

int ok(int L, int R){
    int B=0,F=0,S=0,i;
    for (i=L; i<=R; i++){
        switch (s[i]){
            case 'B' : B++; break;
            case 'F' : F++; break;
            case 'S' : S++; break;
        }
    }
    return B==F && F==S && B>0;
}

int rec(int idx, int n){
    int ret=0, i;

    if (idx>=len) return 0;
    if (n==1) return ok(idx,len-1);
    if (memo[idx][n]!=-1) return memo[idx][n];

    for (i=idx+2; i<len; i++)
        if (ok(idx,i))
            ret += rec(i+1,n-1);

    return memo[idx][n] = ret;
}

int main(){
    int n;

    while (scanf("%d %s",&n,s)!=EOF){
        len = strlen(s);
        memset(memo,-1,sizeof(memo));

        if (rec(0,n)==0)
            puts("Impossible");
        else
            printf("%d\n",rec(0,n));
    }
}

Lihat problem lain:

1. The Chosen Sub Matrix
2. Avoiding Financial Nightmare
3. No Pause Telegraph
4. Burger, French Fries, Soft Drink
5. Taxi!