饭团的烦恼
' d$ U+ W1 j) i4 | B
* }& q" V; c6 [7 z9 r1 t" d6 z: F- A“午餐饭团“是百度内部参与人数最多的民间组织。
- \% ?8 M3 W* W6 q% h7 }+ q4 A& Q$ @ Z0 \; J2 @
同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。
+ G3 l# @) a( D# w5 l9 |! u- X; K
; B, G- j$ ~6 s* m; c参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。
$ N' _; F7 U7 F
R; \" c9 e: p: K) C: K1 s' ~' k但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
0 _; l! a; [0 w7 E z1 a b9 \" H3 d: t) ^
饭团点菜的需求如下:
+ O4 n7 L/ i7 h* p8 s" r3 e. L, p9 }5 }& G0 a- Q2 e
1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。
0 b3 o# ~# D" N- c
0 S: q, ?' ]2 z5 T7 F9 ^0 }* r2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。 7 u8 C6 a% T% U+ o i6 b9 W
1 f: Q7 W/ b% h0 V+ |1 D$ \6 F
3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。
" {2 W, D8 @! p) j/ x$ n! `, p
/ X4 R+ U. P, k& |% i8 w' [输入数据描述如下: 9 a& C3 g( V) e! Z
' ?, n5 y% H, x! d9 O+ n第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。 5 H, v( \( }4 M7 S+ y3 z( ]
6 o* j' ^" W3 o# l2 g' k紧接着 N 行,每行的格式如下: * H8 R; M: u) p/ o( E8 g& T' z
0 x) H" `5 R0 ?# t
菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否) ; i- Q* g" j: N+ \
* b$ U' g4 F8 U" ~
例: & o5 z$ ~; n9 ~) R' V
6 h) w3 Q- O* m# ?4 f% W水煮鱼 30 1 1 ' v z# a n. H) D4 r s! {9 J/ q; N+ Q
5 b% c4 L- q/ I$ c紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。 ! q [0 V/ O7 `4 N4 o: z8 m- ]: P
4 D9 f4 I6 k* I: Y输出数据: 8 f8 x9 v# R" T, E# g
0 }- Y3 O0 ^" D9 r. S0 T, w* c' p. C
对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。
0 o6 O4 j% g) P: _: O5 L7 U$ T2 V. z: O
说明: ! C; K! P1 `+ u" \
6 c0 R2 Q# S' m6 s( K+ I1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
8 _' E; t F# @1 _; d7 Y" }1 W9 @- y+ p0 _5 l" F3 e
2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。 4 Y; p, `( ]3 s6 q# X6 o
. Q2 \. L; L) A) G! W9 e0 u' G
输入样例
2 w9 R8 ~3 c+ [) `( y- ^5 [- k3 2 2
r" ?& R1 s/ o1 t" a
4 r6 j& r; |/ V* p# O' a5 T水煮鱼 30 1 1 # \6 B* I( [( w; {" a: U
! d) }- X1 x% }) @口水鸡 18 1 1
1 d. h7 n- s8 P8 q+ c; v; f. x2 W# [5 p7 @( @/ p8 x2 V
清炖豆腐 12 0 0
9 i* E% U; |" X1 s& D% {
/ c) a1 k3 \; T' J- Q/ {1 1 1 1 / I8 y7 R. w; ^ l& F4 n; ~( U
7 ]0 @9 Y% }6 X5 e% c- S' U0 A( Z
& v; n$ }" ^, c# t/ y) y
输出样例
9 M I: i) C5 W! Y口水鸡 : C, s' Z( s) O% [0 b
3 U8 m1 k A7 p/ ?清炖豆腐
/ c8 G" X5 S+ `! |/ d1 Z9 Z2 C! o% A% ^; }( C, P" I& n
12.00 ) z+ ], J/ V# `% U/ x
2 D! P& }1 G( M$ N$ H/ J- Q* J2 C
* u, G, x! U9 j& u3 H, P- Z
5 T8 `$ n- I. T' h; z时间要求: 1S 之内
* E) b1 o# ]( }5 Z. F5 l1 i! ~$ t, N9 R9 z6 [. z$ C
example:
) E& D. d' U1 D# v- |$ N/ z#include <cstdlib>
9 B) z0 l- \# ^8 ]#include <iostream>6 S. s s' U- F$ `$ Z6 H7 k4 f) p2 Q
7 Y! p( Q# \- ]: F8 qusing namespace std;2 V8 y% a6 d1 s
6 g. m. e' b! E7 d" i9 E2 T1 e- i% f
struct cai* S4 V4 a# E) e7 _# l& ^5 ]
{, o2 ~: O ]4 Y) O
string cainame;
4 t) g( _$ b! j8 E( p$ p int price;
6 c6 S. t- Y- g! G7 E7 W$ g/ | int hun;
2 Q: W: M+ J2 o S int la;
6 g z) x: u2 Y& n: m3 c( J* R };0 s/ Z7 T( @: Y4 {7 T
int* alltotal=new int[30];* @) t+ P$ @: F3 l) N. K6 l
int pos=0;* l) m; C( d& {" i
cai* pcai;
/ `: c4 E8 \$ B* R6 E$ n; }+ K Wint N=3;
. }7 o$ X/ X0 V+ C/ Mvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
o0 d6 I1 g8 T) a, ^7 v/ }$ rint main(int argc, char *argv[])
+ s5 S1 }$ K+ o# n1 k{
# l: @3 L4 Y6 n8 | Z `1 H: i int M=2,K=2;3 q! T4 S) K4 I1 x. D+ m( j9 ~& v6 O
int a=1,b=1,c=1,d=1;
- l8 Z7 X' f3 j" r! |) r/ E p, i pcai = new cai[N];
1 C& A8 U) h- N% [ pcai[0].cainame="water fish";+ Q# c5 `2 J0 y) a" a4 n" p; {
pcai[0].hun=1;
- E( }4 f5 S4 d& {9 y) F3 X pcai[0].la=1;
1 c" d2 z* u/ {7 j/ w; F pcai[0].price=30;
9 c2 Q D D# f6 B4 ^$ V7 A pcai[1].cainame="mouth fish";
8 A% i( D* n5 c- G8 d0 ? Q" q& a( j pcai[1].hun=1;
% `1 }( C) X% |* h' D4 t pcai[1].la=1;6 {1 k2 C$ q; F
pcai[1].price=18; 8 z/ ~# V6 H x- ~7 r; L- R, r
pcai[2].cainame="doufu";
& g) G" B/ q9 M7 a2 T pcai[2].hun=0;' l4 o4 ]! H4 p) m, {
pcai[2].la=0;2 n5 t) f1 G, b/ T/ j
pcai[2].price=12;
% x, }) ?+ m9 P f2 Y% L3 I; G: R for(int i=0;i<N;i++)
" z1 }/ o$ d( D1 K {8 w7 m# N# R7 I* e- N
if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))2 F0 r/ y# b! Z/ _) ]
{& R0 B+ `* e: `. J. J }3 d
int ta=a,tb=b,tc=c,td=d;
5 f& V7 W; U5 w int* select=new int[1];
1 q9 W1 M. ^) L% ^! s select[0]=i;/ j2 i- `* r" {+ J) ~
if(pcai.hun==1)ta--;else tb--;
, p0 x v; D& U) V+ P+ I7 E. c1 Z if(pcai.la==1)tc--;else td--;
% d: Z0 e6 }; ^6 Q! _ fun(select,1,M-1,ta,tb,tc,td,pcai.price);6 G5 j s. \- e8 D! Q; _2 y5 x. w+ L
delete[] select;( }3 u w$ t& ^/ E# ^* U0 ~6 X! i
}, d! S9 _; H( y* G; |8 O
}2 E/ E: m+ I3 s( G2 T: H9 G4 ?1 l
for(int i=0;i<pos;i++)
4 H; x3 n9 m0 }3 n. e cout<<alltotal<<endl;
& R4 d9 P+ [: U* C: Y+ _ delete alltotal;" l* S, Y. S# G
delete []pcai;" r8 R4 H0 ?% G: ?8 P& A
system("PAUSE");+ }$ C N" x2 b" [8 l! Z$ ~4 W
return EXIT_SUCCESS;
& Q p9 a# ~ W. _: A7 k% \: U}
* B- K! d3 `+ x8 `void fun(int * select,int n,int M,int a,int b,int c,int d,int total)2 Z M, e1 l9 v6 P& V! A
{
4 g6 s1 @" N9 D% c) l) {0 S& i% c //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;7 |- w T' f2 W# s( Z$ M# X
//getchar();' l% f( M0 U* f9 _
//cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;( R0 B# N' ]" a% x5 t) Y
if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
; F2 ?% T7 \% U if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
0 F5 B. |! ?* p2 D; w; ?2 V for(int i=select[n-1];i<N;i++)
5 p6 I D, G# t$ B; Y {1 P, `$ [( S. G# o$ a
for(int j=0;j<n;j++)if(select[j]==i)continue;
& B8 X% T; K9 d; @( H$ [; H 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)) A+ R1 q5 w# A6 ?% A9 f
{
' b3 W6 y% c) H: c; p9 D int ta=a,tb=b,tc=c,td=d;) q5 c8 o" Y( z: p
int* myselect=new int[n+1];
8 w: ?7 p! w4 d6 Y5 e3 K7 Q1 b for(int k=0;k<n;k++)myselect[k]=select[k];) o# ]+ a$ _+ Z3 f `
myselect[n]=i;
" g5 E5 O/ ^# o( I! f if(pcai.hun==1)ta--;else tb--; z5 o9 ]3 }, `4 ^" x1 u
if(pcai.la==1)tc--;else td--;0 F# o0 f9 |% d3 T6 f1 M( s
fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);; w: i( S! Z% n" H/ \" b
delete[] myselect;' w- k( N8 l2 o& p' x) W
}
* g2 m) }% u9 l; D5 T }
* ?$ E* D+ ^# ^+ a+ e% o6 V} |