编程介的小学生 2017-11-19 08:30 采纳率: 20.5%
浏览 623
已结题

Bad Wiring

Problem Description
The ninja Ryu has infiltrated the Shadow Clan fortress and finds himself in a long hallway. Although ninjas are excellent fighters, they primarily rely on stealth to complete their missions. However, many lights are turned on in the hallway, and this way it will not take long before Ryu is spotted by a guard. To remain unseen, Ryu will need to turn off all the lights as quickly as possible.
The hallway contains a sequence of n lights L1......Ln. Some of these lights are turned on. Destroy-ing the lights with his shurikens would be too loud, so he needs to turn them off the old-fashioned way, using light switches. Luckily, there is a switch box nearby with a light switch Si for every light Li. However, after trying one of the switches, he notices something funny. When he
ips the switch Si, it does not only turn on/off light Li, but also some of the neighboring lights. Ryu notices that there is a parameter D such that
ipping switch Si turns on/off all the lights L(i-D)......L(i+D), if they exist(This means that S1 turns on/off all the lights L1 ......L(D+1) and Sn turns on/off all the lights L(n-D)......Ln. Of course, if D>=n, then L(D+1) and L(n-D) will not exist either.). Turning on or off lights can attract the attention of the guards, so Ryu would like to turn off all the lights with the minimum number of times
ipping a switch. Can you help him out?

Input
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with two integers n (1 <= n <= 100) and D (0 <= D <= 15): the number of lights and the parameter mentioned above.
2.One line with n integers. The i(th) integer describes the current state of light Li, where 0 means off and 1 means on.

Output
For every test case in the input, the output should contain one integer on a single line: the minimum number of times Ryu needs to flip a switch to turn off all the lights. If it is impossible to turn off all the lights, then output the string "impossible" instead.
In the first example below,flipping switch S4 followed by S7 will turn off all the lights.

Sample Input
2
7 3
1 1 1 0 0 0 0
5 1
1 0 1 0 1

Sample Output
2
3

  • 写回答

1条回答 默认 最新

  • $(X) 2018-07-17 15:15
    关注
    /*from:  https://blog.csdn.net/ac_gibson/article/details/49182987*/
    #include <iostream>
    
    #include <cstdio>
    
    #include <cstring>
    
    using namespace std;
    
    const int maxn=100;
    
    const int inf=0x3fffffff;
    
    int a[maxn][maxn+1],x[maxn],equ,var;
    
    void Init()
    
    {
    
        int d,tmp;
    
        scanf("%d%d",&equ,&d);
    
        var=equ;
    
        memset(a,0,sizeof(a));
    
        memset(x,0,sizeof(x));
    
        for(int i=0;i<var;i++)
    
          scanf("%d",&a[i][var]);
    
        for(int i=0;i<var;i++)
    
        {
    
            for(int j=0;j<=d;j++)
    
            {
    
                if(i-j>=0) a[i-j][i]=1;
    
                if(i+j<var) a[i+j][i]=1;
    
            }
    
        }
    
    }
    
    void Debug()
    
    {
    
        for(int i=0;i<equ;i++)
    
        {
    
            for(int j=0;j<=var;j++)
    
              cout<<a[i][j]<<" ";
    
            cout<<endl;
    
        }
    
        cout<<endl;
    
    }
    
    int gcd(int a,int b)
    
    {
    
        if(a<0) return gcd(-a,b);
    
        if(b<0) return gcd(a,-b);
    
        return b==0?a:gcd(b,a%b);
    
    }
    
    void Gauss()
    
    {
    
        int k,col=0;
    
        for(k=0;k<equ&&col<var;k++,col++)
    
        {
    
            int mx=k;
    
            for(int i=k+1;i<equ;i++)
    
               if(a[i][col]>a[mx][col]) mx=i;
    
            if(mx!=k)
    
            {
    
                for(int i=k;i<var+1;i++)
    
                   swap(a[k][i],a[mx][i]);
    
            }
    
            if(!a[k][col])
    
            {
    
                k--; continue;
    
            }
    
            for(int i=k+1;i<equ;i++)
    
            if(a[i][col])
    
            {
    
                int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col];
    
                int ta=lcm/a[i][col],tb=lcm/a[k][col];
    
                for(int j=col;j<var+1;j++)
    
                   a[i][j]=((a[i][j]*ta-a[k][j]*tb)%2+2)%2;
    
            }
    
        }
    
        //Debug();
    
        for(int i=k;i<equ;i++)
    
          if(a[i][col])
    
          {
    
              puts("impossible");
    
              return ;
    
          }
    
        for(int i=0,j;i<equ;i++)
    
           if(a[i][i]==0){
    
               for(j=i+1;j<var;j++)
    
                  if(a[i][j]) break;
    
               if(j>=var) break;
    
               for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]);
    
        }
    
       int Min=inf;
    
       for(int j=0;j<(1<<(equ-k));j++)
    
         {
    
            int tmp=j,p=equ-1;
    
            while(tmp) x[p--]=tmp%2,tmp>>=1;
    
            for(int i=k-1;i>=0;i--)
    
            {
    
              int tmp=a[i][var]%2;
    
              for(int j=i+1;j<var;j++)
    
                 if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%2+2)%2;
    
              x[i]=(tmp/a[i][i])%2;
    
            }
    
            tmp=0;
    
            for(int i=0;i<var;i++) tmp+=x[i];
    
            Min=min(Min,tmp);
    
         }
    
       printf("%d\n",Min);
    
    }
    
    int main()
    
    {
    
        int t,q;
    
        scanf("%d",&t);
    
        while(t--)
    
        {
    
            Init();
    
            Gauss();
    
        }
    
        return 0;
    
    }
    
    评论

报告相同问题?

悬赏问题

  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥50 汇编语言除法溢出问题
  • ¥65 C++实现删除N个数据列表共有的元素
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波