fork download
copy 
  1. /*
  2.   Zenit CK 2011/2012, uloha g)
  3.   Riesenie by Zemco
  4.  
  5.   Skusame vsetky moznosti skupiny ludi. Danu skupinu vyskusame,
  6.   ci kazdy schopnost vie niekto a ak ano, zistime
  7.   ci nie je lacnejsia/skor v abecede ako ta, ktoru pozname doteraz.
  8.  
  9.   Zo zadania mame predpoklad, ze nejake riesenie existuje.
  10.   Cas riesenia: 2^N * ( dake polynomialne drobne typu N*(logN + MlogM) )
  11.    */
  12.  
  13. #include <iostream>
  14. #include <map>
  15. #include <set>
  16. #include <string>
  17. #include <vector>
  18. #include <algorithm>
  19. using namespace std;
  20.  
  21. typedef vector<string> VS;
  22.  
  23. #define FOR(i,N) for(int i=0;i<(int)N;i++)
  24. #define PB push_back
  25.  
  26. int N,M;
  27. set<string> current,best,kandidat;
  28. //vstup. pre dane meno si pamatame vo vektore nazvy jeho schopnosti
  29. map<string,VS> MP;
  30. VS mena;
  31.  
  32. int main(){
  33.   cin >> M;
  34.   string s;
  35.   FOR(i,M) cin >> s;
  36.   cin >> N;
  37.   FOR(i,N){
  38.     int x;
  39.     cin >> x >> s;
  40.     mena.PB( s );
  41.     VS schopnost;
  42.     FOR(i,x){
  43.       string sch;
  44.       cin >> sch;
  45.       schopnost.PB(sch);
  46.     }
  47.     MP[s] = schopnost;
  48.   }
  49.  
  50.   //dummy riesenie, horsie od vsetkeho
  51.   FOR(i,N+1) best.insert( string(i+3,'z') );
  52.  
  53.   //skusime skupinu ludi danu binarnym zapisom cisla 'i'
  54.   FOR(i,(1<<N)){
  55.     current.clear();
  56.     kandidat.clear();
  57.     //zrekonstruujeme set skillov, ktory ma dana mnozina ludi
  58.     FOR(j,N) if (i & (1<<j)){
  59.       kandidat.insert( mena[j] );
  60.       FOR(k,MP[mena[j]].size()) current.insert( MP[mena[j]][k] );
  61.     }
  62.     //mnozina je vyhovujuca, ak tam je M roznych skillov
  63.     if ( (int)current.size() == M ){
  64.       if (kandidat.size() > best.size()) continue;
  65.       //vyuzijeme to, ze v pripade rovnosti velkosti mnozin robi comparator '<' presne to co chceme - porovnava lexikograficky
  66.       if (kandidat.size() < best.size()) best = kandidat;
  67.       else best = kandidat < best ? kandidat : best;
  68.     }
  69.   }
  70.  
  71.   for(set<string>::iterator it = best.begin(); it != best.end(); it++){
  72.     if (it != best.begin()) cout << " ";
  73.     cout << *it;
  74.   }
  75.   cout << endl;
  76.   return 0;
  77. }
Success #stdin #stdout 0.01s 2872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/V5ov3
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
12 years ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!