ACM/ICPC Indonesia National Contest 2007 - Qualification
Problem D
Burger, French Fries, Soft Drink
Time Limit: 1sAnna works as a waitress at a popular fast-food restaurant in Indonesia, "Om Burger". Her job is much easier than any waiters/waitresses at other fast-food restaurants, because Om Burger owns an automatic fast-food machine.
Om Burger serves only a single combo-menu package named Paket Uenak, which consists of three items: 1 Burger (B), 1 French Fries (F), and 1 Soft Drink (S). Each customer would be given a card to write the number of Paket Uenak packages to be ordered. The card should be given back to Anna who will insert it into the machine. The machine will prepare all items of each package one by one according to the written number on the card, but not necessary in any particular order of item. For example, if the number 2 (means 2 Paket Uenak packages are ordered by a customer) is written on the card, the machine will prepare items in the sequence of BBFFSS, or any of its permutation (BFSBFS, BBFSFS, etc). There could be more than one card to be processed by the machine at a time. However the machine will process all cards sequentially. That means it will not proceed to the next card before finishing the current card.
One day, some customers are queuing to put their orders. While they make a quite long queue, it gives Anna an idea. Instead of inserting the card one by one, she initiatively inserts more than one card at a time. Brilliant, isn't she? Well, let's see what happens next. The machine does work well, but now she doesn't have any idea which item belongs to which card, because the machine doesn't give any separations to separate packages from different cards.
Fortunately, Anna still remembers the number of cards inserted and its sequence (which card belongs to whom). However, she doesn't remember the number of Paket Uenak packages written on each card.
For example, if there are two cards inserted into the machine:
Prepared : B B F S S F S F B B F S
Possibility-1 : (B B F S S F) ( S F B B F S), the first customer ordered 2 Paket Uenak packages, and the second customer ordered 2 Paket Uenak packages.
Possibility-2 : (B B F S S F S F B) (B F S), the first customer ordered 3 Paket Uenak packages, and the second customer ordered 1 Paket Uenak package.
No need to tell, that now she's apologizing and questioning all customers for what they have been ordering again. But this problem has aroused her curiosity as she is also a student in Computer Science. Help Anna to find how many possible order arrangements could be found from any given condition(s).
Input Specification
Each line of input contains an integer N (1 < N < 30) denoting the number of card(s) inserted, and a string which contains character(s) of B, F, and S (no spaces) denoting the order of items prepared by the machine. You may assume that the length of each string is less than 100.Output Specification
For each line of input, print the number of possible order arrangements could be found. If there is no possible order arrangement, output "Impossible" (without quotes).Sample Input
2 BBFSSFSFBBFS 2 BBFSSFSFBB
Sample Output
2 Impossible
Problem Setter: Suhendry Effendy
Pembahasan 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));
}
}
No comments:
Post a Comment