neoevoke » [usaco] 2.2 Party Lamps

[usaco] 2.2 Party Lamps - usaco

2009.08.14 14:22 neoevoke Edit

램프는 6개 이상 볼 필요 없고
operation은 2번이상하면 원래대로 돌아오기 때문에 2번이상 해볼 필요 없으니까
총 16가지 경우에 대해서만 고려하면 되는 문제였다.

/*
ID: neoevok1
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>

using namespace std;

int n,c;

vector<int> on, off;

vector<bitset<6> > ret;

bool const cmp(const bitset<6> a, const bitset<6> b) 
{
	for(int i=0;i<6;i++)
		if(a[i]<b[i]) return true;
		else if(a[i]>b[i]) return false;
	return false;
}

void dfs(int d, bitset<6> b, bitset<4> v)
{
	if(d<=c)
	{
		bool found=true;
		for(int i=0;i<(int)on.size();i++)
		{
			if(b[on[i]%6]==0)
				found=false;
		}
		for(int i=0;i<(int)off.size();i++)
		{
			if(b[off[i]%6]==1)
				found=false;
		}
		if(found)
		{
			vector<bitset<6> >::iterator it=find(ret.begin(), ret.end(), b);
			if(it==ret.end())
				ret.push_back(b);
		}
	}

if(v[0]==0)
	{
		for(int i=0;i<6;i++)
			b[i]=1-b[i];
		v[0]=1;
		dfs(d+1,b,v);
		v[0]=0;
		for(int i=0;i<6;i++)
			b[i]=1-b[i];
	}

if(v[1]==0)
	{
		for(int i=0;i<3;i++)
			b[i*2]=1-b[i*2];
		v[1]=1;
		dfs(d+1,b,v);
		v[1]=0;
		for(int i=0;i<3;i++)
			b[i*2]=1-b[i*2];
	}

if(v[2]==0)
	{
		for(int i=0;i<3;i++)
			b[i*2+1]=1-b[i*2+1];
		v[2]=1;
		dfs(d+1,b,v);
		v[2]=0;
		for(int i=0;i<3;i++)
			b[i*2+1]=1-b[i*2+1];
	}

if(v[3]==0)
	{
		for(int i=0;i<2;i++)
			b[i*3]=1-b[i*3];
		v[3]=1;
		dfs(d+1,b,v);
		v[3]=0;
		for(int i=0;i<2;i++)
			b[i*3]=1-b[i*3];
	}
}

int main() {
    ofstream fout ("lamps.out");
    ifstream fin ("lamps.in");

fin >> n >> c;
	
	while(1)
	{
		int t;
		fin >> t;
		if(t==-1) break;
		t--;
		on.push_back(t);
	}

while(1)
	{
		int t;
		fin >> t;
		if(t==-1) break;
		t--;
		off.push_back(t);
	}

dfs(0, bitset<6>(string("111111")), bitset<4>(string("0000")));

sort(ret.begin(), ret.end(), cmp);

if(ret.empty())
		fout << "IMPOSSIBLE" << endl;

for(int i=0;i<(int)ret.size();i++)
	{
		for(int j=0;j<n;j++)
			fout << ret[i][j%6];
		fout << endl;
	}
	return 0;
}

[usaco] 2.3 The Longest Prefix [usaco] 2.2 Runaround Numbers

Trackbacks 0

엮인글 주소: http://dw.yutar.net/329409/8c8/trackback

Comments 0

Leave Comments

neoevoke난 전설 같은건 믿지 않아

[usaco] 2.2 Party Lamps - usaco

Trackbacks 0

Comments 0

Leave Comments

Category

Recent Post

Recent Comment

Recent Trackback

Tag