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

厚积薄发

饭团的烦恼
0 i3 q& ^; I" \
“午餐饭团“是百度内部参与人数最多的民间组织。
. T) L) S( F& _" |
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
+ o% B9 b, Y8 {, l4 ~& X5 j7 d5 j
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
4 Y- X0 W: Q. @; E9 k; S. r0 P
2 O3 l+ [" M, z4 V+ E# g饭团点菜的需求如下：

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

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

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

输入数据描述如下：

* F0 Q/ W4 C3 u" x第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

* ^# p5 X! P+ Z" L. i- l8 M3 @3 v紧接着 N 行，每行的格式如下：

菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
! S( u# x# d* ~+ O2 ^  `& [
例：
, c) f- E/ v- @  G4 v
水煮鱼 30 1 1
) M! [* {7 s  O% P. }
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
4 S3 h5 K- `( w6 R
* N7 H' K" t( }5 I9 @, ]# {输出数据：
: G& y; X! g5 L8 H
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

# ?' o2 l) p. t说明：

2 z+ O5 [; k& Q8 X8 A- r1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
% w: b8 H9 X% E! @
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
/ x* q2 V& u- P7 K" \9 k4 R
输入样例

' S3 W% a& S- h& r# Q9 X( U- K3 G3 2 2

  {, L, ?1 g! N; \水煮鱼 30 1 1
  Q. m  K2 D. i4 o. K( a
# ~* i1 U: H" y7 X# M口水鸡 18 1 1

清炖豆腐 12 0 0
4 \& U8 [8 T: t6 f5 b" r
1 1 1 1
: C, E! G' A7 s: u

# H6 b4 J% m* F" U/ O; `$ L
输出样例

口水鸡
& H: j+ l! x# ~
9 t) s1 \% x$ E. f, N9 G2 O8 V清炖豆腐

# j! C! A% C$ h8 Z0 Z12.00
. Q1 m. t- E/ Z1 a; A" Z

7 a3 W+ R8 b2 t3 X/ W- F

3 y9 [+ F5 A* Q% E时间要求： 1S 之内

example：
4 t( m" Q3 A. H2 E: V#include <cstdlib>
#include <iostream>
) Z6 j1 x7 M- N+ z! X+ l0 ?
using namespace std;
8 {. i% ~8 L5 C$ X: ~
- M$ d1 ]$ |$ L
struct cai
$ |( F! H. F% K# o2 _8 E! w  Q, M: m{
       string cainame;
       int price;
       int hun;
* O; I& J5 w. Q% F! e       int la;
3 _4 I7 `, U7 k  V# F/ ^8 W       };
% I# P1 e# S1 @9 z4 D* @, |int* alltotal=new int[30];
int pos=0;
1 U8 }- Q$ b. q8 tcai* pcai;
int N=3;  
  h  ~$ }9 E1 [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;
  d3 f; @% K* `( F, D    int a=1,b=1,c=1,d=1;
( T' j, }7 ~/ b9 ]# _    pcai = new cai[N];
    pcai[0].cainame="water fish";
. E' _( `8 o" R" X8 k    pcai[0].hun=1;
1 S6 E. z5 C: T! u# `, ^: V& E& W1 e    pcai[0].la=1;
) O( }: f) F* D9 L: |: |( Y2 s    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
5 w( b: Y  i0 G* V& y4 b8 O7 g  R    pcai[1].hun=1;
" Q4 W7 F" [; ^9 P    pcai[1].la=1;
    pcai[1].price=18;
# T0 `" e& U9 X& _    pcai[2].cainame="doufu";
    pcai[2].hun=0;
0 C: Y2 v- B4 U    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
( Z% G! M4 F8 e, s( o4 w) Q3 A    {
- l: q  g, t( _5 W& c        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
$ z& b( g7 J* ?) {( t2 K8 e& D        {
        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
% U4 L, \" c0 z9 [        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
- H0 k: }4 W4 q6 m) }8 E        }
    }
% M  d# _0 A- F' P: Q# W; j    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
( z9 }: g  w) x5 a6 Y) e    delete alltotal;
& d) O8 P1 h. p$ ?    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
& F0 k: S" G  x7 V9 d}
- g0 ^0 B! F2 F, `. y; u0 Z& svoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
) f+ f! h# l5 `. F- [0 D% c7 O{
+ C, M3 y" _( w# S    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
! g4 S. H3 e! s. j* n    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
- B4 \" k: s4 [/ J7 G# b3 }    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
    for(int i=select[n-1];i<N;i++)
4 p2 a5 a. E$ ]7 F* x    {
; X- b* c3 T6 G* B         for(int j=0;j<n;j++)if(select[j]==i)continue;
2 X. }3 W& y7 t+ h0 C  S        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))
        {
& }% x: T% r8 M        int ta=a,tb=b,tc=c,td=d;
3 I7 U$ d/ H$ [5 _        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
1 W/ p/ Q) _# T& g2 n+ L        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
; |/ [9 ~4 U+ o$ h3 y3 u        }
& ^* o% I& x9 O4 A, n+ Q& p    }
}

928171481

嗯，不错不错