CCCSENIOR2009년 문제 2번 질문입니다.
똥덩어리
cccsenior2009년 문제 2번 질문입니다.요약할 수가 없네요..질문 내용 : = =
problem s2: the lights going on and off
problem description
for your birthday, you have been given a grid of r (1 r 30) rows of lights, with each row
containing l (1 l 8) lights. lights can be in one of two states: on or off. for this question,
the topmost row is row r, and the bottom-most row is row 1. also, beside all rows except the
topmost row (row r), there is a button which can be pushed.
pushing the button beside row k (1 k r) will peform an “exclusive-or” operation on each
light of row k, which is described below. consider column i in row k, where 1 i l. if the
lights in column i of row k and column i of row k + 1 are both the same (i.e., both on, or both
off), then pushing the button beside row k will cause the light in column i of row k to be off. if the
lights in column i of row k and column i of row k + 1 are different (i.e., one is on, and the other is
off), then pushing the button beside row k will cause the light in column i of row k to be on. an
example is shown below, for l = 4:
column numbers 1 2 3 4
row k + 1 on on off off
row k before button pushed on off on off
row k after button pushed off on on off
you are told which lights are initially on and which are initially off. you must calculate how many
different light patterns are possible for the bottom row by any sequence of button pushes.
input description
the first line of input will contain the integer r, the number of rows. the second line of input
will contain the integer l, the number of lights per row. the next r lines of input will contain
l integers, where the integer will either be 0 (to indicate “off”) or 1 (to indicate ”on”). pairs of
consecutive integers will be separated by one space character. these r lines will be given in topdown
order: that is, the third line of input will be the description of row r, the fourth line will be
r 1, and so on, until the last line describes the bottom row.
output description
output the number of possible light patterns of the bottom row.
sample input
4
3
0 0 1
0 1 1
1 0 1
0 0 1
output for sample input
4
간단히 문제를 설명해드리자면.
r*l의 전구셋트가 있습니다.
1 r 30, 1 = l 8 이구요.
즉, r은 l만큼의 전구가 몇개있다 그거구요.
l은 한 줄에 전구 몇개다 입니다.
여기서, row 1은 제일 아래있는 줄을 뜻합니다.
row r이 제일 위에있는 줄을 뜻합니다.
여기서, row r을 제외한 나머지 row에는 모두 버튼이 있는데, 이 버튼을 누르면
row k를 눌럿을 시, row k = (row k) xor (row k+1) 이 연산을 수행하고, row k에 들어가는 값이 전구 패턴의 하나가 됩니다.
이렇게해서.. 순서에 상관없이, 중복돼지 않게 전구 패턴이 총 몇가지 경우의 수가 있는지 찾는 프로그램입니다.
도와주세요.. ㅜ
막막하네요..
