USACO 2.2 - Party Lamps

To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

• Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
• Button 2: Changes the state of all the odd numbered lamps.
• Button 3: Changes the state of all the even numbered lamps.
• Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,...

A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.

PROGRAM NAME: lamps

INPUT FORMAT

No lamp will be listed twice in the input.

Line 1:	N
Line 2:	Final value of C
Line 3:	Some lamp numbers ON in the final configuration, separated by one space and terminated by the integer -1.
Line 4:	Some lamp numbers OFF in the final configuration, separated by one space and terminated by the integer -1.

SAMPLE INPUT (file lamps.in)

10
1
-1
7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.

OUTPUT FORMAT

Lines with all the possible final configurations (without repetitions) of all the lamps. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. The lines must be ordered from least to largest (as binary numbers).

If there are no possible configurations, output a single line with the single word `IMPOSSIBLE'

SAMPLE OUTPUT (file lamps.out)

0000000000
0101010101
0110110110

In this case, there are three possible final configurations:

• All lamps are OFF
• Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON.
• Lamps 1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.

출처: http://train.usaco.org/

1부터 N 까지의 램프가 있다. 램프에 4개의 버튼이 있고 각각의 버튼은 다음과 같은 일을 한다.1

1: 모른 램프의 상태를 변경 (on -> off, off -> on)

2. 홀수 램프 상태 변경

3: 짝수 램프 상태 변경

4: 3k + 1 램프의 상태 변경

파티가 시작될 때 모든 램프는 켜져있습니다.

램프의 개수 N 과 버튼을 누를 횟수 C 그리고 최종적으로 켜져있어야 될 램프와 꺼져있어야 될 램프가 주어질 경우 가능한 모든 경우를 중복없이 구하시오.

input

1:  N

2: C

3: 켜져있어야 될 램프. 공백으로 구분되며 -1일 경우 종료

4. 꺼져있어야 될 램프. 공백으로 구분되며 -1일 경우 종료

output

꺼져있을 경우0, 켜져있을 경우 1, binary numbers 기준으로 오름차순으로 출력.

가능한 경우가 없을 경우 'IMPOSSIBLE' 출력.

처음에는 모든 경우를 구하는 brute force 방법을 사용했으나 c가 100인 상황에서 1초가 초과됬습니다. 그래서 다음 방법으로 c가 아무리 크더라도 결국 키고 끄는 행위를 반복할 뿐이라는 점을 이용해서 필요한 상황만 계산을 해서 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;
typedef long long ll;
 
ofstream fout("lamps.out");
int n;
vector<bool> lamps;
vector<int> on;
vector<int> off;
set<string> ret;
 
bool whetherMeet()
{
    for (vector<int>::iterator it = on.begin(); it != on.end(); it++)
    {
        if (lamps[*it] == false)
            return false;
    }
    for (vector<int>::iterator it = off.begin(); it != off.end(); it++)
    {
        if (lamps[*it])
            return false;
    }
 
    return true;
}
 
void changeState(int type)
{
    switch (type)
    {
    case 1:
        for (vector<bool>::iterator it = lamps.begin(); it != lamps.end(); it++)
            *it = !*it;
        break;
    case 2:
        for (int i = 0; i < n; i += 2)
            lamps[i] = !lamps[i];
        break;
    case 3:
        for (int i = 1; i < n; i += 2)
            lamps[i] = !lamps[i];
        break;
    case 4:
        for (int i = 0; i < n; i += 3)
            lamps[i] = !lamps[i];
        break;
    default:
        break;
    }
}
 
//It used more than the allotted runtime of 1 seconds when c is over 100
void bruteForce(int remainingNumber)
{
    if (remainingNumber == 0)
    {
        if (whetherMeet())
        {
            string str = "";
            for (int i = 0; i < n; i++)
                str += to_string((int)lamps[i]);
            ret.insert(str);
        }
        return;
    }
 
    for (int i = 1; i < 5; i++)
    {
        changeState(i);
        bruteForce(remainingNumber - 1);
        changeState(i);
    }
}
 
void greedy(int c)
{
    for (int i = 0; i < 1 << 4; i++)
    {
        int type[4] = { i & 1, i >> 1 & 1, i >> 2 & 1, i >> 3 & 1 };
        int bitCount = 0;
        for (int i = 0; i < 4; i++)
            bitCount += type[i];
 
        if (bitCount > c)
            continue;
 
        if (bitCount % 2 != c & 2)
            continue;
 
        fill(lamps.begin(), lamps.end(), 1);
 
        for (int i = 0; i < 4; i++)
        {
            if (type[i] == 1)
                changeState(i + 1);
        }
 
        if (whetherMeet())
        {
            string str = "";
            for (int i = 0; i < n; i++)
                str += to_string((int)lamps[i]);
            ret.insert(str);
        }
    }
}
 
int main()
{
    ifstream fin("lamps.in");
    
    int c;
    fin >> n >> c;
 
    int lamp;
    while (fin >> lamp)
    {
        if (lamp == -1)
            break;
        on.push_back(lamp - 1);
    }
    while (fin >> lamp)
    {
        if (lamp == -1)
            break;
        off.push_back(lamp - 1);
    }
 
    vector<bool> temp(n, 1);
    lamps = temp;
 
    greedy(c);
 
 
    if (ret.empty())
    {
        fout << "IMPOSSIBLE" << endl;
    }
    else
    {
        for (set<string>::iterator it = ret.begin(); it != ret.end(); it++)
            fout << *it << endl;
    }
 
    fin.close();
    fout.close();
    return 0;
}