2006 年百度之星程序设计大赛初赛题目 1

厚积薄发

饭团的烦恼

) q  V' C" o2 d7 [3 F2 f) |! T; N“午餐饭团“是百度内部参与人数最多的民间组织。

3 I# U% ?- v$ H同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
7 L  F( T) H$ c6 y, h. w
0 V6 N. E3 ^- Q% I+ u/ F) {参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

; }0 U% j! V2 P/ ]' }1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
% F" Y, P! H. H/ Z
紧接着 N 行，每行的格式如下：
- Q* j1 p. |3 ?+ G
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
# K/ R# [% n1 C
例：
' c7 P- ]" {' [4 ]8 F& s) E
水煮鱼 30 1 1
2 D' O- B: n, E  e
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
! D& W6 A4 z6 f* i0 R) O( M; Z
' }& q2 G7 g: S3 }: F0 ?输出数据：
3 X9 ^; ]- _: v6 j- c
/ t8 i0 u, t) G" y/ C对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

; G6 [" e* V, P3 H8 h# Q0 v( ]说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

2 S! k. g% B3 K% ~2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
+ W2 T+ r! J, _% z. V$ C
输入样例

3 2 2

& F# T6 F% A. _! `# G' M9 W; n( ^水煮鱼 30 1 1
! y. V' p) X: d2 i6 i# p- M: g
8 g' |& {" m0 I# J$ ^: S口水鸡 18 1 1

清炖豆腐 12 0 0

7 y' d* D9 E5 `/ C1 1 1 1

# T. j8 k. g, s/ n& ~
! R) ]  w1 p" Q" n输出样例

3 _# z- `8 T4 p/ M5 ?2 F) q& z口水鸡
: W' v) O. z- Y
% K& ~! w% d; X+ V/ D清炖豆腐

4 f+ {+ e/ y- X7 G" V) G12.00
- x- v* n: }% n( y* u

# F7 m- a: t2 x, [
# V) T2 r! I4 @1 V3 U1 L时间要求： 1S 之内

! q9 G( ]' h) H) Z9 U9 {example：
5 _% P5 X( {  Z3 @8 v. A+ u#include <cstdlib>
#include <iostream>

using namespace std;


3 Q& H4 k4 x6 Y- H7 t0 W. ustruct cai
: v$ H% T. w& c; l( [$ }4 k{
       string cainame;
       int price;
       int hun;
1 n" d  h# T8 X. c3 r/ Y% W2 _, x       int la;
       };
int* alltotal=new int[30];
int pos=0;
cai* pcai;
int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
" H' e6 w. S6 R% x2 D. v. Y9 b    pcai[0].cainame="water fish";
3 o7 W. l, ?% g# b8 u$ T/ q/ ^+ a    pcai[0].hun=1;
8 L0 H% l" r; P6 a* h    pcai[0].la=1;
    pcai[0].price=30;
0 U5 K4 A3 N/ C% J9 g+ i5 C    pcai[1].cainame="mouth fish";
' _! v/ e' [3 ~( F    pcai[1].hun=1;
    pcai[1].la=1;
" g+ U( h1 x& P" U. \) c    pcai[1].price=18;
& \4 Z8 c; T) ^: p( p& u+ Q$ \2 F    pcai[2].cainame="doufu";
    pcai[2].hun=0;
* |% V' I* G8 a8 O4 m    pcai[2].la=0;
0 f' l0 F/ t2 l1 Y4 W    pcai[2].price=12;
& U5 r0 B4 o: B! W/ C    for(int i=0;i<N;i++)
6 o6 x0 j1 u6 ~/ r7 J% j3 Y    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
3 g4 Z$ K" A- M1 d: M0 a3 _$ i        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
$ m3 S/ k: Z$ F) U        select[0]=i;
: i; }2 E* ]7 e- Q  s) c        if(pcai.hun==1)ta--;else tb--;
, `! h# S1 V3 T3 O3 B& |! s9 ?& Y        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
! X5 Q5 Z* X$ X% O8 T# j9 X        delete[] select;
        }
+ O0 s$ v* j9 [3 G( `    }
  G; }1 v8 u3 S# g    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
    delete alltotal;
( c" l: k) X. f1 J0 h- }    delete []pcai;
' r, P) u: d0 e, h+ ^4 I4 J3 R    system("PAUSE");
    return EXIT_SUCCESS;
}
. N' `! D# N9 h7 C, L4 P) ivoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
* v% v% Y4 A4 [2 C$ [2 X    //getchar();
, c) y# A0 M: L* ]. i* {: f    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
0 V6 B' z6 n' y$ w& {( ~    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
0 o; ?, A( D! Z" G5 a5 ~3 \    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
8 j  A7 [, g) o; N% i" D0 n$ S    for(int i=select[n-1];i<N;i++)
    {
! i2 A3 B! h+ E7 u% r' Q8 k# y         for(int j=0;j<n;j++)if(select[j]==i)continue;
        if( (a<=0&&b<=0&&c<=0&&d<=0) || (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
. G9 ?# |, h% N4 _( A; j        myselect[n]=i;
. c1 w: \) V' D0 b: ]        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
; i" \7 z0 Y3 P" X6 p% W/ ~$ i        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
* ?" ^7 G8 w7 w8 g  C        delete[] myselect;
        }
    }
: L! M( H7 E0 `3 E2 u& ?; i( P}

928171481

嗯，不错不错