2.2.4 Party Lamps 派对灯

2.2.4 Party Lamps 派对灯

时间: 1ms        内存:64M

描述:

在IOI98的节日宴会上,我们有N(10<=N<=100)盏彩色灯,他们分别从1到N被标上号码。 这些灯都连接到四个按钮: 按钮1:当按下此按钮,将改变所有的灯:本来亮着的灯就熄灭,本来是关着的灯被点亮。 按钮2:当按下此按钮,将改变所有奇数号的灯。 按钮3:当按下此按钮,将改变所有偶数号的灯。 按钮4:当按下此按钮,将改变所有序号是3*K+1(K>=0)的灯。例如:1,4,7...
一个计数器C记录按钮被按下的次数。
当宴会开始,所有的灯都亮着,此时计数器C为0。
你将得到计数器C(0<=C<=10000)上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态,并且没有重复。

输入:

不会有灯会在输入中出现两次。
第一行: N。
第二行: C最后显示的数值。
第三行: 最后亮着的灯,用一个空格分开,以-1为结束。
第四行: 最后关着的灯,用一个空格分开,以-1为结束。

输出:

每一行是所有灯可能的最后状态(没有重复)。每一行有N个字符,第1个字符表示1号灯,最后一个字符表示N号灯。0表示关闭,1表示亮着。这些行必须从小到大排列(看作是二进制数)。
如果没有可能的状态,则输出一行'IMPOSSIBLE'。

示例输入:

10
1
-1
7 -1

/*在这个样例中,有10盏灯,只有1个按钮被按下。最后7号灯是关着的。*/

示例输出:

0000000000
0101010101
0110110110

/*在这个样例中,有三种可能的状态:

所有灯都关着 
1,4,7,10号灯关着,2,3,5,6,8,9亮着。 
1,3,5,7,9号灯关着,2, 4, 6, 8, 10亮着。*/

提示:

参考答案(内存最优[1268]):

#include <iostream>
using namespace std;

#define N 101

int n,c;
int light[9][7]={
	0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,
	0,0,0,1,1,1,0,
	0,0,1,0,1,0,1,
	0,0,1,1,0,1,1,
	0,1,0,0,1,0,0,
	0,1,0,1,0,1,0,
	0,1,1,0,0,0,1,
	0,1,1,1,1,1,1,
};//常量表

int minnum[9]={0,1,2,1,1,2,1,2,0};//对应常量表8个状态最少摁的次数
int dat[N];
bool flag1,flag2;

int main()
{
	int i,j,tmp;
	cin>>n>>c;
	for(i=1;i<=n;i++)
		dat[i]=-1;
	while(cin>>tmp&&tmp!=-1)
		dat[tmp]=1;
	while(cin>>tmp&&tmp!=-1)
		dat[tmp]=0;
	flag1=false;
	for(i=1;i<9;i++)
	{
		flag2=true;
        for(j=1;j<=n;j++)
        {
			if(dat[j]==-1)//如果没有确定是亮或灭
				continue;
			tmp=j%6;//六位循环
			if(tmp==0)//如果是6的倍数
				tmp=6;
			if(dat[j]!=light[i][tmp])//有个灯不同说明不是这个状态,结束判断
			{
				flag2=false;
				break;
			}
        } 
        if(flag2==true&&c>=minnum[i])
		{
			flag1=true;//有一个满足条件就标记
			for(j=1;j<=n;j++)
			{
				tmp=j%6;
				if(tmp==0)
					tmp=6;
				cout<<light[i][tmp];
			}
			cout<<endl;
		}
	}
	if(flag1==false)
		cout<<"IMPOSSIBLE"<<endl;
	return 0;      
}

参考答案(时间最优[4]):

/*
ID: zhuihun1
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define MAXSIZE 105
using namespace std;
ofstream fout ("lamps.out");
ifstream fin ("lamps.in");
int n,c,pwo_n=0,powon[MAXSIZE],pwf_n=0,powoff[MAXSIZE],re_n=0;
int visited[MAXSIZE],light[MAXSIZE];
bool state[MAXSIZE];
string res[10000];
void change(int x)
{
    int i;
    switch(x)
    {
        case 0:
        for(i=0;i<n;i++)
        {
            if(state[i]==1) state[i]=0;
            else state[i]=1;
        }
        break;
        case 1:
        for(i=0;i<n;i++)
        {
            if((i+1)%2==1)
            {
                if(state[i]==1) state[i]=0;
                else state[i]=1;
            }
        }
        break;
        case 2:
        for(i=0;i<n;i++)
        {
            if((i+1)%2==0)
            {
                if(state[i]==1) state[i]=0;
                else state[i]=1;
            }
        }break;
        case 3:
        for(i=0;i<n;i++)
        {
            if(i%3==0)
            {
                if(state[i]==1) state[i]=0;
                else state[i]=1;
            }
        }break;
    }
}
bool manzu()
{
    memset(state,1,sizeof(state));
    for(int i=0;i<c;i++)
        change(light[i]);
    for(int i=0;i<pwo_n;i++)
        if(state[powon[i]-1]!=1)
            return false;
    for(int i=0;i<pwf_n;i++)
        if(state[powoff[i]-1]!=0)
            return false;
    return true;
}
bool cunzai(string str)
{
    for(int i=0;i<re_n;i++)
        if(res[i]==str)
            return false;
    return true;
}
void zuhe(int x)
{
    if(x==c)
    {
        if(!manzu())
            return;
        string tmp="";char c;
        for(int i=0;i<n;i++)
        {
            c=state[i]+'0';
            tmp+=c;
        }
        if(cunzai(tmp))
            res[re_n++]=tmp;
        return;
    }
    for(int i=0;i<4;i++)
    {

        if(i>=light[x-1])
        {
            light[x]=i;
            zuhe(x+1);
        }
    }
}
int main()
{
    memset(visited,0,sizeof(visited));
    memset(light,-1,sizeof(light));
    cin>>n>>c;
    if(c>4)
        c=4-c%2;
    int t;
    while(cin>>t&&t!=-1)
        powon[pwo_n++]=t;
    while(cin>>t&&t!=-1)
        powoff[pwf_n++]=t;
    zuhe(0);
    sort(res,res+re_n);
    if(re_n==0)
        cout<<"IMPOSSIBLE";
    else
        for(int i=0;i<re_n;i++)
            cout<<res[i]<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注