fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <fstream>
  5. #include <cstring>
  6. #include <string>
  7. #define For(i,a,b) for(i=a;i<=b;i++)
  8. using namespace std;
  9.  
  10.  int arr[18];
  11.  int res,t,n,k,m,oper;
  12.  
  13.  
  14. /*this function returns whether the sequence is valid or not*/ 
  15.  bool isValid(){
  16.      int hash[19],i,maxm=0,j;
  17.  	memset(hash,0,sizeof(hash));
  18.  	For(i,1,n+1){
  19.  		if(i-k>=1){
  20.  			maxm=0;
  21.  			For(j,1,18){
  22.  				if(hash[j])
  23. 					maxm = max(maxm,j);
  24.  			}
  25.  			if(hash[maxm]>=m)
  26.  				return 0;
  27.  			hash[arr[i-k]]-=1;
  28.  		}
  29.  	    if(i<=n)
  30.  			hash[arr[i]]++;
  31.  	}
  32.  	return 1;
  33.  }
  34.  
  35.  /*using backtracking search() is creating all permutations*/
  36.  /*its argument is the index of the array,oper is the operations performed till now*/
  37.  
  38.  void search(int i){
  39.  	if(i>n){
  40.  		if(isValid()){
  41.  			res = min(res,oper);
  42.  		/*cout<<"This sequence is valid:\n";
  43.  			int l;
  44.  			For(l,1,n)
  45.  				cout<<arr[l]<< " ";
  46.  			cout<<endl;	*/
  47.  		}
  48.  		return;
  49.  	}
  50.  	int k;
  51.  	For(k,i,n+1){
  52.  		arr[k]+=1;
  53.  	  if(k<=n)
  54.  		oper++;
  55.  		search(k+1);
  56.  	  if(k<=n)	
  57.  		oper--;
  58.  		arr[k]-=1;
  59.  	}
  60.  }
  61.  
  62.  int main(){
  63.   cin>>t;
  64.   while(t--){
  65.   	oper = 0;
  66.   	res = 18;
  67.   	cin>>n>>k>>m;
  68.   	int i;
  69.   	For(i,1,n)
  70.   		cin>>arr[i];
  71.   	search(1);
  72.   	if(res<=n)
  73.   		cout<<res<<endl;
  74.   	else
  75.   		cout<<-1<<endl;	
  76.   }
  77.  return 0;
  78.  }
Success #stdin #stdout 0.02s 2680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/K0x9CH
language:
C++ (gcc 8.3)
created:
11 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!