Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.2 kB
7
Indexable
Never
//////// Painting: 
#include <iostream>
using namespace std;

//int dx[6]={1,-1,-1,-1,1,1};
//int dy[6]={0,0,-1,1,1,-1};
int dx[5]={0,0,-1,1,0};
int dy[5]={0,-1,0,0,1};
int kq;
int a[30][30];
int c[30];
int used[30][4];
int dem;
int n;
void backtrack(int k){
	if(k==n) {
		dem++;
		return;
	}
	for(int i=0; i<4; i++){
		used[k][i]=0;
	}
	for(int i=0; i<k; i++){
		if(a[k][i]==1) {
			used[k][c[i]]=1;
		}
	}
	for(int i=0; i<4; i++){
		if(used[k][i]==0){
			c[k]=i;
			backtrack(k+1);
		}
	}

}



int main(){
	//freopen("input.txt", "r", stdin);
	//nhap lieu
	int t; 
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cout<<"Case #"<<tc<<endl;
		cin>>n;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cin>>a[i][j];
			}
		}
		dem=0;
		backtrack(0);
		
		cout<<dem<<endl;
	}
return 0;
}


// Turn over game
#include <iostream>
using namespace std;

//int dx[6]={1,-1,-1,-1,1,1};
//int dy[6]={0,0,-1,1,1,-1};
int dx[5]={0,0,-1,1,0};
int dy[5]={0,-1,0,0,1};
int kq;
char a[4][4];
int dem;
void lat(int x, int y){
	for(int i=0; i<5; i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&xx<4&&yy>=0&&yy<4){
			if(a[xx][yy]=='b') a[xx][yy]='w';
			else if(a[xx][yy]=='w') a[xx][yy]='b';
		}
	}
}
bool fullmau(){
	int demden=0;
	int demtrang=0;
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			if(a[i][j]=='b') demden++;
			 if(a[i][j]=='w') demtrang++;
		}
	}
	if(demden==16||demtrang==16) return true;
	else return false;
}
void backtrack(int k){
	if(dem>kq&&!fullmau()) return;
	if(fullmau()) {
		if(kq>dem) kq=dem;
		return;
	}
	if(k==16) {
		return;
	}
	for(int i=0; i<2; i++){
		if(i==0){
			backtrack(k+1);
		}
		else{
			dem++;
			lat(k/4,k%4);
			backtrack(k+1);
			lat(k/4,k%4);
			dem--;
		}
	}

}



int main(){
	//freopen("input.txt", "r", stdin);
	//nhap lieu
	int t; 
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cout<<"Case #"<<tc<<endl;
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				cin>>a[i][j];
			}
		}
		dem=0;
		kq=10000;
		backtrack(0);
		if(kq==10000) cout<<"impossible"<<endl;
		else cout<<kq<<endl;
	}
return 0;
}
// checking cube
#include<iostream>
using namespace std;

int N;          
int Answer;     
int arr[51];      
int Leng;      

int cnt = 0;
void BT(int k, int index, int N)
{
	if (N == 0)
	{
		cnt++;
		return;
	}
    
    if(k == 5)
    {
        return;
    }

    
    for(int i = index; i >  0; i--){
		
		if	(N >= arr[i])		
		BT(k + 1,i, N - arr[i]);
	}
}

int main()
{
    
   // freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		cnt = 0;
		cin >> N;
		int index   = 0;

// MAKE AN ARRAY OF 50 CUBE
    
		for (int i = 0; i <= 50; i++)
		{
			arr[i] = i*i*i;
			if (arr[i] > N)
			index = i - 1;
		}
// 		
		/*for (int i = 0; i <= 50; i++)
		{
			if (arr[i] > N)
			index = i - 1;
		}*/


    
    BT(0, index,N);

	cout <<"#"<<tc<<" "<< cnt << endl;

	}
    return 0;
}

// computer ungrade

#include <iostream>
using namespace std;

//int dx[6]={1,-1,-1,-1,1,1};
//int dy[6]={0,0,-1,1,1,-1};
//int dx[2]={0,-1};
//int dy[2]={-1,0};
int n,m,l;
int gia_cho[20];
int online[30][2];
int lk_on[30][20];
int can_mua[20];
int da_mua[20];
int kq;
int price;


void buy(int k){
	price+=online[k][0];
	for(int i=0; i<online[k][1]; i++){
		da_mua[lk_on[k][i]]++;
	}
}
void unbuy(int k){
	price-=online[k][0];
	for(int i=0; i<online[k][1]; i++){
		da_mua[lk_on[k][i]]--;
	}
}
void backtrack(int k){
	if(price>kq) return;
	if(k==m) {
		int sum=price;
		for(int i=0; i<l; i++){
			if(da_mua[can_mua[i]]<1) sum+=gia_cho[can_mua[i]];
		}
		if(sum<kq) kq=sum;
		return;
	}
	for(int i=0; i<2; i++){
		
		if(i==0)  backtrack(k+1);
		else{
			buy(k);
			backtrack(k+1);
			unbuy(k);
		}
	}
}



int main(){
	//freopen("input.txt", "r", stdin);
	//nhap lieu
	int t; 
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		//cout<<"Case #"<<tc<<endl;
		cin>>n;
		for(int i=0; i<n; i++){
			cin>>gia_cho[i];
		}
		cin>>m;
		for(int i=0; i<m; i++){
			int x,y;
			cin>>x>>y;
			online[i][0]=x;
			online[i][1]=y;
			for(int j=0; j<y; j++){
				int x;
				cin>>x;
				lk_on[i][j]=x-1;
			}
		}
		cin>>l;
		for(int i=0; i<l; i++){
			int x;
			cin>>x;
			can_mua[i]=x-1;
		}
		price=0;
		kq=1000000;
		backtrack(0);
		cout<<"#"<<tc<<" "<<kq<<endl;
	}
return 0;
}