1. /*
  2.                 FORHAD-SUST-BD
  3. */
  4. #include <iostream>
  5. #include <string>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <list>
  11. #include <set>
  12. #include <cmath>
  13. #include <cstring>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include <sstream>
  17. #include <stdlib.h>
  18. #include <vector>
  19. #include <iomanip>
  20.  
  21. using namespace std;
  22.  
  23. #ifdef __GNUC__
  24. typedef long long ll;typedef unsigned long long ull;
  25. #else
  26. typedef __int64 ll;  typedef unsigned __int64 ull;
  27. #endif
  28.  
  29. #define INF 1<<28
  30. #define SIZE 100
  31. #define PI 2*acos(0)
  32. #define fg %I64d
  33. #define REP(i,n) for (i=0;i<n;i++)
  34. #define REV(i,n) for (i=n;i>=0;i--)
  35. #define FOR(i,p,k) for (i=p; i<k;i++)
  36. #define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)
  37.  
  38. #define bug(x)    cout<< "->" <<#x<<": "<<x<<endl
  39. #define Sort(x) sort(x.begin(),x.end())
  40. #define Reverse(x) reverse(x.begin(),x.end())
  41. #define MP(a,b) make_pair(a,b)
  42. #define Clear(x,with) memset(x,with,sizeof(x))
  43. #define Copy(c,r)   memcpy(c,r,sizeof(r))
  44. #define SZ(x) (int)x.size()
  45. #define length(x) (int)x.length()
  46. #define All(x) x.begin(),x.end()
  47. #define pb push_back
  48. #define popcount(i) __builtin_popcount(i)
  49. #define gcd(a,b)    __gcd(a,b)
  50. #define fs first
  51. #define sc second
  52. #define two(X) (1<<(X))
  53. #define twoL(X) (((int64)(1))<<(X))
  54. #define contain(S,X) (((S)&two(X))!=0)
  55. #define containL(S,X) (((S)&twoL(X))!=0)
  56.  
  57. typedef pair<int,int> pii;
  58. typedef pair<double,double> pdd;
  59. typedef vector<int> vi;
  60. typedef vector<double>vd;
  61. typedef vector<ll>vll;
  62. typedef vector<string> vs;
  63. typedef vector<vi>vvi;
  64. typedef vector<vll>vvll;
  65. typedef vector<vd>vvd;
  66. typedef vector<pii>vpii;
  67. typedef map<string,int> msi;
  68. typedef map<int,int>mii;
  69. typedef map<pii,int>mpi;
  70.  
  71. template<class T> inline T sqr(T x){return x*x;}
  72. template<class T> inline bool isPrime(T n){if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;}
  73. template<class T> inline T Mod(T n,T m) {return (n%m+m)%m;} //For Positive Negative No.
  74. template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}
  75. int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
  76. ll toLl(string s){ll r=0;istringstream sin(s); sin>>r; return r;}
  77. template<class T> void debug(const T& e){cout<<e<<endl;}
  78. template<class T1,class T2> void debug(const T1& e1,const T2& e2){cout<<e1<<"\t"<<e2<<endl;}
  79. template<class T1,class T2,class T3> void debug(const T1& e1,const T2& e2,const T3& e3){cout<<e1<<"\t"<<e2<<"\t"<<e3<<endl;}
  80. template<class T1,class T2,class T3,class T4> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<endl;}
  81. template<class T1,class T2,class T3,class T4,class T5> void debug(const T1& e1,const T2& e2,const T3& e3,const T4& e4,const T5& e5){cout<<e1<<"\t"<<e2<<"\t"<<e3<<"\t"<<e4<<"\t"<<e5<<endl;}
  82. template<class T> void debug(vector<T>& e){int i;REP(i,SZ(e)) cout<<e[i]<<" ";cout<<endl;}
  83. template<class T> void debug(vector< basic_string<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j];cout<<endl;} cout<<endl;}
  84. template<class T> void debug(vector< vector<T> >& e){int i,j;REP(i,SZ(e)) {REP(j,SZ(e[i])) cout<<e[i][j]<<"\t";cout<<endl;} cout<<endl;}
  85. template<class T> void debug(T e[SIZE][SIZE],int row,int col){int i,j;REP(i,row) {REP(j,col) cout<<e[i][j]<<" ";cout<<endl;}}
  86.  
  87. ll Pow(ll B,ll P){	ll R=1;	while(P>0)	{if(P%2==1)	R=(R*B);P/=2;B=(B*B);}return R;} //compute b^p
  88. //struct pq{    int cost,node;bool operator<(const pq &b)const{return cost>b.cost;}};// Min Priority Queue
  89. //bool comp(pq a,pq b){    return a.cost > b.cost;}   //Comp Sort
  90.  
  91. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  92. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  93. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  94.  
  95. double dp[1<<15][55];
  96. vi profit;
  97. int N,K,req[15];
  98.  
  99. double rec(int mask,int k)
  100. {
  101.     double &ret=dp[mask][k];
  102.     int i;
  103.  
  104.     if(ret>-INF) return ret;
  105.  
  106.     if(k==K) return 0;
  107.  
  108.     ret=0;
  109.  
  110.     REP(i,N)
  111.     {
  112.         if((mask&req[i])!=req[i])
  113.         {
  114.             ret+=rec(mask,k+1);
  115.         }
  116.         else
  117.         {
  118.             ret+=max(rec(mask|two(i),k+1)+profit[i],rec(mask,k+1));
  119.         }
  120.     }
  121.     ret/=N;
  122.     return ret;
  123. }
  124.  
  125. class CrazyComponents
  126. {
  127. public:
  128. 	double expectedProfit(int k, vector <string> components, vector <int> income, vector <int> expense)
  129. 	{
  130. 	    int i,j,val;
  131.         double res;
  132.  
  133. 	    N=SZ(income);
  134. 	    profit.clear();
  135. 	    K=k;
  136.         REP(i,N)
  137.         {
  138.             istringstream iss(components[i]);
  139.             req[i]=0;
  140.             while(iss>>val)
  141.             {
  142.                 req[i]|=two(val);
  143.             }
  144.             profit.pb(income[i]-expense[i]);
  145.         }
  146.         REP(i,two(N))
  147.             REP(j,K)
  148.                 dp[i][j]=-INF;
  149.         res=rec(0,0);
  150.         return res;
  151. 	}
  152. };
  153.  
  154.  
  155. template<typename T> void print( T a ) {
  156.     cerr << a;
  157. }
  158.  
  159. void print( long long a ) {
  160.     cerr << a << "L";
  161. }
  162.  
  163. void print( string a ) {
  164.     cerr << '"' << a << '"';
  165. }
  166.  
  167. template<typename T> void print( vector<T> a ) {
  168.     cerr << "{";
  169.     for ( int i = 0 ; i != a.size() ; i++ ) {
  170.         if ( i != 0 ) cerr << ", ";
  171.         print( a[i] );
  172.     }
  173.     cerr << "}" << endl;
  174. }
  175.  
  176. template<typename T> void assert_eq( int n, T have, T need ) {
  177.     if ( have == need ) {
  178.         cerr << "Case " << n << " passed." << endl;
  179.     } else {
  180.         cerr << "Case " << n << " failed: expected ";
  181.         print( need );
  182.         cerr << " received ";
  183.         print( have );
  184.         cerr << "." << endl;
  185.     }
  186. }
  187.  
  188. template<typename T> void assert_eq( int n, vector<T> have, vector<T> need ) {
  189.     if( have.size() != need.size() ) {
  190.         cerr << "Case " << n << " failed: returned " << have.size() << " elements; expected " << need.size() << " elements.";
  191.         print( have );
  192.         print( need );
  193.         return;
  194.     }
  195.     for( int i= 0; i < have.size(); i++ ) {
  196.         if( have[i] != need[i] ) {
  197.             cerr << "Case " << n << " failed. Expected and returned array differ in position " << i << ".";
  198.             print( have );
  199.             print( need );
  200.             return;
  201.         }
  202.     }
  203.     cerr << "Case " << n << " passed." << endl;
  204. }
  205. void assert_eq( int n, string have, string need ) {
  206.     if ( have == need ) {
  207.         cerr << "Case " << n << " passed." << endl;
  208.     } else {
  209.         cerr << "Case " << n << " failed: expected ";
  210.         print( need );
  211.         cerr << " received ";
  212.         print( have );
  213.         cerr << "." << endl;
  214.     }
  215. }
  216.  
  217. int main( int argc, char* argv[] )
  218. {
  219.  
  220. 	CrazyComponents objectCrazyComponents;
  221.  
  222. 	//test case0
  223. 	int param00 = 1;
  224. 	vector <string> param01;
  225. 	param01.push_back("");
  226. 	param01.push_back("");
  227. 	vector <int> param02;
  228. 	param02.push_back(1);
  229. 	param02.push_back(2);
  230. 	vector <int> param03;
  231. 	param03.push_back(0);
  232. 	param03.push_back(0);
  233. 	double ret0 = objectCrazyComponents.expectedProfit(param00,param01,param02,param03);
  234. 	double need0 = 1.5;
  235. 	assert_eq(0,ret0,need0);
  236.  
  237. 	//test case1
  238. 	int param10 = 2;
  239. 	vector <string> param11;
  240. 	param11.push_back("1");
  241. 	param11.push_back("");
  242. 	vector <int> param12;
  243. 	param12.push_back(10);
  244. 	param12.push_back(0);
  245. 	vector <int> param13;
  246. 	param13.push_back(0);
  247. 	param13.push_back(2);
  248. 	double ret1 = objectCrazyComponents.expectedProfit(param10,param11,param12,param13);
  249. 	double need1 = 1.5;
  250. 	assert_eq(1,ret1,need1);
  251.  
  252. 	//test case2
  253. 	int param20 = 3;
  254. 	vector <string> param21;
  255. 	param21.push_back("1 2");
  256. 	param21.push_back("");
  257. 	param21.push_back("");
  258. 	vector <int> param22;
  259. 	param22.push_back(100);
  260. 	param22.push_back(0);
  261. 	param22.push_back(0);
  262. 	vector <int> param23;
  263. 	param23.push_back(0);
  264. 	param23.push_back(0);
  265. 	param23.push_back(0);
  266. 	double ret2 = objectCrazyComponents.expectedProfit(param20,param21,param22,param23);
  267. 	double need2 = 7.407407407407408;
  268. 	assert_eq(2,ret2,need2);
  269.  
  270. 	//test case3
  271. 	int param30 = 5;
  272. 	vector <string> param31;
  273. 	param31.push_back("1");
  274. 	param31.push_back("2");
  275. 	param31.push_back("0");
  276. 	param31.push_back("");
  277. 	vector <int> param32;
  278. 	param32.push_back(4);
  279. 	param32.push_back(5);
  280. 	param32.push_back(6);
  281. 	param32.push_back(7);
  282. 	vector <int> param33;
  283. 	param33.push_back(0);
  284. 	param33.push_back(0);
  285. 	param33.push_back(0);
  286. 	param33.push_back(8);
  287. 	double ret3 = objectCrazyComponents.expectedProfit(param30,param31,param32,param33);
  288. 	double need3 = 0.0;
  289. 	assert_eq(3,ret3,need3);
  290.  
  291. 	//test case4
  292. 	int param40 = 10;
  293. 	vector <string> param41;
  294. 	param41.push_back("");
  295. 	param41.push_back("");
  296. 	param41.push_back("");
  297. 	param41.push_back("");
  298. 	param41.push_back("");
  299. 	param41.push_back("");
  300. 	param41.push_back("");
  301. 	param41.push_back("");
  302. 	param41.push_back("");
  303. 	param41.push_back("");
  304. 	vector <int> param42;
  305. 	param42.push_back(142352);
  306. 	param42.push_back(2342);
  307. 	param42.push_back(34534);
  308. 	param42.push_back(2344);
  309. 	param42.push_back(12346);
  310. 	param42.push_back(7589);
  311. 	param42.push_back(79872);
  312. 	param42.push_back(973453);
  313. 	param42.push_back(96233);
  314. 	param42.push_back(34567);
  315. 	vector <int> param43;
  316. 	param43.push_back(12432);
  317. 	param43.push_back(2345);
  318. 	param43.push_back(3678);
  319. 	param43.push_back(456);
  320. 	param43.push_back(345);
  321. 	param43.push_back(457);
  322. 	param43.push_back(56758);
  323. 	param43.push_back(4564);
  324. 	param43.push_back(774);
  325. 	param43.push_back(34567);
  326. 	double ret4 = objectCrazyComponents.expectedProfit(param40,param41,param42,param43);
  327. 	double need4 = 1269258.9999999998;
  328. 	assert_eq(4,ret4,need4);
  329.  
  330. }
  331.